[MERGE] faster topo_sort

[Robert Collins]

On Fri, 2006-02-24 at 11:23 +1100, Andrew Bennetts wrote:
> Robert Collins wrote:
> [...]
> > 
> > topo_sort takes 4 seconds of wall time to sort the bzr graph.
> > the one in reconcile I haven't got an accurate time yet, I don't know
> > the python trick offhand to time a method - but its fast enough I can't
> > even count to '1 mississipi' before that phase completes.
> 
> The trick is the timeit module.
> 
> At the command line:
> 
>     python -m timeit -s "setup" -s "more setup" "statement to time"
> 
> e.g.:
> 
>     python -m timeit -s "from bzrlib.weavefile import read_weave" "read_weave(open('.bzr/inventory.weave'))"
> 
> You can also import timeit and use it in code directly, but I find that's a bit
> awkward.

EWWW.

I used a more primitive approach after putting the new sort in a
function of its own:
        import time;
        from tsort import topo_sort
        start = time.clock()
        self._work_queue = topological_sort(self._rev_graph.items())
        fasttime = time.clock() - start
        start = time.clock()
        topo_sort(self._rev_graph.items())
        slowtime = time.clock() - start
        self.pb.note('times: %d, %d' % (fasttime, slowtime))

Looping that 5 times gives the following output:
times: 0, 2
times: 0, 2
times: 0, 2
times: 0, 2
times: 0, 2

i.e. unmeasurable and 2 seconds.


So - really - I'd like to replace the current topo_sort routine with
this one. 

Rob



-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 191 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20060225/9428f92e/attachment.pgp