list IndexError

[Ishwor]

i am trying to remove an item 'e' from the list l but i keep getting IndexError.
I know the size of the list l is changing in the for loop & its sort
of trivial task but i found no other way than to suppress the
IndexError by doing a pass. any other ways you guys can suggest? Also
is this a good or bad habit in Python? someone may perhaps suggest a
better way which i am unaware of?? the deletion could be invoked from
user input (command line) as well so its not limited to 'e'( as in my
code)
[color=blue][color=green][color=darkred]
>>> l[/color][/color][/color]
['a', 'b', 'c', 'e', 'm'][color=blue][color=green][color=darkred]
>>> for i in range(0,len(l)) :[/color][/color][/color]
if l[i] == 'e':
l.pop(i);


'e'

Traceback (most recent call last):
File "<pyshell#389>" , line 2, in -toplevel-
if l[i] == 'e':
IndexError: list index out of range[color=blue][color=green][color=darkred]
>>> l[/color][/color][/color]
['a', 'b', 'c', 'm']


==Using suppressing technique( a bad one though :-) )==[color=blue][color=green][color=darkred]
>>> l[/color][/color][/color]
['a', 'b', 'c', 'm', 'd'][color=blue][color=green]
>> for i in range(0,len(l)) :[/color][/color]
try:
if l[i] == 'e':
l.pop(i);
except IndexError:
pass;
[color=blue][color=green][color=darkred]
>>> l[/color][/color][/color]
['a', 'b', 'c', 'm', 'd']

==Using suppressing technique====

Any type of code changing/improving ways is heartily welcomed ;-)

--
cheers,
Ishwor Gurung

[Steven Bethard]

Re: list IndexError

Ishwor wrote:[color=blue]
> i am trying to remove an item 'e' from the list l[/color]

I thought it might be helpful to code some of the alternatives you've
been given and look at the timings to put things into perspective. The
code:

-------------------- remove.py --------------------
def remove_lc(x, lst):
lst[:] = [item for item in lst if item != x]

def remove_list(x, lst):
result = []
for item in lst:
if item != x:
result.append(i tem)
lst[:] = result

def remove_filter(x , lst):
lst[:] = filter(lambda item: item != x, lst)

def remove_xrange(x , lst):
for i in xrange(len(lst)-1, -1, -1):
if lst[i] == x:
del lst[i]

def remove_remove(x , lst):
while x in lst:
lst.remove(x)

def remove_try(x, lst):
try:
while True:
lst.remove(x)
except ValueError:
pass

def remove_ishwor(x , lst):
for item in lst[:]:
if item == x:
lst.remove(x);
--------------------------------------------------

First, some timings when only 1 out of every 1000 elements needs to be
removed. Timings were taken with Python 2.4 on a 2.26 Ghz Windows box
using:
$ python -m timeit -s "import remove; lst = [x % 1000 for x in
xrange(10000)]" "remove.remove_ <name>(500, lst)"

remove_remove: 516 usec per loop
remove_try: 604 usec per loop
remove_ishwor: 1.61 msec per loop
remove_xrange: 2.29 msec per loop
remove_lc: 2.37 msec per loop
remove_list: 5.3 msec per loop
remove_filter: 5.65 msec per loop

Now, some timings when 1 out of every 10 elements needs to be removed.
Timings were taken using:
$ python -m timeit -s "import remove; lst = [x % 10 for x in
xrange(10000)]" "remove.remove_ <name>(5, lst)"

remove_lc: 2.03 msec per loop
remove_xrange: 2.08 msec per loop
remove_list: 4.72 msec per loop
remove_filter: 5.17 msec per loop
remove_try: 30.7 msec per loop
remove_ishwor: 31.5 msec per loop
remove_remove: 60.2 msec per loop



The moral of the story here is that, if the items to be removed only
make up a very small percentage of the list, an approach like
remove_remove or remove_try might be okay. On the other hand, if you
expect the items to be removed will make up even a moderate percentage
of the list (e.g. 10%), then remove_lc or remove_xrange is a vastly
better alternative.

Steve

[Ishwor]

Re: list IndexError

On Wed, 22 Dec 2004 21:42:16 GMT, Steven Bethard
<steven.bethard @gmail.com> wrote:[color=blue]
> Ishwor wrote:[color=green]
> > i am trying to remove an item 'e' from the list l[/color]
>
> I thought it might be helpful to code some of the alternatives you've
> been given and look at the timings to put things into perspective. The
> code:
>
> -------------------- remove.py --------------------
> def remove_lc(x, lst):
> lst[:] = [item for item in lst if item != x]
>
> def remove_list(x, lst):
> result = []
> for item in lst:
> if item != x:
> result.append(i tem)
> lst[:] = result
>
> def remove_filter(x , lst):
> lst[:] = filter(lambda item: item != x, lst)
>
> def remove_xrange(x , lst):
> for i in xrange(len(lst)-1, -1, -1):
> if lst[i] == x:
> del lst[i]
>
> def remove_remove(x , lst):
> while x in lst:
> lst.remove(x)
>
> def remove_try(x, lst):
> try:
> while True:
> lst.remove(x)
> except ValueError:
> pass
>
> def remove_ishwor(x , lst):
> for item in lst[:]:
> if item == x:
> lst.remove(x);
> --------------------------------------------------
>
> First, some timings when only 1 out of every 1000 elements needs to be
> removed. Timings were taken with Python 2.4 on a 2.26 Ghz Windows box
> using:
> $ python -m timeit -s "import remove; lst = [x % 1000 for x in
> xrange(10000)]" "remove.remove_ <name>(500, lst)"
>
> remove_remove: 516 usec per loop
> remove_try: 604 usec per loop
> remove_ishwor: 1.61 msec per loop
> remove_xrange: 2.29 msec per loop
> remove_lc: 2.37 msec per loop
> remove_list: 5.3 msec per loop
> remove_filter: 5.65 msec per loop
>
> Now, some timings when 1 out of every 10 elements needs to be removed.
> Timings were taken using:
> $ python -m timeit -s "import remove; lst = [x % 10 for x in
> xrange(10000)]" "remove.remove_ <name>(5, lst)"
>
> remove_lc: 2.03 msec per loop
> remove_xrange: 2.08 msec per loop
> remove_list: 4.72 msec per loop
> remove_filter: 5.17 msec per loop
> remove_try: 30.7 msec per loop
> remove_ishwor: 31.5 msec per loop
> remove_remove: 60.2 msec per loop
>
> The moral of the story here is that, if the items to be removed only
> make up a very small percentage of the list, an approach like
> remove_remove or remove_try might be okay. On the other hand, if you
> expect the items to be removed will make up even a moderate percentage
> of the list (e.g. 10%), then remove_lc or remove_xrange is a vastly
> better alternative.
>
> Steve
> --
> http://mail.python.org/mailman/listinfo/python-list
>[/color]
umm... looks good.. i am running these task sets on my box as well
slightly slower than yours 2.4Ghz... thanx Steve. :-) now i'll sit
back and dwell a bit deeper into it now.


--
cheers,
Ishwor Gurung

[Peter Otten]

Re: list IndexError

Steven Bethard wrote:
[color=blue]
> I thought it might be helpful to code some of the alternatives you've
> been given and look at the timings to put things into perspective. The
> code:
>
> -------------------- remove.py --------------------
> def remove_lc(x, lst):
> lst[:] = [item for item in lst if item != x][/color]

[snip]
[color=blue]
> $ python -m timeit -s "import remove; lst = [x % 1000 for x in
> xrange(10000)]" "remove.remove_ <name>(500, lst)"[/color]

I do not think it measures what you think it measures.

A statement in the -s option is only run once, so you have to be careful
with mutable data and pass a copy of your sample to the function about to
be timed. The following example illustrates the problem:

$ py24 -m timeit -n5 -r1 -s"r=[0]" -s"def f(r): print r; r[0] += 1" "f(r)"
[0]
[1]
[2]
[3]
[4]
5 loops, best of 1: 106 usec per loop

Peter

[Nick Coghlan]

Re: list IndexError

Steven Bethard wrote:[color=blue]
> Ishwor wrote:
>[color=green]
>> i am trying to remove an item 'e' from the list l[/color]
>
>
> I thought it might be helpful to code some of the alternatives you've
> been given and look at the timings to put things into perspective. The
> code:
>
> -------------------- remove.py --------------------
> def remove_lc(x, lst):
> lst[:] = [item for item in lst if item != x]
>
> def remove_try(x, lst):
> try:
> while True:
> lst.remove(x)
> except ValueError:
> pass
>[/color]
I'd suggest a slightly different definition for remove_try:

def remove_try(x, lst):
idx = 0
try:
while True:
idx = lst.index(x, idx)
del s[idx]
except ValueError:
pass

This avoids the 'restart from the beginning' problem with the current approach.

Anyway, pitting that against Steve's remove_lc on a 2.6 GHz hyperthreaded P4
gives the following results for different percentages of removed values:

..1% lc: 2010 usec try: 467 usec
10% lc: 1810 usec try: 427 usec
50% lc: 1010 usec try: 273 usec
90% lc: 214 usec try: 61 usec

I know why the filtration version gets faster as the percentage increases (the
resulting list is smaller), but I'm not sure why the in-place version is getting
faster (as it makes more method calls and performs more deletions). One
possibility is that as the list gets shorter due to the deletions, the whole
thing gets pulled into the processor's cache and the operations start going
blazingly fast.

Cheers,
Nick.

P.S. These were the commands I timed:

..1%:
python -m timeit -s "import remove; lst = [bool(x % 1000) for x in
xrange(10000)]" "remove.remove_ <name>(False, lst)"

10%:
python -m timeit -s "import remove; lst = [bool(x % 10) for x in xrange(10000)]"
"remove.remove_ <name>(False, lst)"

50%:
python -m timeit -s "import remove; lst = [bool(x % 2) for x in xrange(10000)]"
"remove.remove_ <name>(False, lst)"

90%:
python -m timeit -s "import remove; lst = [not bool(x % 10) for x in
xrange(10000)]" "remove.remove_ <name>(False, lst)"

And just to prove they're both still doing the right thing in that last example:

Py> import remove
Py> lst = [not bool(x % 10) for x in xrange(10000)]
Py> len(lst)
10000
Py> remove.remove_l c(False, lst)
Py> len(lst)
1000
Py> lst = [not bool(x % 10) for x in xrange(10000)]
Py> len(lst)
10000
Py> remove.remove_t ry(False, lst)
Py> len(lst)
1000

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net

[Nick Coghlan]

Re: list IndexError

Peter Otten wrote:[color=blue]
> I do not think it measures what you think it measures.[/color]

Ah, good point. . . so we were actually measuring how long it takes to make zero
replacements on the modified list, which explains the downward trend of the
timings (as the modified list gets shorter).

Adding the list copy (using lst[:] in the call to the remove() method) gives me
these numbers:

..1% lc: 2410 usec try: 617 usec
10% lc: 2020 usec try: 7340 usec
50% lc: 1780 usec try: 34300 usec
90% lc: 1450 usec try: 61000 usec

Right, that's *far* more like the numbers I was expecting :)

And now they demonstrate what they were meant to demonstrate - that there's a
reason filtration is the recommended approach!

Cheers,
Nick.

--
Nick Coghlan | ncoghlan@email. com | Brisbane, Australia
---------------------------------------------------------------

http://boredomandlaziness.skystorm.net

[Steven Bethard]

Re: list IndexError

Steven Bethard wrote:[color=blue]
> Ishwor wrote:
>[color=green]
>> i am trying to remove an item 'e' from the list l[/color]
>
>
> I thought it might be helpful to code some of the alternatives you've
> been given and look at the timings to put things into perspective.[/color]

Corrected timings[1] using:

$ python -m timeit -s "import remove" "remove.remove_ <name>(500, [x %
1000 for x in xrange(10000)])"

remove_xrange: 5.46 msec per loop
remove_lc: 5.48 msec per loop
remove_try: 6.31 msec per loop
remove_ishwor: 7.03 msec per loop
remove_list: 8.38 msec per loop
remove_filter: 9.08 msec per loop
remove_remove: 9.98 msec per loop

and using:

$ python -m timeit -s "import remove" "remove.remove_ <name>(50, [x % 100
for x in xrange(10000)])"

remove_lc: 5.12 msec per loop
remove_xrange: 5.8 msec per loop
remove_list: 7.9 msec per loop
remove_filter: 8.29 msec per loop
remove_try: 30.3 msec per loop
remove_ishwor: 30.7 msec per loop
remove_remove: 55.2 msec per loop

So, when timed correctly =) list comprehensions and xrange are faster
even when the items to be removed are only 0.1% of the data.

Steve

[1] Thanks Peter!

P.S. For fun, I played around with the data to see if I could find a
dataset on which one of the "slower" techniques is faster than remove_lc
or remove_xrange. Here's one:

$ python -m timeit -s "import remove" "remove.remove_ <name>(25, [x % 50
for x in xrange(100)])"

remove_remove: 53.3 usec per loop
remove_xrange: 57.7 usec per loop
remove_try: 58.8 usec per loop
remove_ishwor: 58.9 usec per loop
remove_lc: 65.4 usec per loop
remove_list: 93.7 usec per loop
remove_filter: 95.8 usec per loop