[Tutor] Lists...

[Roeland Rengelink]

Michael Schmitt wrote:
> 
> Just for fun I added a function using Alan G method to the Roeland's timing
> code as follows:
> 
Hi Michael,

I don't know why our numbers differ so much (you got 0.00000 in a lot of
your timing measurements)
Anyway, Alan's method is strictly brute force, just written somewhat
differently.
Here's what I get (Code follows at the end)

Brute force (n=10), t=0.000137
List filter (n=10), t=0.000212	# Alan's code
Dict lookup (n=10), t=0.000150
Dict filter (n=10), t=0.000119
Sorted list (n=10), t=0.000426

Brute force (n=100), t=0.006812
List filter (n=100), t=0.006745
Dict lookup (n=100), t=0.001056
Dict filter (n=100), t=0.000680
Sorted list (n=100), t=0.003793

Brute force (n=1000), t=0.831248
List filter (n=1000), t=0.837468
Dict lookup (n=1000), t=0.017591
Dict filter (n=1000), t=0.007191
Sorted list (n=1000), t=0.055949

Brute force (n=10000), t=92.381026
List filter (n=10000), t=92.870684
Dict lookup (n=10000), t=0.151935
Dict filter (n=10000), t=0.124802
Sorted list (n=10000), t=0.532801

i.e Quadratic time behaviour for brute force, linear time for
dictinonary based methods and using sorted lists.

-- the code 

from __future__ import nested_scopes

def intersect1(l1, l2):
    '''brute force intersection of two lists'''
    return [item for item in l1 if item in l2]

def intersect2(l1, l2):
    '''intersection of two lists, using dicts'''
    dict = {}
    for item in l2:
        dict[item] = None
    return [item for item in l1 if dict.has_key(item)]

def intersect2a(l1, l2):
    '''using dicts with filter, thanks to Remco Gehrlich'''
    dict = {}
    for item in l2:
        dict[item] = 1
    return filter(dict.has_key, l1)

def intersect3(l1, l2):
    '''intersection of two sorted lists of unique items'''
    result = []
    lo = 0
    hi = len(l2)
    for i in l1:
        for j in xrange(lo, hi):
            n = cmp(l2[j], i)
            if n==-1:
                lo = j
            elif n==1:
                break
            else:
                lo = j
                result.append(i)
                break
    return result

def intersect_eas(L1, L2):
    '''The easiest way for Alan G, requires nested_scopes'''
    return filter(lambda x: (x in L2), L1)

def make_list(n):
    '''Make a sorted list of unique ints larger than 1'''
    import random
    l = []
    x = 1
    for i in xrange(n):
        x = x+random.randrange(1, 5)
        l.append(x)
    return l

def time_func(intersect_func, l1, l2):
    import time
    t1 = time.time()
    l = intersect_func(l1, l2)
    t2 = time.time()-t1
#    print l[0:10]
    return t2

def test(n):
    l1 = make_list(n)
    l2 = make_list(n)
    print 'Brute force (n=%i), t=%f' % (n, time_func(intersect1, l1,
l2))
    print 'List filter (n=%i), t=%f' % (n, time_func(intersect_eas, l1,
l2))
    print 'Dict lookup (n=%i), t=%f' % (n, time_func(intersect2, l1,
l2))
    print 'Dict filter (n=%i), t=%f' % (n, time_func(intersect2a, l1,
l2))
    print 'Sorted list (n=%i), t=%f' % (n, time_func(intersect3, l1,
l2))
    print
if __name__=='__main__':
    test(10)
    test(100)
    test(1000)
    test(10000)


-- 
r.b.rigilink@chello.nl

"Half of what I say is nonsense. Unfortunately I don't know which half"