Python memoization decorator

Memoização , se você ainda não estiver familiarizado com ela, é uma maneira de armazenar em cache os resultados das chamadas de função para evitar a repetição do trabalho.

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)

Por exemplo, computar a sequência de Fibonacci da maneira recursiva ingênua resulta em uma tonelada de cálculos repetidos.

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

fib(35)leva cerca de 10 segundos para ser executado na minha máquina. A sequência recursiva de Fibonacci escala em O (2 ^ N) (embora este seja um limite superior ).

Se usarmos a memoização, isso é reduzido para cerca de um milissegundo e podemos calcular rapidamente valores muito maiores.

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

>>> fib(100)
354224848179261915075L