Memoización explicada visualmente: cuándo recordar cambia la curva

Memoizar consiste en recordar la respuesta de una función para no resolver otra vez la misma pregunta. La técnica parece pequeña, pero puede eliminar miles o millones de llamadas repetidas cuando distintos caminos llegan a los mismos estados.

La condición es importante: misma entrada debe significar misma salida. Si el resultado depende del reloj, la red, permisos cambiantes o estado global mutable, ya no basta con guardar argumentos y respuestas.

Memoización no significa “guardar todo”. Significa reconocer cuándo una respuesta sigue siendo la misma.

01. Memoización en 30 segundos

Una función memoizada necesita cuatro decisiones:

1. Qué argumentos definen la pregunta.
2. Cómo reconocer la misma entrada.
3. Dónde vive el resultado guardado.
4. Cuándo deja de ser válido o debe liberarse.

Flujo de una función memoizada desde la entrada hasta un hit o miss de caché

El recorrido básico es directo: construyes una clave, buscas un resultado y, si no existe, calculas y guardas. La siguiente llamada equivalente se convierte en una lectura.

Memoización y caché no son sinónimos perfectos. La memoización es un caso específico: asocia los argumentos de una función determinista con su resultado. Una caché general puede representar datos remotos, usar TTL, invalidarse por eventos o compartirse entre servidores.

02. El problema no es calcular: es repetir estados

Fibonacci permite ver el problema con pocas líneas:

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Para obtener fib(6), la rama de fib(5) vuelve a pedir fib(4), fib(3) y fib(2). La rama derecha solicita varios de esos estados otra vez. Cada llamada individual es barata; la explosión aparece porque el árbol reconstruye subproblemas completos.

Árbol de Fibonacci con estados repetidos frente a estados únicos memoizados

La implementación ingenua suele describirse como O(2ⁿ) —una cota simple para un crecimiento cercano a φⁿ—. Al memoizar, el universo relevante deja de ser el número de caminos y pasa a ser el número de estados únicos: 0, 1, 2, …, n.

Esta transformación no ocurre por usar un Map. Ocurre porque el problema tiene subproblemas solapados. Si cada entrada aparece una sola vez, guardar resultados añade memoria sin evitar trabajo.

03. Top-down, tabulación y memoria constante

La versión top-down conserva la recursión y comparte un mapa durante toda la llamada principal:

function fibMemo(
  n: number,
  memo = new Map<number, number>([[0, 0], [1, 1]])
): number {
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const value = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, value);
  return value;
}

Cada estado se calcula una vez; las repeticiones se convierten en hits. Como el mapa por defecto se crea al comenzar cada invocación externa, acelera ese árbol recursivo, pero no comparte resultados entre llamadas independientes.

Bottom-up es tabulación, no memoización estricta. Construye los estados en orden y puede evitar la recursión:

function fibIterative(n: number): number {
  let previous = 0;
  let current = 1;

  for (let i = 0; i < n; i += 1) {
    [previous, current] = [current, previous + current];
  }

  return previous;
}

Comparación entre recursión ingenua, memoización top-down y tabulación bottom-up

Top-down resulta natural cuando solo visitas una parte de un espacio grande. Bottom-up suele ser más predecible cuando necesitas todos los estados y conoces un orden válido para construirlos.

04. La clave y la vida de la caché son el contrato

Con números o strings, un Map reconoce la igualdad por valor. Con objetos, reconoce identidad de referencia:

const cache = new Map<object, string>();

cache.set({ id: 7 }, "Ada");
cache.get({ id: 7 }); // undefined: es otro objeto

Si dos objetos diferentes deben representar la misma pregunta, necesitas una clave estable y explícita:

type PathQuery = {
  start: { x: number; y: number };
  goal: { x: number; y: number };
  mapVersion: number;
};

function pathKey(query: PathQuery) {
  const { start, goal, mapVersion } = query;
  return `${start.x}:${start.y}|${goal.x}:${goal.y}|v${mapVersion}`;
}

Anatomía de una clave de memoización completa y estable

La clave debe evitar colisiones, normalizar entradas equivalentes e incluir toda dependencia que cambie el resultado. También debes decidir el ámbito: una llamada, una petición, un componente o todo el proceso. Un Map persistente sin límite puede retener memoria indefinidamente; un WeakMap permite que claves basadas en objetos sean liberadas cuando ya no existen otras referencias.

05. Cuando recordar crea nuevos problemas

Memoizar cambia tiempo por memoria. Antes de hacerlo, revisa estos riesgos:

• Baja reutilización: si casi todas las claves son distintas, predominan los misses.
• Datos obsoletos: si el resultado cambia sin cambiar la clave, la función no era realmente determinista.
• Mutabilidad: devolver el mismo objeto permite que un consumidor altere la respuesta de los demás.
• Crecimiento: una función de larga vida puede acumular entradas sin límite.
• Concurrencia: dos solicitudes simultáneas pueden iniciar el mismo trabajo antes de que exista un resultado.

Para funciones asíncronas, guardar la promesa pendiente permite compartir trabajo en curso. Si la promesa falla, conviene retirarla para permitir un reintento:

function memoizeAsync<Args extends unknown[], Value>(
  fn: (...args: Args) => Promise<Value>,
  keyOf: (...args: Args) => string
) {
  const cache = new Map<string, Promise<Value>>();

  return (...args: Args) => {
    const key = keyOf(...args);
    const hit = cache.get(key);
    if (hit) return hit;

    const pending = fn(...args);
    cache.set(key, pending);
    pending.catch(() => cache.delete(key));
    return pending;
  };
}

Cuando necesitas TTL, LRU, invalidación por eventos, coherencia entre servidores o permisos dinámicos, el problema ya pertenece a una política de caché más amplia. La memoización sigue siendo la idea de reutilizar; la infraestructura decide durante cuánto tiempo es seguro hacerlo.

06. Checklist para decidir

Antes de memoizar, responde:

1. ¿La misma entrada produce siempre la misma salida?
2. ¿Las entradas se repiten con frecuencia real?
3. ¿El cálculo cuesta más que construir la clave y consultar el almacenamiento?
4. ¿La clave representa todas las dependencias?
5. ¿Dónde debe vivir la memoria y cuándo se libera?
6. ¿Un objeto devuelto puede mutar?
7. ¿Necesitas compartir una promesa pendiente o manejar reintentos?

Memoiza cuando puedas identificar un conjunto pequeño de estados repetidos dentro de una exploración mucho mayor. No lo hagas por reflejo alrededor de cualquier función: mide hits, misses, memoria y costo evitado.

La pregunta final no es “¿puedo guardar esta respuesta?”. Es “¿volveré a formular exactamente la misma pregunta y seguirá significando lo mismo?”.