66

I tried this code to remove items from a list:

x = ["ok", "jj", "uy", "poooo", "fren"]
for item in x:
    if len(item) != 2:
        x.remove(item)

Why isn't "fren" removed from x?

Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
alwbtc
  • 28,057
  • 62
  • 134
  • 188

5 Answers5

110

You can't remove items from a list while iterating over it. It's much easier to build a new list based on the old one:

y = [s for s in x if len(s) == 2]
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
  • Well, to nitpick: You "can", but you'll get useless results and other containers outright disallow it. –  Nov 29 '11 at 14:58
  • 2
    @delnan: Well, to nitpick even more, you *can* and even get useful results if you iterate over the list in reverse order. But this is probably not faster (and definitely much more confusing) than just creating a new list as Sven suggested. – Tim Pietzcker Nov 30 '11 at 08:23
  • Yeah I do it in reverse order, works without copying: x = len(system_list) # remove all null entries for i in range(x-1, -1, -1): if not system_list[i]: del system_list[i] – radtek Mar 04 '14 at 18:46
  • @radtek: Since removing an item from a list is an O(n) operation, that approach has O(n²) worst-case complexity. – Sven Marnach Mar 04 '14 at 18:59
  • this answer is perfectly working. – xaratustra May 04 '21 at 13:33
49

hymloth and sven's answers work, but they do not modify the list (the create a new one). If you need the object modification you need to assign to a slice:

x[:] = [value for value in x if len(value)==2]

However, for large lists in which you need to remove few elements, this is memory consuming, but it runs in O(n).

glglgl's answer suffers from O(n²) complexity, because list.remove is O(n).

Depending on the structure of your data, you may prefer noting the indexes of the elements to remove and using the del keywork to remove by index:

to_remove = [i for i, val in enumerate(x) if len(val)==2]
for index in reversed(to_remove): # start at the end to avoid recomputing offsets
    del x[index]

Now del x[i] is also O(n) because you need to copy all elements after index i (a list is a vector), so you'll need to test this against your data. Still this should be faster than using remove because you don't pay for the cost of the search step of remove, and the copy step cost is the same in both cases.

[edit] Very nice in-place, O(n) version with limited memory requirements, courtesy of @Sven Marnach. It uses itertools.compress which was introduced in python 2.7:

from itertools import compress

selectors = (len(s) == 2 for s in x)
for i, s in enumerate(compress(x, selectors)): # enumerate elements of length 2
    x[i] = s # move found element to beginning of the list, without resizing
del x[i+1:]  # trim the end of the list
Community
  • 1
  • 1
gurney alex
  • 13,247
  • 4
  • 43
  • 57
  • 3
    Here's an in-place O(n) version that only needs O(1) additional memory: http://ideone.com/F10fB. It isn't any more complex than your O(n^2) version. (+1 for a detailed answer, btw) – Sven Marnach Nov 29 '11 at 15:26
  • nice one. You should post it as an answer on SO. – gurney alex Nov 29 '11 at 15:52
  • Why would you assign to `x[:]` instead of just `x`? – Kirk Strauser Nov 29 '11 at 15:56
  • The code doesn't really fit in my answer, but it fits well in the discussion in *your* answer. Care to integrate it? (Note that `itertools.compress()` was introduced in Python 2.7.) – Sven Marnach Nov 29 '11 at 16:03
  • @KirkStrauser: To change the semantics to in-place manipulation. see also http://stackoverflow.com/a/1208792/279627 – Sven Marnach Nov 29 '11 at 16:04
  • @SvenMarnach OK, so that'd be good for when there are multiple references to `x` (such as the caller of the function we're working with here), right? But in the short term, isn't it still building a second copy of the list in memory then assigning it in-place to `x[:]`, then collecting the old now-unreferenced list? – Kirk Strauser Nov 29 '11 at 16:45
  • @KirkStrauser: Of course, that's the very reason for my first comment to this post. – Sven Marnach Nov 29 '11 at 16:55
  • @SvenMarnach That's what I thought. I think we meant different things by "in-place", and I wanted to make sure Python wasn't using some advanced optimization I didn't know about. Thanks! – Kirk Strauser Nov 29 '11 at 17:02
  • @KirkStrauser: You might be interested in [this post](http://stackoverflow.com/questions/4948293/python-slice-assignment-memory-usage/4948508#4948508) for more details. – Sven Marnach Nov 29 '11 at 17:05
  • @gurneyalex Thanks for showing the usage of slice x[:] to avoid creation of a new object! I came here looking only for that. – Ethan Sep 06 '15 at 17:03
7
x = [i for i in x if len(i)==2]
hymloth
  • 6,869
  • 5
  • 36
  • 47
2

This stems from the fact that on deletion, the iteration skips one element as it semms only to work on the index.

Workaround could be:

x = ["ok", "jj", "uy", "poooo", "fren"]
for item in x[:]: # make a copy of x
    if len(item) != 2:
        print "length of %s is: %s" %(item, len(item))
        x.remove(item)
glglgl
  • 89,107
  • 13
  • 149
  • 217
  • hmm... you are right. So in terms of time, hymloth's and your solutions seem to be the best AFAICT... – glglgl Nov 29 '11 at 15:22
2

The already-mentioned list comprehension approach is probably your best bet. But if you absolutely want to do it in-place (for example if x is really large), here's one way:

x = ["ok", "jj", "uy", "poooo", "fren"]
index=0
while index < len(x):
    if len(x[index]) != 2:
        print "length of %s is: %s" %(x[index], len(x[index]))
        del x[index]
        continue
    index+=1
Austin Marshall
  • 2,991
  • 16
  • 14