How to del item of a list in loop?

[Fredrik Lundh]

(if you have 2.4, try replacing [] with () and see what happens)

The result is a generator with a name ("lst") that's rather misleading
in the context.

according to my dictionary, the word "list" means "A series of names, words,
or other items written, printed, or imagined one after the other". I'd say that
matches both list objects and iterators pretty well.

but alright, you can change the name to "seq" if you want.

Achieving the same result as the list comprehension, by doing lst = list(i for

.... etc etc), appears to be slower.

the original post didn't contain a complete use case; a generator is a perfect
replacement for a list in many cases. I'm sure most comp.lang.python readers
are smart enough to understand when and why.

</F>

 

[Nick Coghlan]

The effbot's version is still going to be faster though:
lst = [x for x in lst if x != 2]

Have you measured this?

Nope. I'm going purely on the fact that it is O(n), and the in-place
modification will always be worse than that.

Cheers,
Nick.

 

[Michael Hoffman]

I've taken your code and improved it along the
suggested lines, added timing for first, middle, and last elements,
added several more methods, and added a testing facility as well. Would
you like a copy?

Actually I think it would be great if you posted it here for our
combined edification. I would have been considerably less annoyed if you
had done that and explained why it is better rather than nitpicking my
version.

 

[John Machin]

Actually I think it would be great if you posted it here for our
combined edification.

import timeit, sys

# Requirement for func(lst, x):
# From list "lst", remove all objects whose value == "x"
# Note: in-situ deletion is required.
# Return None

duds = set(('method_while', 'method_coghlan'))

def method_copy(lst, x):
for obj in lst[:]:
if obj == x:
lst.remove(x)

def method_listcomp(lst, x):
lst[:] = [obj for obj in lst if obj != x]

def method_genexpr(lst, x):
lst[:] = (obj for obj in lst if obj != x)

def method_while(lst, x):
i = 0
while i < len(lst):
if lst == x:
lst.remove(i) # bug: s/b lst.remove(x)
else:
i += 1

def method_while2(lst, x):
inx = 0
while inx < len(lst):
if lst[inx] == x:
lst.remove(x)
else:
inx += 1

def method_while3(lst, x):
inx = 0
n = len(lst)
while inx < n:
if lst[inx] == x:
lst.remove(x)
n -= 1
else:
inx += 1

def method_del(lst, x):
inx = 0
n = len(lst)
while inx < n:
if lst[inx] == x:
del lst[inx]
n -= 1
else:
inx += 1

def method_del_bkwds(lst, x): O(LR)
for inx in xrange(len(lst) - 1, -1, -1):
if lst[inx] == x:
del lst[inx]

def method_coghlan(lst, x):
for i, obj in enumerate(reversed(lst)):
if obj == x:
del lst[-i] # bug: should be lst[-i-1]

def method_coghlan2(lst, x): # O(LR)
for i, obj in enumerate(reversed(lst)):
if obj == x:
del lst[-i-1]

def method_try_remove(lst, x): # O(LR)
try:
while 1:
lst.remove(x)
except:
pass

def method_richter(lst, x): # O(L)
i = 0
for item in lst:
if item != x:
lst = item
i += 1
del lst[i:]

lsts = dict(ten=range(10),
hundred=range(100),
thousand=range(1000),
tenk=range(10000),
hundredk=range(100000),
million=range(1000000))

def main(action, meths):
if not action:
usage()
action = action[0]
all_method_names = [x for x in globals() if
x.startswith("method_")]
all_method_names.sort()
if not meths:
method_names = all_method_names
else:
method_names = ["method_" + x for x in meths]
input = set(method_names)
all = set(all_method_names)
wrong = input - (all & input)
if wrong:
print "***Bzzzzt", wrong
sys.exit(1)
if action == "time":
do_timing(method_names)
elif action == "test":
do_tests(method_names)
else:
usage()

def do_timing(method_names):
list_names = [(len(lst), name) for name, lst in lsts.iteritems()]
list_names.sort() # in size order
list_names = [x[1] for x in list_names]
for lst_name in list_names:
orig_list = lsts[lst_name]
lst = orig_list[:] # make a fresh copy of the list!
for method_name in method_names:
if method_name in duds: continue
for inx in [0, len(lst) // 2, -1]:
delarg = str(lst[inx])
stmt = '%s(lsts["%s"],%s)' % (method_name, lst_name,
delarg)
setup = "from __main__ import %s, lsts" % method_name
times = 3000000 / len(lst) # reduce the number of
times you repeat for big lists
print "%20s(%10s,%10s): %.3f" % (method_name,
lst_name, delarg, min(timeit.Timer(stmt, setup).repeat(3, times)))

tests = (
([1,2,3], 2, [1,3]),
([9,8,7], 9, [8,7]),
([9,8,7], 8, [9,7]),
([9,8,7], 7, [9,8]),
([9,8,7], 0, [9,8,7]),
([9,8,7], -1,[9,8,7]),
([9,8,7], 99, [9,8,7]),
([9], 9, []),
([], 9, []),
)

def do_tests(method_names):
nerrs = 0
for method_name in method_names:
func = globals()[method_name]
for test in tests:
listarg, delarg, expected = test
trap = 0
try:
actual = listarg[:]
func(actual, delarg)
except:
exc, val = sys.exc_info()[:2]
trap = 1
if trap:
print "%s(%s, %s) -> %s(%s); expected %s" %
(method_name, listarg, delarg, exc, val, expected)
nerrs += 1
elif actual != expected:
print "%s(%s, %s) -> %s; expected %s" % (method_name,
listarg, delarg, actual, expected)
nerrs += 1
if not nerrs:
print "--- all tests passed ---"

def usage():
print "usage: %s action [method_names]" % sys.argv[0]
print "action is time or test"
sys.exit(1)

if __name__ == "__main__":
main(sys.argv[1:2], sys.argv[2:])

 

[John Machin]

According to Nick's article, I added three 'reversed' methods to your provided
test prog. and the result turned out method_reversed is faster than

others except the 'three' case.

Following is my modified version: [snip]
def method_reversed_idx(lst):
idx = 0
for i in reversed(lst):
if i == 2:
del lst[idx]
idx += 1

There appears to be a problem with this one:
.... idx = 0
.... for i in reversed(lst):
.... if i == 2:
.... del lst[idx]
.... idx += 1
....

lst=[1,2,3];method_reversed_idx(lst);print lst [1, 3]
lst=[2,1,3];method_reversed_idx(lst);print lst [2, 1]
lst=[1,3,2];method_reversed_idx(lst);print lst [3]

 

[skull]

According to Nick's article, I added three 'reversed' methods to your provided
test prog. and the result turned out method_reversed is faster than others except the 'three' case.
Following is my modified version:

import timeit

def method_copy(lst):
for i in lst[:]:
if i == 2:
lst.remove(i)
return lst

def method_listcomp(lst):
return [i for i in lst if i!=2]

def method_while(lst):
i = 0
while i < len(lst):
if lst == 2:
lst.remove(i)
else:
i += 1
return lst

def method_enum_reversed(lst):
for i,x in enumerate(reversed(lst)):
if x == 2:
del lst[-i-1]

def method_reversed(lst):
for i in reversed(lst):
if i == 2:
lst.remove(i)

def method_reversed_idx(lst):
idx = 0
for i in reversed(lst):
if i == 2:
del lst[idx]
idx += 1

lsts = dict(three=range(3),
hundred=range(100),
thousand=range(1000),
million=range(1000000))

if __name__ == "__main__":
for lst_name, lst in lsts.iteritems():
print "%s" % lst_name
for method_name in ["method_copy", "method_listcomp", "method_while", "method_enum_reversed", "method_reversed", "method_reversed_idx"]:
stmt = '%s(lsts["%s"])' % (method_name, lst_name)
setup = "from __main__ import %s, lsts" % method_name

times = 3000000 / len(lst) # reduce the number of times you repeat for big lists
print " %s: %s" % (method_name, timeit.Timer(stmt, setup).repeat(3, times))