#10433: clean up the code for Kruskal's algorithm
-------------------------------+--------------------------------------------
Reporter: mvngu | Owner: jason, ncohen, rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-4.6.2
Component: graph theory | Keywords:
Author: Minh Van Nguyen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by ncohen):
* status: needs_review => needs_info
Comment:
Hello Minh !!!
I'm sorry to come back with another thing to fix after having made so many
remarks, but I really hadn't thought this problem would occur.. I just did
some profiling, and even though your code is faster when no checkings are
required, there is a large slowdown by default :
* With checkings :
{{{
#!python
for i in range(10):
g = graphs.RandomGNP(50,.3)
timeit("g.min_spanning_tree()")
25 loops, best of 3: 13.1 ms per loop
25 loops, best of 3: 12.7 ms per loop
25 loops, best of 3: 12.5 ms per loop
25 loops, best of 3: 12.5 ms per loop
25 loops, best of 3: 13.1 ms per loop
25 loops, best of 3: 12.6 ms per loop
25 loops, best of 3: 12 ms per loop
25 loops, best of 3: 11.9 ms per loop
25 loops, best of 3: 12.8 ms per loop
25 loops, best of 3: 13.2 ms per loop
}}}
* Without Checkings :
{{{
#!python
for i in range(10):
g = graphs.RandomGNP(50,.3)
timeit("g.min_spanning_tree(check=False)")
125 loops, best of 3: 2.36 ms per loop
125 loops, best of 3: 2.1 ms per loop
125 loops, best of 3: 2.34 ms per loop
125 loops, best of 3: 2.49 ms per loop
125 loops, best of 3: 2.42 ms per loop
125 loops, best of 3: 2.36 ms per loop
125 loops, best of 3: 2.37 ms per loop
125 loops, best of 3: 2.23 ms per loop
125 loops, best of 3: 2.34 ms per loop
125 loops, best of 3: 2.2 ms per loop
}}}
* With no patch applied ::
{{{
#!python
for i in range(10):
g = graphs.RandomGNP(50,.3)
timeit("g.min_spanning_tree()")
125 loops, best of 3: 3.33 ms per loop
125 loops, best of 3: 2.96 ms per loop
125 loops, best of 3: 3.21 ms per loop
125 loops, best of 3: 3.32 ms per loop
125 loops, best of 3: 2.8 ms per loop
125 loops, best of 3: 3.06 ms per loop
125 loops, best of 3: 3.03 ms per loop
125 loops, best of 3: 3.13 ms per loop
125 loops, best of 3: 3.4 ms per loop
125 loops, best of 3: 3.5 ms per loop
}}}
Calling ``to_undirected()`` ::
{{{
#!python
for i in range(10):
g = graphs.RandomGNP(50,.3)
timeit("g.to_undirected()")
125 loops, best of 3: 4.43 ms per loop
125 loops, best of 3: 4.56 ms per loop
125 loops, best of 3: 4.88 ms per loop
125 loops, best of 3: 4.59 ms per loop
125 loops, best of 3: 4.92 ms per loop
125 loops, best of 3: 4.54 ms per loop
125 loops, best of 3: 4.57 ms per loop
125 loops, best of 3: 4.25 ms per loop
125 loops, best of 3: 4.69 ms per loop
125 loops, best of 3: 4.63 ms per loop
}}}
Calling ``is_connected()``::
{{{
#!python
for i in range(10):
g = graphs.RandomGNP(50,.3)
timeit("g.is_connected()")
625 loops, best of 3: 153 µs per loop
625 loops, best of 3: 154 µs per loop
625 loops, best of 3: 157 µs per loop
625 loops, best of 3: 152 µs per loop
625 loops, best of 3: 150 µs per loop
625 loops, best of 3: 149 µs per loop
625 loops, best of 3: 149 µs per loop
625 loops, best of 3: 153 µs per loop
625 loops, best of 3: 153 µs per loop
625 loops, best of 3: 155 µs per loop
}}}
So in general the default behaviour leads to a much slower performance,
even though disabling the checkings makes it better than the current
implementation. I think most of it is because of the time required to copy
the graph (checking the connectivity is comparatively *much* faster). I
tried to find some cheap trick to avoid the checking, at least when the
graph is simple and unweighted. Actually, I rewrote a computation of
spanning trees based on depth-first search, but I wasn't able to do better
than what your code does when the checkings are disabled, so it's not
useful by itself. I think the best way is to find a way around graph
copies, but no cheap tricks so far `^^;`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10433#comment:11>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
