¿Qué es la memoización y cómo puedo usarla en Python?

Acabo de empezar con Python y no tengo idea de qué es la memoización y cómo usarla. Además, ¿puedo tener un ejemplo simplificado?

La memorización se refiere efectivamente a recordar los resultados de las llamadas a métodos (“memoización” → “memorándum” → a recordar) y luego devolver el resultado recordado en lugar de volver a calcular el resultado. Puedes considerarlo como un caché para los resultados del método. Para más detalles, consulte la página 387 para la definición en Introducción a los algoritmos (3e), Cormen et al.

Un ejemplo simple para calcular factoriales utilizando la memorización en Python sería algo como esto:

factorial_memo = {} def factorial(k): if k < 2: return 1 if k not in factorial_memo: factorial_memo[k] = k * factorial(k-1) return factorial_memo[k] 

Puedes complicarte más y encapsular el proceso de memorización en una clase:

 class Memoize: def __init__(self, f): self.f = f self.memo = {} def __call__(self, *args): if not args in self.memo: self.memo[args] = self.f(*args) #Warning: You may wish to do a deepcopy here if returning objects return self.memo[args] 

Entonces:

 def factorial(k): if k < 2: return 1 return k * factorial(k - 1) factorial = Memoize(factorial) 

Se añadió una característica conocida como " decoradores " en Python 2.4 que le permite ahora simplemente escribir lo siguiente para lograr lo mismo:

 @Memoize def factorial(k): if k < 2: return 1 return k * factorial(k - 1) 

La biblioteca de Python Decorator tiene un decorador similar llamado memoized que es ligeramente más robusto que la clase Memoize muestra aquí.

Nuevo en Python 3.2 es functools.lru_cache . De forma predeterminada, solo almacena en caché las 128 llamadas utilizadas más recientemente, pero puede establecer el maxsize en None para indicar que el caché nunca debe caducar:

 import functools @functools.lru_cache(maxsize=None) def fib(num): if num < 2: return num else: return fib(num-1) + fib(num-2) 

Esta función por sí misma es muy lenta, intente con fib(36) y tendrá que esperar unos diez segundos.

La lru_cache anotación lru_cache garantiza que si la función se ha llamado recientemente para un valor particular, no volverá a calcular ese valor, sino que usará un resultado anterior en caché. En este caso, conduce a una tremenda mejora de la velocidad, mientras que el código no está saturado con los detalles del almacenamiento en caché.

Las otras respuestas cubren lo que está bastante bien. No estoy repitiendo eso. Sólo algunos puntos que podrían ser útiles para usted.

Por lo general, la memoria es una operación que puede aplicar a cualquier función que calcule algo (costoso) y devuelva un valor. Debido a esto, a menudo se implementa como un decorador . La implementación es sencilla y sería algo así.

 memoised_function = memoise(actual_function) 

o expresado como un decorador

 @memoise def actual_function(arg1, arg2): #body 

La memorización es mantener los resultados de cálculos costosos y devolver el resultado almacenado en caché en lugar de recalcularlo continuamente.

Aquí hay un ejemplo:

 def doSomeExpensiveCalculation(self, input): if input not in self.cache:  self.cache[input] = result return self.cache[input] 

Se puede encontrar una descripción más completa en la entrada de wikipedia sobre memoización .

No olvidemos la función hasattr incorporada, para aquellos que quieren hacer manualidades. De esa manera puede mantener la memoria caché de mem dentro de la definición de la función (en lugar de una global).

 def fact(n): if not hasattr(fact, 'mem'): fact.mem = {1: 1} if not n in fact.mem: fact.mem[n] = n * fact(n - 1) return fact.mem[n] 

He encontrado esto extremadamente útil

 def memoize(function): from functools import wraps memo = {} @wraps(function) def wrapper(*args): if args in memo: return memo[args] else: rv = function(*args) memo[args] = rv return rv return wrapper @memoize def fibonacci(n): if n < 2: return n return fibonacci(n - 1) + fibonacci(n - 2) fibonacci(25) 

La memorización consiste básicamente en guardar los resultados de las operaciones anteriores realizadas con algoritmos recursivos para reducir la necesidad de atravesar el árbol de recursiones si se requiere el mismo cálculo en una etapa posterior.

vea http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Ejemplo de memorización de Fibonacci en Python:

 fibcache = {} def fib(num): if num in fibcache: return fibcache[num] else: fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2) return fibcache[num] 

La memoización es la conversión de funciones en estructuras de datos. Por lo general, uno quiere que la conversión se realice de forma incremental y perezosa (a petición de un elemento de dominio determinado, o “clave”). En los lenguajes funcionales perezosos, esta conversión perezosa puede suceder automáticamente y, por lo tanto, la memoria puede implementarse sin efectos secundarios (explícitos).

Bueno, debería responder la primera parte primero: ¿qué es la memoria?

Es solo un método para intercambiar memoria por tiempo. Piensa en la tabla de multiplicación .

El uso de objetos mutables como valor predeterminado en Python generalmente se considera malo. Pero si lo usa con prudencia, en realidad puede ser útil para implementar una memoization .

Aquí hay un ejemplo adaptado de http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

Al usar un dict mutable en la definición de la función, los resultados calculados intermedios se pueden almacenar en caché (por ejemplo, al calcular factorial(10) después de calcular factorial(9) , podemos reutilizar todos los resultados intermedios)

 def factorial(n, _cache={1:1}): try: return _cache[n] except IndexError: _cache[n] = factorial(n-1)*n return _cache[n] 

Aquí hay una solución que funcionará con los argumentos de tipo list o dict sin quejarse:

 def memoize(fn): """returns a memoized version of any function that can be called with the same list of arguments. Usage: foo = memoize(foo)""" def handle_item(x): if isinstance(x, dict): return make_tuple(sorted(x.items())) elif hasattr(x, '__iter__'): return make_tuple(x) else: return x def make_tuple(L): return tuple(handle_item(x) for x in L) def foo(*args, **kwargs): items_cache = make_tuple(sorted(kwargs.items())) args_cache = make_tuple(args) if (args_cache, items_cache) not in foo.past_calls: foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs) return foo.past_calls[(args_cache, items_cache)] foo.past_calls = {} foo.__name__ = 'memoized_' + fn.__name__ return foo 

Tenga en cuenta que este enfoque puede extenderse naturalmente a cualquier objeto implementando su propia función hash como un caso especial en handle_item. Por ejemplo, para hacer que este enfoque funcione para una función que toma un conjunto como un argumento de entrada, podría agregarlo a handle_item:

 if is_instance(x, set): return make_tuple(sorted(list(x))) 

Solución que funciona con argumentos de palabras clave y posicionales independientemente del orden en que se pasaron los argumentos de palabras clave (utilizando inspect.getargspec ):

 import inspect import functools def memoize(fn): cache = fn.cache = {} @functools.wraps(fn) def memoizer(*args, **kwargs): kwargs.update(dict(zip(inspect.getargspec(fn).args, args))) key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args) if key not in cache: cache[key] = fn(**kwargs) return cache[key] return memoizer 

Pregunta similar: la identificación de las funciones de varargs equivalentes para la memorización en Python

 cache = {} def fib(n): if n <= 1: return n else: if n not in cache: cache[n] = fib(n-1) + fib(n-2) return cache[n] 

Solo quería agregar a las respuestas ya proporcionadas, la biblioteca de decoradores de Python tiene algunas implementaciones simples pero útiles que también pueden memorizar “tipos no lavables”, a diferencia de functools.lru_cache .