Hi Nathann,
Thank you for the timely updates! I agree with you about the calls to
random. I can move those out of the timing portion. I suspected that
the passage to the backend was probably responsible for the slow speed
of the add/remove edge/vertices calls. The cost of method calls is
overhead I'm willing to swallow if the harder algorithms are
faster. :)
As for the scc() method, the "_digraph()" problem was my fault--I
didn't understand how scc_digraph() worked. Unfortunately, after
removing "_digraph()" the timings are just as bad. Sample below:
(1000 node graph)
scc() -- 10 trials: sage_cgraph 1362871.89 usec [ now computed using
self.M.strongly_connected_components() (see previous post in thread) ]
scc() -- 10 trials:    networkx    6015.06 usec I'm afraid I'm still
missing something crucial here? :-? Also, as a confirmation of your
argument concerning the calls to the backend, the Sage implementation
of NetworkX (implementation='networkx' instead of 'c_graph') does work
nearly as as fast as pure NetworkX after removing "_digraph()"--and
still much faster than the c_graph implementation.
As far as which functions/methods to benchmark, I am (or rather we
are) interested in a few specific graph algorithms, scc() among them.
That's why I've been picking on scc(). As a side note, I've also been
testing subgraph functionality. Eg.,
 self.M.subgraph(self.rand_verts(K)), which maybe has a better
implementation using subgraph_search() ??
Anyways, I greatly appreciate your help with this. It would be great
to be able to use Sage/Python to run all of our code.
Merry Christmas,Jesse
On Dec 25, 3:08 am, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Oh yes, and something else about your benchmark : try to avoid using "rand"
> methods when you are doing one, especially when you test such low-level
> methods, because often the rand() method represents  an important part of
> the time.
>
> The best would be to compute all the random number you need in a first
> phase, then run %timeit on the add_edge part.
>
> Well, it probably will not reflect well on Sage because it should increase
> the differences between the libraries, but I think that it is very
> important in your benchmark, To give you an idea :
>
> sage: from numpy import random as rnd
> sage:
> sage: g = Graph(500)
> sage: def rand_entry(G):
> ....:     ...    n = G.order()
> ....:     ...    i = rnd.randint(0,n-1)
> ....:     ...    j = rnd.randint(0,n-1)
> ....:     ...    G.add_edge(i,j)
> ....:     ...    G.delete_edge(i,j)
> ....:
> sage: def just_rand(G):
> ....:     ...    n = G.order()
> ....:     ...    i = rnd.randint(0,n-1)
> ....:     ...    j = rnd.randint(0,n-1)
> ....:     ...    return i*j
> ....:
> sage: %timeit rand_entry(g)
> 625 loops, best of 3: 20.4 µs per loop
> sage: %timeit just_rand(g)
> 625 loops, best of 3: 4.93 µs per loop
>
> So 20% of the time used by this test method is actualy used by calls to
> "random()" :-)
>
> Nathann

-- 
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to 
sage-support+unsubscr...@googlegroups.com
For more options, visit this group at 
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org

Reply via email to