#16005: Waste of time in iterator_edges 2
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.2
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers: Vincent Delecroix
theory | Work issues:
Keywords: | Commit:
Authors: | 567600b943c81837a5bc525136b55c6f7878327b
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/16005 |
Dependencies: |
#15978 |
-------------------------+-------------------------------------------------
Changes (by vdelecroix):
* reviewer: => Vincent Delecroix
Comment:
Hi Nathann,
Some old timings
{{{
sage: g=graphs.RandomGNP(1500,.4)
sage: timeit('for e in g.edge_iterator(): pass')
5 loops, best of 3: 684 ms per loop
}}}
Some new timings
{{{
sage: g=graphs.RandomGNP(1500,.4)
sage: timeit('for e in g.edge_iterator(): pass')
5 loops, best of 3: 317 ms per loop
}}}
This is definitely cool!
Question for further optimization: why in the `SparseGraphBackend` the
methods `iterator_edges`, `iterator_in_edges` and `iterator_out_edges` do
not use the `out_neighbors_unsafe`/`in_neighbors_unsafe` of `SparseGraph`
with an array `int * neighbors` allocated once for all to the maximum of
the degrees? That would avoid as many "malloc"+"list creation" as there
are number of vertices in the call.
--
Ticket URL: <http://trac.sagemath.org/ticket/16005#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
