17

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?

Ezequiel
  • 668
  • 2
  • 9
  • 25

5 Answers5

32

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.

Community
  • 1
  • 1
PaulMcG
  • 62,419
  • 16
  • 94
  • 130
  • How well does that scale to large lists? – jmucchiello Sep 20 '09 at 03:17
  • 1
    It turns out this does better the longer the lists get. See this test code: http://pastebin.com/f5bf9e3e8. – PaulMcG Sep 20 '09 at 04:25
  • This is the way to do this; note that "I" should be a set, not a list. – Glenn Maynard Sep 20 '09 at 07:24
  • @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. – PaulMcG Sep 20 '09 at 10:15
  • `I` should be a set even in the first example, so that the total lookup time is `O(n)` – u0b34a0f6ae Sep 20 '09 at 14:32
  • @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. – PaulMcG Sep 20 '09 at 17:00
  • +1 for the second code solution with `item.isValid()`. BTW, if you already have a set of indices, it is not necessary to use enumerate to create tuples, as in the first code solution. I prefer `[ L[i] for i in xrange(len(L)) if i not in I ]`. For a complete example of doing so, see http://stackoverflow.com/a/20589125/199364. At that link, I also show a related solution, if you have a list of values to be removed, rather than the indices. – ToolmakerSteve Dec 14 '13 at 23:40
9
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
  • 26,009
  • 8
  • 71
  • 83
  • That's a great idea. :D I'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 Sep 20 '09 at 02:28
  • you need the list() since you cannot call reversed() directly on a set. – dcrosta Sep 20 '09 at 02:29
  • ack, that was silly! i didn't mean reversed(list(...)), i meant sorted(..., reverse=True) – dcrosta Sep 20 '09 at 02:30
  • 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 Sep 20 '09 at 02:33
  • 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 Sep 20 '09 at 07:31
  • 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. – PaulMcG Sep 20 '09 at 10:30
4

You can use numpy.delete as follows:

import numpy as np
a = ['a', 'l', 3.14, 42, 'u']
I = [1, 3, 4]
np.delete(a, I).tolist()
# Returns: ['a', '3.14']

If you don't mind ending up with a numpy array at the end, you can leave out the .tolist(). You should see some pretty major speed improvements, too, making this a more scalable solution. I haven't benchmarked it, but numpy operations are compiled code written in either C or Fortran.

philE
  • 1,655
  • 15
  • 20
1

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
  • 4,167
  • 28
  • 30
0
L = [ item for item in L if L.index(item) not in I ]
cherish
  • 1,370
  • 1
  • 11
  • 16