Re: [pygame] Iterate over list and delete

[Irv Kalb <Irv@xxxxxxxxxxxxxx>]

A very big thank you to everyone who responded to this question!

I ran a test in my program and found that I had overestimated the number of elements in my list.  It turns out that I typically have under 50, so it looks like performance is not an issue in this case.  

I really like Tyler's solution, even though it's the slowest of the ones proposed.  I knew there was a way to o the reversing through the list, but I had forgotten about "reversed".   While I really like the other algorithms, I'm sure that this one will be easiest for my students to understand.

In my curriculum, I will probably add in a good discussion of what is really going on here, and possibly discuss other ways of solving this problem with more time efficient (but potentially more difficult to follow) algorithms.  In fact, this sounds like a very good homework problem ... thanks!

Special thanks to Ian for providing algorithmic timing results.  Very informative.

Irv  

On May 20, 2018, at 4:55 PM, Irv Kalb <Irv@xxxxxxxxxxxxxx> wrote:

Thanks very much.

Is there a way to do that without the list comprehension? I'm building this as part of a class, and I will not have talked about list comprehensions up until that point.

Thanks,

Irv

On May 20, 2018, at 2:35 PM, Daniel Foerster <pydsigner@xxxxxxxxx> wrote:

I think what you're looking for is this:

my_list = [x for x in my_list if not need_to_delete(x)]

On Sun, May 20, 2018, 16:28 Irv Kalb <Irv@xxxxxxxxxxxxxx> wrote:

I am building a game where I am keeping track of many objects in a list (let's just call it "myList".  In every "frame" of my game I need to see if any objects need to be removed from myList.

I know that this code:

for item in myList:
    if needsToBeDeleted(item):
         myList.remove(item)

does not work correctly because it affects the order of list while I am iterating over it.  (Specifically, if there are two elements in a row that should be removed, the first one is removed, but the second one is skipped over.)

I have looked at many different solutions, and have found a number of different approaches, but none them seem elegant.  Here are ones that work:

1)  Build a list of indices in reverse order (  [n - 1, n -2, n - 3, ... 0] )
     Iterate over this list
          if the element at that index needs to be deleted,
                pop the element at this index

    (untested, but should work)

     indexList = list(range(0, n - 1))
     indexList.reverse()

     for index in indexList:
          if needsToBeDeleted(myList[index]):
                myList.pop(index)

    I believe this will work, but it looks very clunky.


2)  Create a tempList that starts off empty.
     Iterate through my original list.
        If an element does NOT need to be deleted, append it to the tempList. 
     Reassign the myList to the tempList
     Set the tempList to None (or delete it)

     tempList = []
     for item in myList:
         if not needsToBeDeleted(item):
             tempList.append(item)
      myList = tempList
      tempList = None

     Seems OK, but again, seems like kind of a kludge.

3)  Iterate through a copy of the list:

     for item in myList[:]:
         if needsToBeDeleted(item):
             myList.remove(item)

      This does work, but I would guess it might be slow for long lists (since it first has to duplicate a list, then when it wants to delete an element, 'remove' must search through the list to find the matching element before deleting it).  Also, it would be tricky to explain to students, because I am iterating through a copy of a list, but deleting elements from the original list.


Does anyone have an easier, more clear, reusable approach?

If not, any thoughts on which of these three approach would be most efficient and clear?  I don't have a favorite yet.

Thanks,

Irv