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.
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.