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:
active_nodes.remove(A)
......
.....
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:
aremoved(iA)
......
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
--
http://mail.python.org/mailman/listinfo/python-list
