Respuesta.

Historia de la pregunta:

La memoización es una técnica de optimización ampliamente utilizada en programación funcional, cálculos recursivos y programación dinámica, cuando las mismas funciones se llaman repetidamente con los mismos argumentos. En Python, se popularizó con la aparición del decorador functools.lru_cache y patrones de almacenamiento en caché de resultados de cálculos.

Problema:

Sin almacenamiento en caché, las funciones recursivas tipo cálculo de números de Fibonacci funcionan muy lentamente: para cada argumento, los cálculos se repiten muchas veces, lo que lleva a un crecimiento exponencial en el número de llamadas.

Solución:

La memoización guarda los valores ya calculados (por ejemplo, en un diccionario), para volver a utilizarlos cuando sea necesario:

Ejemplo de implementación manual:

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

Desde Python 3.2, se puede usar simplemente el decorador:

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

Características clave:

Permite acelerar funciones recursivas o computacionalmente costosas sin cambiar su lógica.
La implementación puede ser manual (en un diccionario) o automática (a través de lru_cache).
Se debe tener cuidado con los argumentos mutables, ya que lru_cache solo funciona con argumentos hasheables (inmutables).

Preguntas capciosas.

¿Se puede memoizar una función con argumentos mutables (por ejemplo, listas)?

No, lru_cache requiere que todos los argumentos sean hasheables (inmutables), de lo contrario se producirá un TypeError.

from functools import lru_cache

@lru_cache
# def f(a): return a[0]  # TypeError: unhashable type: 'list'

¿Se eliminan automáticamente los valores memoizados?

Sí, si se establece maxsize, los valores que superen el límite se eliminan (Least Recently Used). Una caché infinita (maxsize=None) puede llevar a desbordamiento de memoria.

¿Qué pasará si una función memoizada se llama a sí misma con nuevos argumentos?

La memoización seguirá funcionando: para cada conjunto único de argumentos, el resultado se calcula una sola vez y se almacena en caché.

Errores típicos y antipatrón

Usar memoización sin limitación del caché y desbordar la memoria.
Intentar memoizar funciones con argumentos mutables.
Olvidar limpiar la caché cuando ya no se necesita.

Ejemplo de la vida real

Caso negativo

Se escribe un propio caché sin limitación de tamaño:

cache = {}
def foo(x):
    if x not in cache:
        cache[x] = long_heavy_computation(x)
    return cache[x]

Con el tiempo, el programa utiliza gigabytes de memoria.

Pros:

Funciona rápidamente para llamadas repetidas.

Contras:

Crecimiento ilimitado de memoria.
Posible Out of Memory.

Caso positivo

Uso de lru_cache con maxsize:

from functools import lru_cache

@lru_cache(maxsize=1000)
def foo(x):
    return long_heavy_computation(x)