Memoización

Memoización

La memoización es una técnica de optimización que consiste en cachear (guardar) el resultado de una función para unos argumentos dados, de modo que si se vuelve a llamar con los mismos argumentos no se recalcula: se devuelve el valor guardado. Es un caso particular de caché aplicado a funciones puras (las que siempre devuelven lo mismo para la misma entrada).

La idea con un Map y un closure

Guardamos los resultados en un Map que vive en un closure, privado a la función cacheada:

function memoize(fn) {
  const cache = new Map();
  return function (n) {
    if (cache.has(n)) {
      return cache.get(n); // ¡acierto de caché!
    }
    const resultado = fn(n);
    cache.set(n, resultado);
    return resultado;
  };
}

El caso clásico: Fibonacci

El fibonacci recursivo ingenuo es O(2ⁿ) porque recalcula los mismos valores una y otra vez. Con memoización pasa a ser lineal, O(n):

function fibonacci(n) {
  if (n < 2) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
const fibRapido = memoize(function (n) {
  if (n < 2) return n;
  return fibRapido(n - 1) + fibRapido(n - 2);
});

console.log(fibRapido(40)); // instantáneo; el ingenuo tardaría muchísimo

Memoizar tiene un coste en memoria: estás cambiando tiempo por espacio. Úsalo cuando los recálculos sean caros y los argumentos se repitan.

Ejemplos

Contar cuántas veces se ejecuta de verdad

function memoize(fn) {
  const cache = new Map();
  return function (n) {
    if (cache.has(n)) return cache.get(n);
    const r = fn(n);
    cache.set(n, r);
    return r;
  };
}
let llamadas = 0;
const cuadrado = memoize((n) => { llamadas++; return n * n; });
console.log(cuadrado(5));
console.log(cuadrado(5));
console.log(cuadrado(5));
console.log("Cálculos reales:", llamadas); // 1, gracias a la caché