[Tutor] Lists...

[Michael Schmitt]

Just for fun I added a function using Alan G method to the Roeland's timing
code as follows:

def intersect1(l1, l2):
    '''brute force intersection of two lists'''
    if len(l1) > 1000:
        print 'forget about it...\n brute force number invalid!'
        return l1
    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'''
    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 '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 'Sort easy (n=%i), t=%f' % (n, time_func(intersect_eas, l1,l2))

if __name__=='__main__':
    test(10)
    test(100)
    test(1000)
    test(10000)

and the results.....
Brute force (n=10), t=0.000000
Dict lookup (n=10), t=0.000000
Dict filter (n=10), t=0.000000
Sorted list (n=10), t=0.000000
Sort easy (n=10), t=0.000000
Brute force (n=100), t=0.000000
Dict lookup (n=100), t=0.010000
Dict filter (n=100), t=0.000000
Sorted list (n=100), t=0.000000
Sort easy (n=100), t=0.000000
Brute force (n=1000), t=0.631000
Dict lookup (n=1000), t=0.030000
Dict filter (n=1000), t=0.021000
Sorted list (n=1000), t=0.060000
Sort easy (n=1000), t=0.010000
forget about it...
 brute force number invalid!
Brute force (n=10000), t=0.131000
Dict lookup (n=10000), t=0.270000
Dict filter (n=10000), t=0.210000
Sorted list (n=10000), t=0.681000
Sort easy (n=10000), t=0.210000

Thanks guys... that was cool.

Question regarding running the brute force method  with values of 10000 for
n under IDLE, "how do I stop the code from running with out shuting down
IDLE?"

Michael Schmitt