Memoização

Memoização

A memoização é uma técnica de otimização que consiste em cachear (guardar) o resultado de uma função para determinados argumentos, de modo que se ela for chamada de novo com os mesmos argumentos não seja recalculada: retorna-se o valor guardado. É um caso particular de cache aplicado a funções puras (as que sempre retornam o mesmo para a mesma entrada).

A ideia com um Map e um closure

Guardamos os resultados em um Map que vive em um closure, privado à função cacheada:

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

O caso clássico: Fibonacci

O fibonacci recursivo ingênuo é O(2ⁿ) porque recalcula os mesmos valores uma e outra vez. Com memoização passa a ser linear, 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; o ingênuo demoraria muitíssimo

Memoizar tem um custo em memória: você está trocando tempo por espaço. Use quando os recálculos forem caros e os argumentos se repetirem.

Exemplos

Contar quantas vezes realmente executa

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 chamadas = 0;
const quadrado = memoize((n) => { chamadas++; return n * n; });
console.log(quadrado(5));
console.log(quadrado(5));
console.log(quadrado(5));
console.log("Cálculos reais:", chamadas); // 1, graças ao cache