Removal of element from list while traversing causes the nextelement to be skipped

[William McBrine]

Look at this -- from Python 2.5.1:

a = [1, 2, 3, 4, 5]
for x in a:

.... if x == 3:
.... a.remove(x)
.... print x
....
1
2
3
5

a [1, 2, 4, 5]

Sure, the resulting list is correct. But 4 is never printed during the
loop!

What I was really trying to do was this:

apps = [name for name in os.listdir(ROOT) if
os.path.isdir(os.path.join(ROOT, name))]

apptitles = {}

for name in apps:
try:
app = __import__(name)
except:
apps.remove(name)
else:
apptitles[name] = getattr(app, 'TITLE', name.title())

which worked fine, until I actually had a directory with no module in it.
Then that directory was correctly removed from the list, but the _next_
one was skipped, so its title was never assigned, which caused problems
later in the program.

 

[Berteun Damman]

Look at this -- from Python 2.5.1:

a = [1, 2, 3, 4, 5]
for x in a:

... if x == 3:
... a.remove(x)
... print x
...
1
2
3
5[1, 2, 4, 5]

You have to iterate over a copy of 'a', so for x in a[:]. Modifying a
list while iterating over is a recipe for problems. (As it is in many
other programming languages.)

Berteun

 

[imageguy]

Look at this -- from Python 2.5.1:

a = [1, 2, 3, 4, 5]
for x in a:

...     if x == 3:
...         a.remove(x)
...     print x
...
1
2
3
5
[1, 2, 4, 5]

Sure, the resulting list is correct. But 4 is never printed during the
loop!

What I was really trying to do was this:

apps = [name for name in os.listdir(ROOT) if
        os.path.isdir(os.path.join(ROOT, name))]

apptitles = {}

for name in apps:
    try:
        app = __import__(name)
    except:
        apps.remove(name)
    else:
        apptitles[name] = getattr(app, 'TITLE', name.title())

which worked fine, until I actually had a directory with no module in it.
Then that directory was correctly removed from the list, but the _next_
one was skipped, so its title was never assigned, which caused problems
later in the program.

You should not change/modify the original sequence iterating over.
In the list comprehension, try changing os.listdir(ROOT) to
os.listdir(ROOT)[:] so you are get a copy of the original list.

geoff.

 

[attn.steven.kuo]

Look at this -- from Python 2.5.1:

a = [1, 2, 3, 4, 5]
for x in a:

... if x == 3:
... a.remove(x)
... print x
...
1
2
3
5
[1, 2, 4, 5]

Sure, the resulting list is correct. But 4 is never printed during the
loop!

(snipped)


If you're going to delete elements from
a list while iterating over it, then do
it in reverse order:

a = [ 98, 99, 100 ]
last_idx = len(a) - 1
for i, x in enumerate(a[::-1]):

.... if x == 99: del(a[last_idx - i])
.... print x
....
100
99
98[98, 100]

 

[Berteun Damman]

If you're going to delete elements from
a list while iterating over it, then do
it in reverse order:

Why so hard? Reversing it that way creates a copy, so you might as
well do:

a = [ 98, 99, 100 ]
for i, x in enumerate(a[:]):

... if x == 99: del(a)
... print x

Berteun

 

[Santiago Romero]

Look at this -- from Python 2.5.1:

a = [1, 2, 3, 4, 5]
for x in a:

... if x == 3:
... a.remove(x)
... print x

Well ... you could use:
.... print a
.... if a == 3: del a
....
5
4
3
2
1[1, 2, 4, 5]


Bye.

 

[Duncan Booth]

If you're going to delete elements from
a list while iterating over it, then do
it in reverse order:

Why so hard? Reversing it that way creates a copy, so you might as
well do:

a = [ 98, 99, 100 ]
for i, x in enumerate(a[:]):

... if x == 99: del(a)
... print x

Why so hard?

a = [ 98, 99, 100, 98, 99, 100 ]
for i, x in enumerate(a[:]):

if x == 99: del(a)

[98, 100, 98, 99]

oops! But:

a = [ 98, 99, 100, 98, 99, 100 ]
last_idx = len(a) - 1
for i, x in enumerate(a[::-1]):

if x == 99: del(a[last_idx - i])

[98, 100, 98, 100]

Reversing it works. Your code doesn't.

 

[Paul Hankin]

Look at this -- from Python 2.5.1:

a = [1, 2, 3, 4, 5]
for x in a:

...     if x == 3:
...         a.remove(x)
...     print x
...
1
2
3
5
[1, 2, 4, 5]

Sure, the resulting list is correct. But 4 is never printed during the
loop!

What I was really trying to do was this:

apps = [name for name in os.listdir(ROOT) if
        os.path.isdir(os.path.join(ROOT, name))]

apptitles = {}

for name in apps:
    try:
        app = __import__(name)
    except:
        apps.remove(name)
    else:
        apptitles[name] = getattr(app, 'TITLE', name.title())

which worked fine, until I actually had a directory with no module in it.
Then that directory was correctly removed from the list, but the _next_
one was skipped, so its title was never assigned, which caused problems
later in the program.

How about...
for name in apps:
try:
app == __import__(name)
apptitles[name] = getattr(app, 'TITLE', name.title())
except ImportError:
pass

# Remove apps with no title, ie those that didn't import.
apps = [name for name in apps if apptitles.get(name)]

Alternatives for the last line would be 'apps = filter(apptitles.get,
apps)'
or 'apps = apptitles.keys()'.

 

[Paul Hankin]

Why so hard? Reversing it that way creates a copy, so you might as
well do:

a = [ 98, 99, 100 ]
for i, x in enumerate(a[:]):

 ...     if x == 99: del(a)
 ...     print x

Why so hard?

a = [ 98, 99, 100, 98, 99, 100 ]
for i, x in enumerate(a[:]):

        if x == 99: del(a)

Why so hard?

a = [x for x in a if x != 99]

OK, so this doesn't modify a in place.. but how often do you really
need to do that?

If I really had to modify it in place (and the condition wasn't really
x == 99), how about:
bad_indices = [i for i, x in enumerate(a) if x == 99]
for bad_index in reversed(bad_indices):
del a[bad_index]

 

[Joe Riopel]

If you're going to delete elements from
a list while iterating over it, then do
it in reverse order:

how about

li = [1,2,3,4,5]
filter(lambda x: x != 3, li) [1, 2, 4, 5]

 

[Santiago Romero]

how about

li = [1,2,3,4,5]
filter(lambda x: x != 3, li)

[1, 2, 4, 5]

I haven't measured it, but this should be the fast solution in all
the thread ...

 

[Paul Rubin]

li = [1,2,3,4,5]
filter(lambda x: x != 3, li)

[1, 2, 4, 5]

I haven't measured it, but this should be the fast solution in all
the thread ...

li.remove(3) is probably faster.

 

[Santiago Romero]

li = [1,2,3,4,5]
filter(lambda x: x != 3, li)
[1, 2, 4, 5]

I haven't measured it, but this should be the fast solution in all
the thread ...

li.remove(3) is probably faster.

But that only removes the first ocurrence of item==3.

In a = [1, 2, 3, 3, 3, 4, 3, 3, 2, 3], the filter solution will
efectively remove all items with value == 3 while li.remove(3) will
only remove the first ocurrence.

Bye!

 

[cokofreedom]

li = [1,2,3,4,5]
filter(lambda x: x != 3, li)
[1, 2, 4, 5]
I haven't measured it, but this should be the fast solution in all
the thread ...

li.remove(3) is probably faster.

But that only removes the first ocurrence of item==3.

In a = [1, 2, 3, 3, 3, 4, 3, 3, 2, 3], the filter solution will
efectively remove all items with value == 3 while li.remove(3) will
only remove the first ocurrence.

Bye!

from itertools import ifilter
print [x for x in ifilter(lambda x: x != 99, li)]

Will this one be faster or slower than filter?

 

[Paul Rubin]

In a = [1, 2, 3, 3, 3, 4, 3, 3, 2, 3], the filter solution will
efectively remove all items with value == 3 while li.remove(3) will
only remove the first ocurrence.

Hmm, interesting, I didn't realize that (shoulda checked the docs).
Thanks!

 

[Arnaud Delobelle]

If I really had to modify it in place (and the condition wasn't really
x == 99), how about:
bad_indices = [i for i, x in enumerate(a) if x == 99]
for bad_index in reversed(bad_indices):
    del a[bad_index]

Or one could use the trick of counting from the right (untested):

n = len(a)
for i, x in enumerate(a):
if x == 99: del a[i-n]

 

[Neil Cerutti]

Or one could use the trick of counting from the right (untested):

n = len(a)
for i, x in enumerate(a):
if x == 99: del a[i-n]

Or one can put on his bellbottoms, horn-rimmed glasses, and wear a mullet:

i = 0
while i < len(a):
if a == 99:
del a
else:
i += 1

 

[bearophileHUGS]

If you don't want to reinvent the wheel all the time you can use this
one:

def inplacefilter(pred, alist):
"""inplacefilter(pred, alist): filters the given list like
filter(),
but works inplace, minimizing the used memory. It returns None.

>>> pr = lambda x: x > 2
>>> l = []
>>> inplacefilter(pr, l)
>>> l []
>>> l = [1,2,2]
>>> inplacefilter(pr, l)
>>> l []
>>> l = [3]
>>> inplacefilter(pr, l)
>>> l [3]
>>> l = [1,2,3,1,5,1,6,0]
>>> r = filter(pr, l) # normal filter
>>> r [3, 5, 6]
>>> inplacefilter(pr, l)
>>> r == l

True
"""
slow = 0
for fast, item in enumerate(alist):
if pred(item):
if slow != fast:
alist[slow] = alist[fast]
slow += 1
del alist[slow:]


If you use Psyco you can replace the enumerate() with a manually
incremented counter to speed up the code a bit, like this (untested):

def inplacefilter(pred, alist):
slow = 0
fast = 0
for item in alist:
if pred(item):
if slow != fast:
alist[slow] = alist[fast]
slow += 1
fast += 1
del alist[slow:]

Bye,
bearophile

 

[Paul Rubin]

Or one can put on his bellbottoms, horn-rimmed glasses, and wear a mullet:

i = 0
while i < len(a):
if a == 99:
del a
else:
i += 1

Quadratic time!! Yowch!! Back to the future:

def rocket_science(xs):
for x in xs:
if x != 99:
yield x

a[:] = list(rocket_science(a))

;-)

 

[Arnaud Delobelle]

n = len(a)
for i, x in enumerate(a):
    if x == 99: del a[i-n]

Oops. That can't work. Don't know what I was thinking here. I
probably did had one mental refactoring too many...