Having trouble deleting objects from a list...

[KraftDiner]

I have a list, and within it, objects are marked for deletion.
However when I iterate through the list to remove objects
not all the marked objects are deleted..
here is a code portion:

i = 0
for obj in self.objList:
if obj.mouseHit:
print 'delete + ' + `i`
self.objList.pop(i)
flag = True
else:
i = i + 1
print `i`

I can't see what I'm doing wrong!
It seems like the last selected object is the one that is not
deleted...

 

[Jason Stitt]

I have a list, and within it, objects are marked for deletion.
However when I iterate through the list to remove objects
not all the marked objects are deleted..
here is a code portion:

i = 0
for obj in self.objList:
if obj.mouseHit:
print 'delete + ' + `i`
self.objList.pop(i)
flag = True
else:
i = i + 1
print `i`

You're mixing two different ways of looping, and they're getting out
of sync.

'for obj in self.objList' will keep right on iterating through the
list even if you don't increment i.

A direct adaptation of your code that should work is:

i = 0
while i < len(self.objList):
if self.objList.mouseHit:
self.objList.pop(i)
flag = True
else:
i += 1

Or, shorter and a bit more Pythonic, but not in-place:

newObjList = [obj for obj in self.objList if not obj.mouseHit]
flag = (len(newObjList) != len(self.objList))
self.objList = newObjList

I don't know how the performance of the two would compare. The second
involves creating a new list, but Python is supposed to optimize the
heck out of list comprehension, and removing items from a list in
place isn't free, either.

Jason

 

[Mike Meyer]

On Oct 19, 2005, at 8:16 PM, KraftDiner wrote:
'for obj in self.objList' will keep right on iterating through the
list even if you don't increment i.

And if you modify self.objList while you're iterating over it, the
results are undefined.

A direct adaptation of your code that should work is:

i = 0
while i < len(self.objList):
if self.objList.mouseHit:
self.objList.pop(i)
flag = True
else:
i += 1

You probably want "del self.objList" instead of
"self.objList.pop(i)". That saves a method lookup and the return of a
value you're just going to throw away.

Or, shorter and a bit more Pythonic, but not in-place:

newObjList = [obj for obj in self.objList if not obj.mouseHit]
flag = (len(newObjList) != len(self.objList))
self.objList = newObjList

I don't know how the performance of the two would compare. The second
involves creating a new list, but Python is supposed to optimize the
heck out of list comprehension, and removing items from a list in
place isn't free, either.

Deleting an element from an arbitrary point in a CPython list of
length n is O(n). So deleting m items from an n-element list is
O(n*m). Building the new list will be O(n) no matter how many
elements you delete. Unless space is really tight, you probably want
to build a new list.

If you do have to do the delete in place, you'll improve things by
scanning the list from the end towards the beginnings. That makes the
worst-case behavior go from O(n^2) to O(n), because you no longer have
to move any elements after you delete one.

i = len(self.objList) - 1
while i >= 0:
if self.objList.mouseHit:
del self.objList
flag = True
i -= 1

<mike