Having trouble deleting objects from a list...

[Mike Meyer]

Jason Stitt <jason at pengale.com> writes:
> 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[i].mouseHit:
>          self.objList.pop(i)
>          flag = True
>      else:
>          i += 1

You probably want "del self.objList[i]" 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[i].mouseHit:
      del self.objList[i]
      flag = True
   i -= 1

   <mike
-- 
Mike Meyer <mwm at mired.org>			http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.