list IndexError

Nick Coghlan ncoghlan at iinet.net.au
Thu Dec 23 09:39:31 CET 2004


Steven Bethard wrote:
> Ishwor wrote:
> 
>> i am trying to remove an item 'e' from the list l
> 
> 
> 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
> 
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_lc(False, lst)
Py> len(lst)
1000
Py> lst = [not bool(x % 10) for x in xrange(10000)]
Py> len(lst)
10000
Py> remove.remove_try(False, lst)
Py> len(lst)
1000

-- 
Nick Coghlan   |   ncoghlan at email.com   |   Brisbane, Australia
---------------------------------------------------------------
             http://boredomandlaziness.skystorm.net



More information about the Python-list mailing list