#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):
[[Image(http://lobi.dev.si/s.png)]]
Hello,
on picture you can see a diagram what happens when we call neighbors() on
graph. You can see there is a lot conversion from set/iter and then back
again.
Where this conversion is not necessary I remove it.
But most time reduction was made (for ours specific test), when function
neighbor_iterator (F2) start calling iterator_out_nbrs (F4.2) for
undirected graph instead iterator_nbrs (F3.1). If graph is undirected we
only need out nbrs. or in nbrs.??????????
{{{
Before:
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
125 loops, best of 3: 2.03 ms per loop
Now:
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
625 loops, best of 3: 900 µs per loop
}}}
I also remove
{{{
#Sparse
if self._cg_rev is not None:
return iter([vertex_label(u_int,
self.vertex_ints,
self.vertex_labels,
self._cg)
for u_int in self._cg_rev.out_neighbors(v_int)])
}}}
in iterator_in_nbrs (F 4.1). I don't know what relation this has with
sparse/dense.
But most time consuming problem is conversion from vertex int to vertex
label in iterator_out_nbrs (F4.2) and iterator_in_nbrs (F4.1)
This conversion for our specific test takes almost 500 µs.
I tried to implement array of python object in cython, where we can save
vertex labels, but I was unsuccessful, because I don't know cython well
(yet). Maybe someone can help me?
If this is a good solution then we can return iter of vertex labels
instead of list of vertex int from cpdef list out_neighbors (F5).
So what do you think?
Best,
Uros
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13730#comment:16>
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.
