¿Qué es la memorización y cómo puedo usarla en Python?
Acabo de empezar con Python y no tengo idea de qué es la memorización y cómo usarla. Además, ¿puedo darme un ejemplo simplificado?
La memorización se refiere efectivamente a recordar ("memorización" → "memorando" → para recordar) los resultados de las llamadas a métodos en función de las entradas del método y luego devolver el resultado recordado en lugar de calcular el resultado nuevamente. Puedes considerarlo como un caché para los resultados del método. Para obtener más detalles, consulte la página 387 para conocer la definición en Introducción a los algoritmos (3e), Cormen et al.
Un ejemplo sencillo para calcular factoriales usando 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)
En Python 2.4 se agregó una característica conocida como " decoradores " que ahora le permite 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 decoradores de Python tiene un decorador similar llamado memoizedque es un poco más robusto que la Memoizeclase que se muestra aquí.
functools.cachedecorador:
Python 3.9 lanzó una nueva función functools.cache. Almacena en memoria caché el resultado de una función llamada con un conjunto particular de argumentos, lo cual es memorización. Es fácil de usar:
import functools
import time
@functools.cache
def calculate_double(num):
time.sleep(1) # sleep for 1 second to simulate a slow calculation
return num * 2
La primera vez que llame caculate_double(5), tomará un segundo y devolverá 10. La segunda vez que llame a la función con el mismo argumento calculate_double(5), devolverá 10 al instante.
Agregar el cachedecorador garantiza que si la función ha sido llamada recientemente para un valor particular, no volverá a calcular ese valor, sino que utilizará un resultado anterior almacenado en caché. En este caso, esto conduce a una enorme mejora en la velocidad, mientras que el código no está saturado con los detalles del almacenamiento en caché.
( Editar : el ejemplo anterior calculó un número de Fibonacci mediante recursividad, pero cambié el ejemplo para evitar confusiones, de ahí los comentarios anteriores).
functools.lru_cachedecorador:
Si necesita admitir versiones anteriores de Python, functools.lru_cachefunciona en Python 3.2+. De forma predeterminada, solo almacena en caché las 128 llamadas utilizadas más recientemente, pero puede configurar maxsizepara Noneindicar que el caché nunca debe caducar:
@functools.lru_cache(maxsize=None)
def calculate_double(num):
# etc
Las otras respuestas cubren bastante bien lo que es. No voy a repetir eso. Sólo algunos puntos que podrían resultarle útiles.
Por lo general, la memorización es una operación que puede aplicar a cualquier función que calcule algo (caro) y devuelva un valor. Debido a esto, a menudo se implementa como decorador . La implementación es sencilla y sería algo como esto.
memoised_function = memoise(actual_function)
o expresado como decorador
@memoise
def actual_function(arg1, arg2):
#body
