El mismo cálculo, otra vez
La memoización guarda el resultado de cada cálculo para no repetirlo. Convierte una recursividad muy lenta en una rápida con muy poco cambio.
Un cajero debe devolver 15 céntimos con las monedas que tiene. Al probar combinaciones, calcularía cien veces el cambio de 5 céntimos. Basta calcularlo una vez y apuntar el resultado.
Al final de esta lección
Nota
Puedo acelerar una recursividad lenta guardando las respuestas que ya conozco.
Palabras clave
| Palabra | Qué significa | Ejemplo |
|---|---|---|
| Memoización | guardar un resultado para no calcularlo otra vez | |
| Trabajo repetido | el mismo cálculo hecho muchas veces | |
| Tabla de resultados | el diccionario donde se guardan los resultados | |
| Fibonacci | cada número es la suma de los dos anteriores | 0, 1, 1, 2, 3, 5 |
| Cambio de monedas | dar una cantidad con el menor número de monedas |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Fibonacci recursivo repite cálculos
Para calcular fib(5), la función calcula fib(4) y fib(3). Pero fib(4) calcula otra vez fib(3). Y fib(3) calcula fib(2) más de una vez.
Cada resultado se recalcula muchas veces. Por eso fib(27) necesita 635.621 llamadas, aunque solo hay 28 resultados distintos.
Veces que se calcula cada fib(n)
| Llamada | Veces que se calcula |
|---|---|
| fib(5) | 1 |
| fib(4) | 1 |
| fib(3) | 2 |
| fib(2) | 3 |
| fib(1) | 5 |
| fib(0) | 3 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Escribe la versión lenta en slow.py
printf "calls = 0\ndef f(n):\n global calls\n calls = calls + 1\n if n < 2:\n return n\n return f(n - 1) + f(n - 2)\nprint(f(27), calls)\n" > slow.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Ejecuta la versión lenta
python3 slow.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
La memoización guarda cada resultado
La idea es sencilla. Antes de calcular, mira en un diccionario si ya tienes la respuesta. Si la tienes, la devuelves. Si no, la calculas y la guardas.
Cada resultado se calcula una sola vez. El número de pasos pasa de crecer muy deprisa a crecer con n.
Fibonacci con un diccionario de memoria
# Fibonacci con memoria: cada resultado se guarda en un diccionario.
calls = 0
memo = {}
def fib(n):
global calls
calls = calls + 1
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(30), "con", calls, "llamadas")
# Sin memoria, fib(30) haría 2.692.537 llamadas.
Escribe la versión con memoria en fast.py
printf "calls = 0\nmemo = {}\ndef f(n):\n global calls\n calls = calls + 1\n if n in memo:\n return memo[n]\n if n < 2:\n return n\n memo[n] = f(n - 1) + f(n - 2)\n return memo[n]\nprint(f(27), calls)\n" > fast.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Ejecuta la versión con memoria
python3 fast.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que memoizar cambia el resultado. No cambia nada: la respuesta es la misma. Solo evita repetir cálculos. Sirve cuando el mismo subproblema aparece muchas veces; si nunca se repite, la memoria no ayuda.
El cambio de monedas también repite trabajo
Para dar 15 céntimos con monedas de 1, 5 y 12, pruebas cada moneda y resuelves el resto. El resto, por ejemplo 10, aparece por muchos caminos.
Elegir siempre la moneda mayor no basta: 12 más tres de 1 son cuatro monedas, pero tres de 5 son solo tres. Hay que probar todas, y la memoria evita repetir.
Menos monedas, con memoria
# Menos monedas para devolver un cambio, con memoria.
coins = [1, 5, 12]
memo = {}
def fewest(amount):
if amount == 0:
return 0
if amount in memo:
return memo[amount]
best = 1000
for coin in coins:
if coin <= amount:
tries = fewest(amount - coin) + 1
if tries < best:
best = tries
memo[amount] = best
return best
print(fewest(15))
# Prueba con 20 y con 23.