#15035: removing redundant set/iter conversions in graph backend
----------------------------+----------------------------------------------
Reporter: slani | Owner:
Type: | Status: positive_review
enhancement | Milestone: sage-5.12
Priority: minor | Resolution:
Component: graph | Merged in:
theory | Reviewers: Nathann Cohen, Jernej Azarija
Keywords: | Work issues:
Authors: Uros | Dependencies:
Slana |
Report Upstream: N/A |
Branch: |
Stopgaps: |
----------------------------+----------------------------------------------
Description changed by slani:
Old description:
> Hello,
>
> this patch speeds up neighbor iterator method when the original graph is
> not directed. The speed up is achieved by removing unnecessary set
> conversions in the graph backend.
> (as seen on a figure in ticket [http://trac.sagemath.org/ticket/13730].)
>
> Before:
> {{{
> sage: G = graphs.RandomBarabasiAlbert(1000,2)
> sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
> 100 loops, best of 3: 7.8 ms per loop
>
> }}}
>
> After:
> {{{
> sage: G = graphs.RandomBarabasiAlbert(10**6,2)
> sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
> 100 loops, best of 3: 3.58 ms per loop
>
> }}}
New description:
Hello,
this patch speeds up neighbor iterator method when the original graph is
not directed. The speed up is achieved by removing unnecessary set
conversions in the graph backend.
(as seen on a figure in ticket [http://trac.sagemath.org/ticket/13730].)
Before:
{{{
sage: G = graphs.RandomBarabasiAlbert(1000,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
100 loops, best of 3: 7.8 ms per loop
}}}
After:
{{{
sage: G = graphs.RandomBarabasiAlbert(1000,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
100 loops, best of 3: 3.58 ms per loop
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/15035#comment:5>
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/groups/opt_out.
