fibonacci com memoizatino

fib.py

import timeit


def memoize(fn):
    cache = {}
    def newfn(arg):
        if arg in cache:
            return cache[arg]
        else:
            cache[arg] = fn(arg)
            return cache[arg]
    return newfn


def fib(n):
    if n in (1, 2):
        return 1
    return fib(n - 1) + fib(n - 2)


def fast_fib(n):
    if n in (1, 2):
        return 1
    return fast_fib(n - 1) + fast_fib(n - 2)


fast_fib = memoize(fast_fib)


if __name__ == '__main__':
    print timeit.timeit("import fib; fib.fib(35)", number=1)
    print timeit.timeit("import fib; fib.fast_fib(35)", number=1)

# 3.71057915688
# 0.000109195709229