timing puzzle

Robin Becker robin at reportlab.com
Fri Nov 16 19:42:46 CET 2007

I'm trying to get my head round a timing puzzle I find whilst optimizing A 
Kuchling's version of the Knuth line splitting algorithm from the oedipus 
project. The puzzle is as follows in highly abstract form (here
  active_nodes is a list of objects kept in a sorted order, but there are no 
special methods on the objects for comparison etc)

    for i in xrange(m):
        for A in active_nodes[:]:
           if cond:

is slow my test takes 2.7 seconds; profiling reveals we're calling A.remove 
thousands of times and it's taking a lot of time. There appear to be no other 
usages of active_nodes in the for A loop.

On a hunch I changed the above to

     removed = []
     aremoved = removed.append
     for i in xrange(m):
        for iA,A in enumerate(active_nodes):
           if cond:
        if removed:
            for iA in reversed(removed):
                del active_nodes[iA]
                del removed[:]

this latter is 5 times faster, but I can't really see why. My only guess is that 
  appending to the removed list is relatively easy compared with deletes and the 
reverse order delete is somehow moving less data about. I think in the original 
Knuth the deletion would have been from some real kind of list and O(1) whereas 
here deletions are O(n/2) on average. On the other hand we have to keep this 
list in sorted order. What data structure should I be using? I should add that I 
tried using a __cmp__ method to assist in doing the sorted insert, but that 
interfered with the simple active_nodes.remove.
Robin Becker

More information about the Python-list mailing list