gistfile1.py

import time
import functools

def fib(n, fun=None):
    '''A naive fib function, taking the recursion callable as an argument'''
    if n == 0 or n == 1: return n
    fun = fun or fib
    return fun(n - 1) + fun(n - 2)

def fib2(n):
    '''A non-recursive fib implementation'''
    if n == 0 or n == 1: return n
    t = [0, 1]
    for i in xrange(n):
        t.append(t[-1] + t[-2])
    return t[-2]

def memoize_dict(fun):
    '''A memoization decorator using a dict as storage'''
    mem = dict()
    @functools.wraps(fun)
    def wrapped(arg):
        value = mem.get(arg)
        if value is not None:
            return value
        value = fun(arg, wrapped)
        mem[arg] = value
        return value

    return wrapped

def memoize_constant_list(n, fun):
    '''A memoization decorator using a fixed-size list as storage'''
    mem = [None] * n
    @functools.wraps(fun)
    def wrapped(arg):
        value = mem[arg]
        if value is not None:
            return value
        value = fun(arg, wrapped)
        mem[arg] = value
        return value

    return wrapped

def timed(prefix, fun):
    '''A timing function for simple benchmarking

    No best-out-of-three or whatsoever implemented here
    '''
    print prefix,
    sys.stdout.flush()
    start = time.time()
    print fun()
    end = time.time()
    print 'Calculation took', (end - start), 'seconds'

def counter(fun):
    '''
    A decorator allowing to count the number of calls in a recursive algorithm
    '''
    holder = [0]
    @functools.wraps(fun)
    def helper(arg):
        holder[0] += 1
        return fun(arg, helper)

    @functools.wraps(fun)
    def wrapped(arg):
        value = helper(arg)
        return value, holder[0]

    return wrapped

if __name__ == '__main__':
    import sys
    num_simple = int(sys.argv[1]) if len(sys.argv) > 1 else 30
    num_optimized = int(sys.argv[2]) if len(sys.argv) > 2 else 120

    timed('fib(%d) =' % num_simple, lambda: fib(num_simple))
    print

    print 'Calculating the amount of recursive calls to calculate fib(%d)' % \
            num_simple
    counted_fib = counter(fib)
    value, count = counted_fib(num_simple)
    print 'Calculating fib(%d) =' % num_simple, value, 'took', count, 'calls'
    print

    timed('fib2(%d) =' % num_optimized, lambda: fib2(num_optimized))
    print

    memoize_dict_fib = memoize_dict(fib)
    timed('memoize_dict(fib)(%d) =' % num_optimized,
          lambda: memoize_dict_fib(num_optimized))
    print

    memoize_constant_list_fib = memoize_constant_list(num_optimized + 1, fib)
    timed('memoize_constant_list(%d, fib)(%d) =' % (num_optimized + 1,
                                                    num_optimized),
          lambda: memoize_constant_list_fib(num_optimized))