Python memoization decorator

Memoization, if you aren't already familiar with it, is a way to cache results of function calls to avoid repeating work.

from functools import wraps
def memoize(f):
    """A hacky memoize method decorator."""
    def _c(*args, **kwargs):
        if not hasattr(f, 'cache'):
            f.cache = dict()
        key = (args, tuple(kwargs))
        if key not in f.cache:
            f.cache[key] = f(*args, **kwargs)
        return f.cache[key]
    return wraps(f)(_c)

For example, computing the Fibonacci sequence in the naive recursive way results in a ton of repeated computations.

def fib(x):
    if x <= 0:
        return 0
    if x == 1:
        return 1
    return fib(x - 1) + fib(x - 2)

fib(35) takes about 10 seconds to run on my machine. The recursive Fibonacci sequence scales at O(2^N) (though this is an upper bound).

If we use memoization, this is reduced to about a millisecond, and we can quickly compute much larger values.

@memoize
def fib(x):
    if x <= 0:
        return 0
    if x == 1:
        return 1
    return fib(x - 1) + fib(x - 2)

>>> fib(100)
354224848179261915075L