The bug is almost trivial. The code
verts = data.keys()
....
for u in data:
verts.union([v for v in data[u] if v not in verts])
is slowing down because in python searching in lists is slow. If we
use "verts = set(data.keys())" the code speeds up tremendously.
sage: D={}
sage: for i in xrange(10^3):
....: D[i]=[i+1,i-1]
....:
sage: timeit('g=Graph(D)')
5 loops, best of 3: 79.6 ms per loop
Before I submit a patch how do I run the the graph theory doctests to
make sure nothing else is broken by changing verts from list to set?
Rado
On May 10, 3:40 pm, William Stein <wst...@gmail.com> wrote:
> On Sun, May 10, 2009 at 10:18 AM, Rado <rki...@gmail.com> wrote:
>
> > I was playing with some big(10^6) graphs and noticed SAGE cannot
> > handle constructing them in good time. However, networkx does just
> > fine. Before I dive into the code, is this a feature (i.e. sage graph
> > object has richer data and methods available) or this is a bug?
>
> > sage: D={}
> > sage: for i in xrange(10^3):
> > D[i]=[i+1,i-1]
> > ....:
> > sage: timeit('g=Graph(D)')
> > 5 loops, best of 3: 2.05 s per loop
> > sage: import networkx
> > sage: timeit('g=networkx.XGraph(D)')
> > 25 loops, best of 3: 21.9 ms per loop
>
> > Rado
>
> That's definitely a bug. By the way, amusingly, you can do this to
> very quickly get the Sage graph you want:
>
> sage: time g=Graph(networkx.XGraph(D))
> CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
> Wall time: 0.04 s
>
> William
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
