Memoization en JavaScript

Se trata de una técnica que mejora el rendimiento de una función utilizando una caché para guardar los resultados de invocaciones previas. De esta forma, cuando se vuelve a llamar a la función con el mismo parámetro, se devuelve el resultado de la caché, sin necesidad de recalcular de nuevo.

En realidad estamos mejorando el tiempo de respuesta de la funcion a cambio de ocupar más espacio de memoria. Los resultados se van guardando en un tabla hash (un objeto) indexados por el parámetro o parámetros con los que se ha producido ese resultado.

Podemos limitar el tamaño del objeto de resultados a un máximo e incluir algun algoritmo de sustitución de entradas. En algunos casos puede ser conveniente tener una tabla de resultados fija, inicializada de antemano, con los argumentos que sabemos que se van a dar en una amplia mayoría de las llamadas.

Ejemplo. Factorial de un número

Como sabemos el factorial se define por:

0! = 1
n! = n * (n-1)!

Podemos hacerlo con una función recursiva muy sencilla:

function factorial (n) {
  if (n <= 0) return 1;
  return n * factorial(n-1);
}

Este es un ejemplo de función que se beneficiaría enormemente si utilizaramos memoization para cachear resultados de operaciones anteriores.

Si hacemos factorial(3)la función tendrá que hacer el calculo, pero si luego hacemos factorial(5) de nuevo tendra que calcular ( recursivamente ) el factorial de 4, de 3, de 2 y de 1. Como el factorial de 3 ya lo hemos calculado antes, podriamos aprovecharlo ahorrando procesamiento.

Para aprovechar los calculos anteriores introducimos una caché local que almacenará los resultados.

var cache = {};

function factorial (n) {
    
    if (n <= 0) return 1;
    
    if ( cache[n] ) {
        return cache[n];
    }
    else {  
        cache[n] =  n * factorial(n-1);
        return n * factorial(n-1);
    }   
}

Hemos utilizado una cache externa porque debe permanecer cuando la función haya terminado. Podemos aprovechar que en JavaScript las funciones son también objetos para definir la caché como una propiedad de la función:

function factorial (n) {

    //creamos nuestra cache solamente si no está ya definida
    if ( !factorial.cache ) factorial.cache = {};
    
    if (n <= 0) return 1;
  
    if (factorial.cache[n]) {
        return factorial.cache[n];
    }
    else {
        factorial.cache[n] =  n * factorial(n-1);
        return factorial.cache[n];
  }     
}

Cuando la función tiene varios parámetros tenemos que combinarlos de alguna forma para formar un indice único y válido en la tabla de resultados.

En proyectos grandes, con muchos métodos apropiadas para aplicarles esta técnica, es util crear una función memoizadora a la que pasamos nuestra función y nos devuelve una nueva, igual que la original, pero con memoization.

Fuentes:
Implementing memoization in JavaScript
JavaScript Memoization
Speed-up your JavaScript
Memoization. Una primera mirada