How to del item of a list in loop?
Michael Hoffman
cam.ac.uk at mh391.invalid
Sat Jan 15 07:58:22 EST 2005
skull wrote:
> but I still have an other thing to worry about coming with this way: does
> performance sucks when the list is big enough?
> It makes a copy operation!
>
> here is a faster and 'ugly' solution:
>
> lst = [1, 2, 3]
> i = 0
> while i < len(lst):
> if lst[i] == 2:
> lst.remove(i)
> else:
> i += 1
Actually, that is the slowest of the three methods proposed so far for
large lists on my system.
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[i] == 2:
lst.remove(i)
else:
i += 1
return lst
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"]:
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))
RESULTS:
Michael at MINIMOO ~
$ python -V && uname -a
Python 2.4
CYGWIN_NT-5.1 MINIMOO 1.5.12(0.116/4/2) 2004-11-10 08:34 i686 unknown unknown Cygwin
Michael at MINIMOO ~
$ python testlist.py
thousand
method_copy: [1.0479998588562012, 1.0080001354217529, 1.0119998455047607]
method_listcomp: [1.5119998455047607, 1.5110001564025879, 1.503000020980835]
method_while: [3.8680000305175781, 3.8680000305175781, 3.872999906539917]
hundred
method_copy: [1.1269998550415039, 1.127000093460083, 1.190000057220459]
method_listcomp: [2.0360000133514404, 2.0480000972747803, 2.0069999694824219]
method_while: [3.5299999713897705, 3.5540001392364502, 3.5130000114440918]
three
method_copy: [6.1210000514984131, 6.1679999828338623, 6.1239998340606689]
method_listcomp: [9.7590000629425049, 9.5309998989105225, 9.5]
method_while: [6.6609997749328613, 6.625, 6.6800000667572021]
million
method_copy: [1.3420000076293945, 1.3029999732971191, 1.3389999866485596]
method_listcomp: [1.5409998893737793, 1.5500001907348633, 1.5289998054504395]
method_while: [3.9619998931884766, 3.9210000038146973, 3.9590001106262207]
Now your "while" method does use less memory, but it is not as fast as the
copy method.
If you want to get really hairy, you can compare the bytecode instructions
for these three methods:
$ python
Python 2.4 (#1, Dec 4 2004, 20:10:33)
[GCC 3.3.3 (cygwin special)] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import testlist
>>> from dis import dis
>>> dis(testlist.method_while)
13 0 LOAD_CONST 1 (0)
3 STORE_FAST 1 (i)
14 6 SETUP_LOOP 68 (to 77)
>> 9 LOAD_FAST 1 (i)
12 LOAD_GLOBAL 1 (len)
15 LOAD_FAST 0 (lst)
18 CALL_FUNCTION 1
21 COMPARE_OP 0 (<)
24 JUMP_IF_FALSE 48 (to 75)
27 POP_TOP
15 28 LOAD_FAST 0 (lst)
31 LOAD_FAST 1 (i)
34 BINARY_SUBSCR
35 LOAD_CONST 2 (2)
38 COMPARE_OP 2 (==)
41 JUMP_IF_FALSE 17 (to 61)
44 POP_TOP
16 45 LOAD_FAST 0 (lst)
48 LOAD_ATTR 3 (remove)
51 LOAD_FAST 1 (i)
54 CALL_FUNCTION 1
57 POP_TOP
58 JUMP_ABSOLUTE 9
>> 61 POP_TOP
18 62 LOAD_FAST 1 (i)
65 LOAD_CONST 3 (1)
68 INPLACE_ADD
69 STORE_FAST 1 (i)
72 JUMP_ABSOLUTE 9
>> 75 POP_TOP
76 POP_BLOCK
19 >> 77 LOAD_FAST 0 (lst)
80 RETURN_VALUE
>>> dis(testlist.method_copy)
4 0 SETUP_LOOP 45 (to 48)
3 LOAD_FAST 0 (lst)
6 SLICE+0
7 GET_ITER
>> 8 FOR_ITER 36 (to 47)
11 STORE_FAST 1 (i)
5 14 LOAD_FAST 1 (i)
17 LOAD_CONST 1 (2)
20 COMPARE_OP 2 (==)
23 JUMP_IF_FALSE 17 (to 43)
26 POP_TOP
6 27 LOAD_FAST 0 (lst)
30 LOAD_ATTR 2 (remove)
33 LOAD_FAST 1 (i)
36 CALL_FUNCTION 1
39 POP_TOP
40 JUMP_ABSOLUTE 8
>> 43 POP_TOP
44 JUMP_ABSOLUTE 8
>> 47 POP_BLOCK
7 >> 48 LOAD_FAST 0 (lst)
51 RETURN_VALUE
>>> dis(testlist.method_listcomp)
10 0 BUILD_LIST 0
3 DUP_TOP
4 STORE_FAST 1 (_[1])
7 LOAD_FAST 0 (lst)
10 GET_ITER
>> 11 FOR_ITER 30 (to 44)
14 STORE_FAST 2 (i)
17 LOAD_FAST 2 (i)
20 LOAD_CONST 1 (2)
23 COMPARE_OP 3 (!=)
26 JUMP_IF_FALSE 11 (to 40)
29 POP_TOP
30 LOAD_FAST 1 (_[1])
33 LOAD_FAST 2 (i)
36 LIST_APPEND
37 JUMP_ABSOLUTE 11
>> 40 POP_TOP
41 JUMP_ABSOLUTE 11
>> 44 DELETE_FAST 1 (_[1])
47 RETURN_VALUE
For method_while, almost all of the times the list runs through,
you still have to add 1 to i, which is a lot of instructions:
18 62 LOAD_FAST 1 (i)
65 LOAD_CONST 3 (1)
68 INPLACE_ADD
69 STORE_FAST 1 (i)
72 JUMP_ABSOLUTE 9
With the other methods, when you find a false result, all you have to
do is the JUMP_ABSOLUTE. That saves you some time over several
million repetitions.
Well, that was longer than I thought it would be. HTH.
--
Michael Hoffman
More information about the Python-list
mailing list