I have a list L.
I can delete element i by doing:
del L[i]
But what if I have a set of non contiguous indexes to delete?
I=set([i1, i2, i3,...])
Doing:
for i in I:
del L[i]
Won't work.
Any ideas?
views:
466answers:
3
+4
A:
for i in I:
del L[i]
won't work, because (depending on the order) you may invalidate the iterator -- this will usually show up as some items which you intended to delete remaining in the list.
It's always safe to delete items from the list in the reverse order of their indices. The easiest way to do this is with sorted():
for i in sorted(I, reverse=True):
del L[i]
dcrosta
2009-09-20 02:25:05
That's a great idea. :DI'm not sure if reversed(list(I)) is correct? But I get the idea: sort the indexes in I in reverse order and THEN delete.
Ezequiel
2009-09-20 02:28:04
you need the list() since you cannot call reversed() directly on a set.
dcrosta
2009-09-20 02:29:23
ack, that was silly! i didn't mean reversed(list(...)), i meant sorted(..., reverse=True)
dcrosta
2009-09-20 02:30:58
I get that, but list(I) has no particular order, or am I wrong?wouldn't it be reversed(list(I).sorted())? or list(I).sorted(reverse=True) ?
Ezequiel
2009-09-20 02:33:23
Gotcha ;) Thank you for your answer
Ezequiel
2009-09-20 02:34:10
This is effectively `O(n^2)` (actually `O(n*m)`, I suppose, on the size of each list), because each del has to copy the entire contents of the list from that point on for each deletion. Paul's solution is probably more like O(m log n), and it's just as easy.
Glenn Maynard
2009-09-20 07:31:23
My timing test shows that building a new list is O(n), while the deletion of elements is O(n^2), for exactly the reason stated by Glenn.
Paul McGuire
2009-09-20 10:30:27
+10
A:
Eine Minuten bitte, Ich hap eine kleine Problemo avec diese Religione. -- Eddie Izzard (doing his impression of Martin Luther)
Deleting by reverse-iterating over a list to preserve the iterator is a common solution to this problem. But another solution is to change this into a different problem. Instead of deleting items from the list using some criteria (in your case, the index exists in a list of indexes to be deleted), create a new list that leaves out the offending items.
L[:] = [ item for i,item in enumerate(L) if i not in I ]
For that matter, where did you come up with the indexes in I in the first place? You could combine the logic of getting the indexes to be removed and building the new list. Assuming this is a list of objects and you only want to keep those that pass an isValid test:
L[:] = [ item for item in L if item.isValid() ]
This is much more straightforward than:
I = set()
for i in range(len(L)):
if not L[i].isValid():
I.add(i)
for i in sorted(I, reverse=True):
del L[i]
For the most part, I turn any question about "how to delete from a list the items that I don't want" into "how to create a new list containing just the items I want".
EDITED: changed "L = ..." to "L[:] = ..." per Alex Martelli's answer to this question.
Paul McGuire
2009-09-20 03:04:55
It turns out this does better the longer the lists get. See this test code: http://pastebin.com/f5bf9e3e8.
Paul McGuire
2009-09-20 04:25:17
This is the way to do this; note that "I" should be a set, not a list.
Glenn Maynard
2009-09-20 07:24:53
@Glenn: ??? `I` *is* a set. And which approach do you mean by "this"? The list comp approach or the explicit deletion approach? If you mean the list comp approach, then there is no `I`, set or not.
Paul McGuire
2009-09-20 10:15:37
`I` should be a set even in the first example, so that the total lookup time is `O(n)`
kaizer.se
2009-09-20 14:32:20
@kaizer.se: Am I missing something? Is `I` not a set in the first example? It is not explicitly defined in my answer, so I assumed one would look up at the OP's question, and behold, `I` is defined as a set there too.
Paul McGuire
2009-09-20 17:00:05
A:
If your original list data can safely be turned into a set (i.e. all unique values and doesn't need to maintain order), you could also use set operations:
Lset = set(L)
newset = Lset.difference(I)
You could also maybe do something with a Bag/Multiset, though it probably isn't worth the effort. Paul McGuire's second listcomp solution is certainly best for most cases.
Kevin Horn
2009-09-21 16:28:16