By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,092 Members | 1,650 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,092 IT Pros & Developers. It's quick & easy.

How to del item of a list in loop?

P: n/a

Hi everybody, it is my first post in this newsgroup.
I am a newbie for python though I have several years development experience in c++.
recently, I was stumped when I tried to del item of a list when iteration.

here is the wrong way I did:

lst = [1, 2, 3]
for i in lst:
print i
if i == 2:
lst.remove(i)

the result is:

1
2


as you would see, '3' is missing. this problem is caused by 'lst.remove(i)'.
apparently, 'marked-and-sweep' is a solution to deal with this issue.
but I think there SHOULD BE more 'wise' trick. I want to get your help.

Thanks in advance.

- skull
Jul 18 '05 #1
Share this Question
Share on Google+
25 Replies


P: n/a
skull wrote:
Hi everybody, it is my first post in this newsgroup.
I am a newbie for python though I have several years development experience in c++.
recently, I was stumped when I tried to del item of a list when iteration.

here is the wrong way I did:

lst = [1, 2, 3]
for i in lst:
print i
if i == 2:
lst.remove(i)

the result is:

1
2


as you would see, '3' is missing. this problem is caused by 'lst.remove(i)'.
apparently, 'marked-and-sweep' is a solution to deal with this issue.
but I think there SHOULD BE more 'wise' trick. I want to get your help.


Quick solution:

for i in lst[:]

iterates over a copy.

Reinhold
Jul 18 '05 #2

P: n/a
"skull" wrote:
Hi everybody, it is my first post in this newsgroup.
I am a newbie for python though I have several years development experience in c++.
recently, I was stumped when I tried to del item of a list when iteration.

here is the wrong way I did:

lst = [1, 2, 3]
for i in lst:
print i
if i == 2:
lst.remove(i)

the result is:

1
2


as you would see, '3' is missing. this problem is caused by 'lst.remove(i)'.


the internal loop counter is incremented whether you remove stuff or not, so
when you're moving things around by removing items in the middle, the loop
will skip over items. this is basic for-in usage, and any decent tutorial should
explain this.
to fix this, you can build a new output list, loop backwards, or loop over a
copy. the last is easiest to implement:

lst = [1, 2, 3]
for i in lst[:]:
print i
if i == 2:
lst.remove(i)

but the others may have advantages in certain use cases.
if you want more details, see the language reference:

http://docs.python.org/ref/for.html

(note the warning)

</F>

Jul 18 '05 #3

P: n/a
Reinhold Birkenfeld wrote:
skull wrote:
Hi everybody, it is my first post in this newsgroup.
I am a newbie for python though I have several years development experience in c++.
recently, I was stumped when I tried to del item of a list when iteration.

here is the wrong way I did:

lst = [1, 2, 3]
for i in lst:
print i
if i == 2:
lst.remove(i)

the result is:

1
2
>


as you would see, '3' is missing. this problem is caused by 'lst.remove(i)'.
apparently, 'marked-and-sweep' is a solution to deal with this issue.
but I think there SHOULD BE more 'wise' trick. I want to get your help.


Quick solution:

for i in lst[:]

iterates over a copy.


Addition: In Py2.4, I can't find a problem with

for i in reversed(lst)

Any objections?

Reinhold
Jul 18 '05 #4

P: n/a
On Sat, 15 Jan 2005 15:27:08 -0500, skull <sk****@sina.com.cn> wrote:
lst = [1, 2, 3]
for i in lst:
print i
if i == 2:
lst.remove(i)

the result is:

1
2


As others have suggested, you can use a copy of the list.
Alternatively and depending on what you're trying to accomplish (how
complicated it is), lst = [i for i in lst if i!=2] might look better.
--
Mitja
Jul 18 '05 #5

P: n/a
skull <sk****@sina.com.cn> writes:

Thank you for your replys.
lst[:] is did a solution, it makes a copy of list specially for iteration and
removes items from the original one.

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
Hi everybody, it is my first post in this newsgroup.
I am a newbie for python though I have several years development experience in c++.
recently, I was stumped when I tried to del item of a list when iteration.

here is the wrong way I did:

lst = [1, 2, 3]
for i in lst:
print i
if i == 2:
lst.remove(i)

the result is:

1
2


as you would see, '3' is missing. this problem is caused by 'lst.remove(i)'.
apparently, 'marked-and-sweep' is a solution to deal with this issue.
but I think there SHOULD BE more 'wise' trick. I want to get your help.

Thanks in advance.

- skull

Jul 18 '05 #6

P: n/a
"skull" wrote:
It makes a copy operation!
so? in python, shallow copies are cheap.
here is a faster and 'ugly' solution:


faster? did you try it, or are you combining a C++ mindset with an
urge to do premature optimizations? (hint: it's slower)

if you care about performance, you shouldn't use "remove", btw. building
a new list is more efficient, especially if you use a list comprehension:

lst = [i for i in lst if i != 2]

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

</F>

Jul 18 '05 #7

P: n/a
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@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@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
Jul 18 '05 #8

P: n/a
Reinhold Birkenfeld <re************************@wolke7.net> writes:
Quick solution:

for i in lst[:]

iterates over a copy.


Addition: In Py2.4, I can't find a problem with

for i in reversed(lst)

Any objections?

Reinhold


I just downloaded py2.4, and made a test using reversed.
it sure be no problem, I thought maybe the reversed holded a copy of list,
and eventually iterated through the copy.
but the truth is not as I thought so:

import sys

class Test:
pass

lst = [Test(),Test(),Test()]

E1: for i in lst[:]:
E2: for i in reversed(lst):
print sys.getrefcount(i)

###################
E1 outputs:
4
4
4

E2 outputs:
3
3
3

It looks that the reversed does not make a copy of list in contrast with lst[:].
so should we regard: reversed is faster than lst[:]?
I do not have any idea about why it is.

- skull
Jul 18 '05 #9

P: n/a
Reinhold Birkenfeld wrote:
Addition: In Py2.4, I can't find a problem with

for i in reversed(lst)


Some poking around suggests it's fine - and it avoids copying the list. Don't
delete anything earlier in the list than the current element though (which
list.remove() will do quite happily when data is duplicated).

However, there will still be data movement costs when deleting elements from the
middle of the list. In addition, remove() itself has to do a linear search for
the value being removed.

An off-place solution based on a list comprehension is usually going to be your
best performer - it's an O(n) operation, based on the size of the original list.
The in-place mechanisms can turn out to be O(n**2) due to worst-case memory
movement effects (lists don't allow gaps, so deleting items will usually trigger
data movement).

I think this is about the best you can do for an in-place version:
for i, x in enumerate(reversed(lst)):
if x == 2:
del lst[-i]

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

Cheers,
Nick.
--
Nick Coghlan | nc******@email.com | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net
Jul 18 '05 #10

P: n/a

Fredrik Lundh wrote:

lst = [i for i in lst if i != 2]

(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. Achieving the same result as the list comprehension, by
doing lst = list(i for ... etc etc), appears to be slower.

Jul 18 '05 #11

P: n/a

Nick Coghlan wrote:

I think this is about the best you can do for an in-place version:
for i, x in enumerate(reversed(lst)):
if x == 2:
del lst[-i]
Don't think, implement and measure. You may be surprised. Compare these
two for example:

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

!def method_coghlan(lst, x):
! for i, obj in enumerate(reversed(lst)):
! if obj == x:
! del lst[-i]
! return lst

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


Have you measured this?

Jul 18 '05 #12

P: n/a

Michael Hoffman wrote:
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.
Assuming, as have other posters, that the requirement is to remove all
elements whose value is 2: it doesn't work. The result is [2, 3]
instead of the expected [1, 3].
method_while: [3.8680000305175781, 3.8680000305175781, 3.872999906539917]

Three significant figures is plenty. Showing just the minimum of the
results might be better.
If you want to get really hairy, you can compare the bytecode instructions for these three methods:

Timing and bytecode-peeking a broken function are a little "premature".

Jul 18 '05 #13

P: n/a

Nick Coghlan wrote:
I think this is about the best you can do for an in-place version:
for i, x in enumerate(reversed(lst)):
if x == 2:
del lst[-i]

I think del lst[-i-1] might be functionally better.

Jul 18 '05 #14

P: n/a
John Machin wrote:
Three significant figures is plenty. Showing just the minimum of the
results might be better.


It might be, but how much time do you want to spend on getting your
results for a benchmark that will be run once in the "better" format?

Next time you can run the benchmark yourself and it will be in exactly
the format you want. Give me a break.
--
Michael Hoffman
Jul 18 '05 #15

P: n/a

Michael Hoffman wrote:
John Machin wrote:
Three significant figures is plenty. Showing just the minimum of the results might be better.
It might be, but how much time do you want to spend on getting your
results for a benchmark that will be run once in the "better" format?


About the same time as the "worse" format. The Mona Lisa was painted
once. The Taj Mahal was built once.
Next time you can run the benchmark yourself and it will be in exactly the format you want.


I've done that already. 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?

Jul 18 '05 #16

P: n/a
On Sat, 15 Jan 2005 15:27:08 -0500, skull <sk****@sina.com.cn> wrote:

Hi everybody, it is my first post in this newsgroup.
I am a newbie for python though I have several years development experience in c++.
recently, I was stumped when I tried to del item of a list when iteration.

here is the wrong way I did:

lst = [1, 2, 3]
for i in lst:
print i
if i == 2:
lst.remove(i)

the result is:

1
2

as you would see, '3' is missing. this problem is caused by 'lst.remove(i)'.
apparently, 'marked-and-sweep' is a solution to deal with this issue.
but I think there SHOULD BE more 'wise' trick. I want to get your help.

Thanks in advance.

No one seems to have suggested this in-place way yet,
so I'll trot it out once again ;-)
lst = [1, 2, 3]
i = 0
for item in lst: ... if item !=2:
... lst[i] = item
... i += 1
... del lst[i:]
lst

[1, 3]
Regards,
Bengt Richter
Jul 18 '05 #17

P: n/a

Bengt Richter wrote:
No one seems to have suggested this in-place way yet,
so I'll trot it out once again ;-)
>>> lst = [1, 2, 3]
>>> i = 0
>>> for item in lst: ... if item !=2:
... lst[i] = item
... i += 1
... >>> del lst[i:]
>>> lst

[1, 3]


Works, but slowly. Here's another that appears to be the best on large
lists, at least for removing 1 element. It's O(len(list) *
number_to_be_removed).

!def method_try_remove(lst, remove_this):
! try:
! while 1:
! lst.remove(remove_this)
! except:
! pass

Jul 18 '05 #18

P: n/a
On 15 Jan 2005 23:01:00 -0800, "John Machin" <sj******@lexicon.net> wrote:

Bengt Richter wrote:
No one seems to have suggested this in-place way yet,
so I'll trot it out once again ;-)
>>> lst = [1, 2, 3]
>>> i = 0
>>> for item in lst: ... if item !=2:
... lst[i] = item
... i += 1
...
>>> del lst[i:]
>>> lst

[1, 3]


Works, but slowly. Here's another that appears to be the best on large
lists, at least for removing 1 element. It's O(len(list) *
number_to_be_removed).


So my loop above should beat the while below pretty handily if deleting 2 from lst=[2]*10**7 ;-)
I.e., it should be O(len(lst)) period, though obviously lst.remove will be C-implemented,
and there will be a crossover point. Psyco ought to do well with the above, IWT.
!def method_try_remove(lst, remove_this):
! try:
! while 1:
! lst.remove(remove_this)
! except:
! pass


Maybe
import itertools
def foo(lst, vrem): # remove vrems from lst ... i = 0
... for lst[i], item in itertools.izip(lst, lst): i += item!=vrem
... del lst[i:]
... lst = [1, 2, 3]
foo(lst, 2)
lst

[1, 3]

I wonder if py2.4 generator expression as a souce of slice assignment, i.e.,
(did someone post this one? Someone must have ;-)

lst[:] = (item for item in lst if item!=remove_this)

would do what my loop is doing, in place. If the slice assignment accepts an
iterator, that might do it, if [:] assignment overwrites the old list
until it has to be extended or in this case possibly trimmed at the end.

If so, its hardly worth writing a function, since the generator expression should
have fast local access to its variables.

Regards,
Bengt Richter
Jul 18 '05 #19

P: n/a
Fredrik Lundh wrote:
here is a faster and 'ugly' solution:
faster? did you try it, or are you combining a C++ mindset with an
urge to do premature optimizations? (hint: it's slower)


Hmm. Given

import time

length = 2**15

L = range(length)

start = time.clock()
for i in L[:]:
if i%2 == 1:
L.remove(i)
print time.clock()-start

L = range(length)
start = time.clock()
i = 0
while i < len(L):
if L[i]%2 == 1:
del L[i]
else:
i += 1
print time.clock()-start

on my system (python 2.4, Linux 2.6, Pentium 4 3.2GHz), I get

4.85
0.29

So using an explicit index is *much* faster (the OP's version
was incorrect, of course, as it used .remove with an index).
if you care about performance, you shouldn't use "remove"


Yes, but primarily because remove needs to search the entire
list for the item to be removed.

Whether del is more efficient than building a new list
depends on the number of items to be removed.

Regards,
Martin
Jul 18 '05 #20

P: n/a
John Machin wrote:
(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>

Jul 18 '05 #21

P: n/a
John Machin wrote:
Nick Coghlan wrote:
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.

--
Nick Coghlan | nc******@email.com | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net
Jul 18 '05 #22

P: n/a
John Machin wrote:
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.
--
Michael Hoffman
Jul 18 '05 #23

P: n/a
On Sun, 16 Jan 2005 11:43:10 +0000, Michael Hoffman
<ca*******@mh391.invalid> wrote:
John Machin wrote:
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.


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[i] == 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[i] = 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:])
Jul 18 '05 #24

P: n/a

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[i] == 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))

Jul 18 '05 #25

P: n/a

skull wrote:
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:
def method_reversed_idx(lst): .... 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]


Jul 18 '05 #26

This discussion thread is closed

Replies have been disabled for this discussion.