#13730: Speed up some graph iterations
--------------------------------+-------------------------------------------
Reporter: dcoudert | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.10
Component: graph theory | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
--------------------------------+-------------------------------------------
Comment (by slani):
Hello,
I tried with yield in iterator_out_nbrs (l:1745, c_graph.pyx) but it does
not improve anything.
{{{
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
625 loops, best of 3: 940 µs per loop
}}}.
I did a lot of modification and testing (also tried with new function in
cython which use yield for returning nbrs), but didn't improve anything.
I also made a function (in generic_graph.py) which directly call cpdef
list out_neighbors (base/sparse_graph.pyx; l:798):
{{{
sage: %timeit E = [(u,v) for u in G for v in G.neighbors_three(u)]
625 loops, best of 3: 362 µs per loop
}}}
It is still slower than NetworkX!
I don't know, but I came to the conclusion that we have tow problems:
1. conversion from vertex ints to vertex lables
2. how to faster return vertex ints from data structure we have for nbrs
Vincent, what do you think?
This is also interesting for me:
{{{
sage: G
Graph on 100 vertices
sage: ggnx
<networkx.classes.graph.Graph object at 0x65c8ed0>
sage: %timeit E = [(u,v) for u in G for v in G.neighbors_three(u)]
625 loops, best of 3: 358 µs per loop
sage: %timeit E = [(u,v) for u in ggnx for v in G.neighbors_three(u)]
625 loops, best of 3: 273 µs per loop
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors(u)]
625 loops, best of 3: 213 µs per loop
}}}
Best,
Uros
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13730#comment:22>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
