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
