Reusar respuestas ya resueltas
¿Has resuelto Fibonacci con recursion? Para obtener fib(5) llamas a fib(4) y fib(3), y fib(4) vuelve a llamar a fib(3) y fib(2). Pero fib(2) sigue apareciendo aqui y alla. Resuelves lo mismo una y otra vez. ¿Y si anotaras una respuesta resuelta en algun lado?
Resolver lo mismo de nuevo
La recursion resuelve un problema grande
partiendolo en chicos.
Fibonacci es justo eso.
fib(5) llama a fib(4) y fib(3),
fib(4) vuelve a llamar a fib(3) y fib(2).
Pero mira de cerca,
y fib(2) sigue apareciendo
en esta rama y en aquella.
En el arbol de abajo,
toca uno de los nodos.
El mismo problema chico aparece por todo el arbol. (Clic en un nodo → todos los mismos valores se resaltan)
¿Lo ves?
El mismo fib(2) se resuelve
no una vez sino varias.
Lo mismo con fib(3).
A medida que n crece,
esta duplicacion se dispara.
Resolver una respuesta que ya tienes
una y otra vez
es claramente un desperdicio.
Anota la respuesta
El arreglo es sorprendentemente simple.
Anota una respuesta resuelta
en un bloc de notas.
Cuando la misma se necesita otra vez,
no la recalcules,
solo sacala de la nota.
Calcula solo las nuevas,
saca de nuevo las ya vistas.
Pulsa el boton
para atender las llamadas una a una.
Calcula y anota lo nuevo, saca lo visto de la nota. (Esto es memoizacion)
El calculo ocurre solo la primera vez.
Todo lo demas
se saca de la nota,
asi que resolver lo mismo dos veces
desaparece por completo.
Anotar una respuesta resuelta
y reusarla asi
se llama memoizacion.
El nombre suena elegante,
pero por dentro es solo "anotarlo".
Llenar la tabla desde abajo
Puedes voltear la misma idea
al reves.
En vez de partir desde arriba,
llena la tabla hacia arriba
desde los valores chicos de abajo.
fib(0) y fib(1) simplemente los sabemos.
Sumalos para fib(2),
suma fib(1) y fib(2) para fib(3).
Las celdas de abajo ya estan escritas,
asi que la de arriba es solo una suma.
Llena hacia arriba una celda desde 0 y 1. (Celda siguiente = suma de las dos de abajo · de abajo hacia arriba)
Esta via ni siquiera necesita
un bloc de notas.
La tabla misma es la nota.
Ve de abajo hacia arriba
en una sola pasada,
y no hay nada que volver a resolver.
Si la memoizacion es
"anotalo cuando haga falta,"
esto es "anotalo todo de antemano."
Ambas significan lo mismo por dentro.
Se vuelve mucho mas rapido
¿Y cuanto mas rapido es?
La diferencia de un solo gesto,
anotarlo, es enorme.
La recursion pura
resuelve tambien todos los duplicados,
asi que a medida que n crece
el trabajo explota hacia arriba.
El memo resuelve cada celda una sola vez,
solo en proporcion a n.
Aumenta n y compara ambos.
Resoluciones al mismo n. (Recursion pura = estallido exponencial · memo = lineal en n)
¿Ves la diferencia?
Con apenas un poco mas de n,
la barra de recursion pura
se dispara fuera de la pantalla.
La barra del memo
se queda casi plana.
No resolver la misma respuesta otra vez,
esa sola cosa
es lo que separa lo lento de lo rapido.
Para cerrar
La programacion dinamica
tiene un nombre que asusta
pero por dentro son tres pasos.
Nota que resuelves lo mismo,
anota una respuesta resuelta,
reusala y se vuelve mucho mas rapido.
Toca las tarjetas de abajo una a una
para repasar los tres pasos.
Resolver de nuevo → anotar → mucho mas rapido. (Recuerda que el divide y venceras no se traslapaba, sin necesidad de memo)
En el divide y venceras de la vez pasada,
las piezas partidas no se traslapaban,
asi que no habia nada que anotar.
Ese es justo el cruce de caminos.
Cuando las piezas se traslapan,
es decir, cuando el mismo problema chico
sigue regresando,
ahi es cuando el solo gesto
de anotarlo lo cambia todo.