Algorithm help per favore

[Matt Shomphe]

anton at vredegoor.doge.nl (Anton Vredegoor) wrote in message news:

[snip]
> Better to measure it! I've written a test script. By the way: your
> method has an error, because it chops off the last element
> unconditionally ... Having a lot of people compare code produces
> alternatives, which in my opinion comes before passing tests.
> Tests can be done later.
> 
> So below's my script (based partly on your idea and those of some
> other posters).
> 

Excellent!  I've added some other functions (en(), xrng(), &
inplace2()) and used the profile module to run the test (of course,
the numbers vary with each run):

--------------------------------------------------
# testlist.py

import random, profile
import time

def zipped(L):
    return  list(L[:1]) + [x for x,y in zip(L[1:],L[:-1]) if x!=y] 
def ranged(L):
    return list(L[:1])+[L[i] for i in xrange(1,len(L))
        if L[i] != L[i-1]]
def inplace(thelist):
    i=0
    for item in thelist:
        if item==thelist[i]: continue
        i+=1
        thelist[i]=item
    del thelist[i+1:]
    return thelist
def xrng(l):
    return([l[i] for i in xrange(len(l)) if i == 0 or l[i-1] !=l[i]])
def en(l):
    try:
        return([x for i,x in enumerate(l) if i == 0 or x !=l[i-1]])
    except NameError:
        print "You need python v 2.3 or higher"
        return(l)
    
def inplace2(l):
    for i in xrange(len(l)):
        if i == 0 or l[i] != l[i-1]: continue
        del l[i]
    return(l)

if __name__=='__main__':
    n = 100000
    uniques = 10
    U=range(uniques)
 
    def choice():
        return random.choice(U)
    # Make sure that all the functions return 
    # the correct values with a small test

    testL = [6,3,3,3,4,5,6,7,7,8,8,9,6]
    funcs = [zipped,ranged,inplace,xrng,en,inplace2]
    arr = map(lambda f: f(testL), funcs)
    for val in arr:
        assert val == arr[-1]
    L = [choice() for i in range(n)] #build the test list
    funclist = ['zipped(L)','ranged(L)','inplace(L)','xrng(L)','en(L)','inplace2(L)']
# The list of functions
    for f in funclist: #run it!
        profile.run('%s'%f)
---------------------------------------------------------

Here are the results:

---------------------------------------------------------

         3 function calls in 0.689 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall
filename:lineno(function)
        1    0.003    0.003    0.685    0.685 <string>:1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.004    0.004    0.689    0.689 profile:0(zipped(L))
        1    0.682    0.682    0.682    0.682 testlist.py:4(zipped)


         3 function calls in 0.255 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall
filename:lineno(function)
        1    0.004    0.004    0.254    0.254 <string>:1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.001    0.001    0.255    0.255 profile:0(ranged(L))
        1    0.251    0.251    0.251    0.251 testlist.py:6(ranged)


         3 function calls in 0.182 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall
filename:lineno(function)
        1    0.000    0.000    0.181    0.181 <string>:1(?)
        1    0.001    0.001    0.182    0.182 profile:0(inplace(L))
        0    0.000             0.000          profile:0(profiler)
        1    0.181    0.181    0.181    0.181 testlist.py:9(inplace)


         3 function calls in 0.277 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall
filename:lineno(function)
        1    0.004    0.004    0.276    0.276 <string>:1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.002    0.002    0.277    0.277 profile:0(xrng(L))
        1    0.272    0.272    0.272    0.272 testlist.py:17(xrng)


         3 function calls in 0.299 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall
filename:lineno(function)
        1    0.003    0.003    0.298    0.298 <string>:1(?)
        1    0.001    0.001    0.299    0.299 profile:0(en(L))
        0    0.000             0.000          profile:0(profiler)
        1    0.295    0.295    0.295    0.295 testlist.py:19(en)


         3 function calls in 0.169 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall
filename:lineno(function)
        1    0.000    0.000    0.168    0.168 <string>:1(?)
        1    0.001    0.001    0.169    0.169 profile:0(inplace2(L))
        0    0.000             0.000          profile:0(profiler)
        1    0.168    0.168    0.168    0.168 testlist.py:26(inplace2)

----------------------------------------------------------------------

It seems that inplace() & inplace2() are always fastest (although I'm
a little leery of inplace2()...)