Hay varios artículos excelentes que hablan de la técnica de optimización llamada memoización. Puedes acceder a ellos aquí y aquí. Lo que vamos a hacer es dar un breve repaso a lo que es la memoización. Iremos un poco más allá realizando un análisis paso a paso de lo que realmente hace el código «memoizado», línea a línea. Al final del artículo, entenderás completamente la memoización.
La memoización es la práctica programática de hacer que las funciones recursivas/iterativas largas se ejecuten mucho más rápido.
¿Cómo, te preguntarás? Almacenando en la caché los valores que la función devuelve tras su ejecución inicial.
Cuando introducimos el mismo valor en nuestra función memoizada, ésta devuelve el valor almacenado en la caché en lugar de volver a ejecutar la función, lo que aumenta el rendimiento. Ya no es necesario que tu programa recalcule cada número para obtener un resultado.
Suena increíble, ¿verdad? Bueno, lo que es aún mejor es que no es difícil entender lo que una función memoize está haciendo una vez que se descompone el código.
Aquí está un ejemplo de una función básica memo:
Empecemos desde el principio…
Estamos devolviendo lo que se llama un cierre anónimo. Nuestro cierre anónimo es capaz de heredar cualquier variable o, en este caso, función pasada a memo. Podemos entonces jugar con el objeto de argumentos que nuestra función pasada proporciona.
Nota al margen: Entonces, si cada función tiene un objeto de argumentos, ¿por qué no estamos heredando el objeto de argumentos de memo? Eso es porque, como regla, los cierres no heredan el objeto de argumentos de una función externa. Usamos esta regla a nuestro favor para jugar con la función que queremos memoizar.
Desglosemos exactamente lo que hace la memoización viendo un ejemplo muy simple y poco práctico. Por cierto, deberías copiar/pegar este código, o cualquier código para el caso, para realmente tener una idea de cómo funciona.
Creo que tenemos la esencia de este ejemplo de código. Prácticamente habla por sí mismo. Vamos a profundizar un poco más viendo una instantánea de nuestra función memo real:
Ahora que hemos desglosado lo que hace una función memo, vamos a crear una expresión de función y a pasar una función Fibonacci recursiva en memo y a ver qué pasa.
//Now we'll test our code!
// =======TEST=======
fib(10)//On the first try we need to load//=> loading…//=> loading…//=> loading…//=> loading…//=> loading…//=> 4 loadings later we get...//=> 89// And on the second try…fib(10)//=> 89//No loading! Yaay!//The cool thing about memoizing the recursive Fibonacci algorithm is that once we make a call for the value of the nth number in the series, we are able to store all the previous numbers in the series.//So if we try...
fib(7) //=> 21
//We don't have to recalculate anything.//And if we want to try fib(11)...
fib(11)
//loading...
//=> 144
//Our memoized recursive function already cached fib(1-10),so all it needed to do was to calculate the cached values. // This is what the cache now looks like:
/*
{ '{"0":0}': 1,
'{"0":1}': 1,
'{"0":2}': 2,
'{"0":3}': 3,
'{"0":4}': 5,
'{"0":5}': 8,
'{"0":6}': 13,
'{"0":7}': 21,
'{"0":8}': 34,
'{"0":9}': 55,
'{"0":10}': 89,
'{"0":11}': 144}
*/
Conclusión
La memorización se desmitifica cuando se reduce a pares clave-valor. Todo lo que estamos haciendo es crear un objeto, comprobar los valores existentes que coinciden con la entrada del usuario, y almacenar nuevos pares clave-valor si no existen en nuestro objeto.
Por supuesto, almacenar todos estos datos significa que vamos a utilizar la memoria. Es mejor implementar la memoización en funciones que sean puras y que impliquen cálculos pesados y repetitivos.
Bonus:
Sólo por diversión, aquí tenemos una versión funcional de nuestro memoizador: