gistfile1.py

import itertools


test_strings = {}

def make_harness(args, base_setup, default_run="{0}", default_setup=''):
    """ Creates a decorator to create command strings for timeit.Timer """
    def test(run=default_run, setup=default_setup):
        def dec(f):
            name = f.__name__
            strings = (run.format(name + args),
                       base_setup + name + setup)
            test_strings[name] = strings
            return f
        return dec
    return test

test = make_harness('(today, yesterday)',
                    'from deltas import today, yesterday, ')

@test("dict({0})")
def get_deltas_aas(today, yesterday):
    deltas = {}
    for (new_rank, new_album), (old_rank, old_album) in \
            itertools.izip(enumerate(today), enumerate(yesterday)):
        if old_album in deltas:
            yield (old_album, deltas[old_album] + old_rank)
            del deltas[old_album]
        else:
            deltas[old_album] = old_rank

        if new_album in deltas:
            yield (new_album, deltas[new_album] - new_rank)
            del deltas[new_album]
        else:
            deltas[new_album] = -new_rank


@test()
def get_deltas_gnibbler(today, yesterday):
    D = dict((k,v) for v,k in enumerate(yesterday))
    return dict((k,D[k]-v) for v,k in enumerate(today))


class LookupOnce:
    def __init__(self, seq):
        self.cache = {}
        self.seq = iter(seq)
    def get(self, key):
        if key in self.cache:
            value = self.cache[key]
            del self.cache[key]
            return value
        for v,k in self.seq:
            if k == key:
                return v
            self.cache[k] = v
        raise KeyError

@test(setup=", LookupOnce")
def get_deltas_token2(a, b):
    rank_a = LookupOnce(enumerate(a))
    rank_b = enumerate(b)
    result = {}
    for i, k in rank_b:
        result[k] = i - rank_a.get(k)
    return result

@test()
def get_deltas_token1(a, b):
    rank_a = dict((k, v) for v, k in enumerate(a))
    rank_b = enumerate(b)
    return dict((k, rank_a[k]-i) for i, k in rank_b)


def transform(albums):
    return dict((album, i) for i, album in enumerate(albums))
 
@test("dict({0})", ', transform')
def get_deltas_hughdbrown(album1, album2):
    album_dict1, album_dict2  = transform(album1), transform(album2)
    for k, v in sorted(album_dict1.iteritems()):
         yield k, album_dict2[k] - v

@test()
def get_deltas_tyler(today,yesterday):
    results = {}
    ypos = 0
    for i,title in enumerate(today):
        if title in results:
            results[title] = results[title] - i
        else:
            for ypos in xrange(ypos,len(yesterday)):
                if yesterday[ypos] == title:
                    results[title] = ypos - i
                    ypos = ypos + 1
                    break
                else:
                    results[yesterday[ypos]] = ypos
    return results


# data
today = map(str, range(1000))
yesterday = today[:]

if __name__=='__main__':
    import timeit
    import types
    import random
    

    # book keeping
    results = dict((name, 0) for name in test_strings)


####### Settings ###########
    # utility functions to prepare data
    prepare_yesterday = random.shuffle
    prepare_today = random.shuffle

    iterations = 100

    show_debug = False

##########################

    for _ in xrange(iterations):
        prepare_yesterday(yesterday)
        prepare_today(today)

        for name, (command, setup) in test_strings.items():
            t = timeit.Timer(command, setup)
            results[name] += 1000 * t.timeit(number=10)/10

    for name, result in results.items():
        
        if show_debug: print "{1}\n{0}".format(*test_strings[name])
        print "{0}: {1} msecs".format(name, result/iterations)