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