Deleting from a list (reprise)

[Alex Martelli]

"Hans Nowak" <wurmy at earthlink.net> wrote in message
news:3C32BB53.C52BD2B7 at earthlink.net...
> Anthony Baxter wrote:
> >
> > >>> Hans Nowak wrote
> > > >>> x = [1, 2, 3, 1, 2, 8, 3, 1, 1, 1, 6]
> > > >>> while 1 in x:
> > >       x.remove(1)
> > > >>> x
> > > [2, 3, 2, 8, 3, 6]
> > > >>>
> >
> > note that this is pretty inefficient, as it starts at the start of
> > the list each time through the loop.
>
> Agreed. For small lists, the performance difference is trivial,
> though. I made a silly little benchmark (not posted) that shows
> that walking through the list backwards is almost always
> faster than the 'while x in lst' method shown above. How much
> faster depends on the frequency of the object-to-be-removed.

Benchmarking is a good idea: intuition often fails to give the
"right" answer.  Try, for example, the following:

import time, random

def do_bench(n, func, *args):
    start = time.clock()
    for i in range(n): func(*args)
    stend = time.clock()
    print "  %s %.2f"%(func.__name__, stend-start)

def delwhile(sequence, marker):
    sequence[:] = sequence
    while marker in sequence: sequence.remove(marker)

def delreverse(sequence, marker):
    sequence[:] = sequence
    for i in range(len(sequence), 0, -1):
        if sequence[i-1]==marker: del sequence[i-1]

def delfilter(sequence, marker):
    sequence[:] = sequence
    def nomarker(item, marker=marker): return item != marker
    sequence[:] = filter(nomarker, sequence)

def bench_run(length=100, freqma=0.2):
    # prepare reference sequence
    refr = range(length)
    marker = length+1
    for i in range(length):
        if random.random()<freqma:
            refr[i] = marker
    # run the benchmarks
    print "l=%d p=%.2f"%(length, freqma)
    for func in delwhile, delreverse, delfilter:
        do_bench(1000, func, refr, marker)

if __name__=='__main__':
    for length in 10, 20, 50:
        for freqma in 0.05, 0.10, 0.15:
            bench_run(length, freqma)


Here's what I get in a sample run:

C:\Python22>python -O benchy.py
l=10 p=0.05
  delwhile 0.01
  delreverse 0.04
  delfilter 0.07
l=10 p=0.10
  delwhile 0.01
  delreverse 0.04
  delfilter 0.08
l=10 p=0.15
  delwhile 0.01
  delreverse 0.04
  delfilter 0.07
l=20 p=0.05
  delwhile 0.01
  delreverse 0.06
  delfilter 0.11
l=20 p=0.10
  delwhile 0.01
  delreverse 0.06
  delfilter 0.10
l=20 p=0.15
  delwhile 0.01
  delreverse 0.05
  delfilter 0.09
l=50 p=0.05
  delwhile 0.02
  delreverse 0.12
  delfilter 0.22
l=50 p=0.10
  delwhile 0.02
  delreverse 0.12
  delfilter 0.20
l=50 p=0.15
  delwhile 0.02
  delreverse 0.11
  delfilter 0.19

C:\Python22>

Counter-intuitively to me, the trivial 'delwhile' approach appears to
be substantially faster than the "advanced" ideas on this benchmark
run -- and not by trivial amounts, either: 5 or 10 times faster is NOT
a speedup to sneer at.

As this sharply contradicts your findings about "almost always faster",
it's no doubt worth double checking both this benchmark and yours: it
IS quite possibly that I've goofed up somewhere (though I can't see it).


Alex