Code review comment for lp:~mkbosmans/bzr/topo_sort

Revision history for this message
Maarten Bosmans (mkbosmans) wrote :

The last commit 4582 adds the foo_append improvement.
Also instead of toying with pointer to list items to be popped, etc., I used collections.deque, which is a double-linked list, so that data structure captures your suggested optimization for the list used as stack nicely. It depends on Python 2.4, I hope that's OK for bzr.
To make the algorithm more clear, I added a comment about ghost parents and renamed some of the variables.

These are my new timings (not to be compared with any times posted elsewhere)

r4579 1.41 improved TopoSorted.sorted()
r4580 1.05 new algorithm topo_sort()
r4582 0.93 foo_append, etc.
       0.89 use deque

So this is a nice 15% further improvement for the new algorithm.

« Back to merge proposal