Programación dinámica y memoización en JavaScript

Problema

El plan de carga

Un mensajero va en un scooter eléctrico por una ruta de n km. Hay una estación de carga en cada kilómetro, y la batería dura como máximo 2 km. Así que desde cada parada el mensajero avanza 1 o 2 km hasta la siguiente. En cada estación donde se detiene, paga su tarifa. Las tarifas son distintas, y la aplicación tiene que encontrar el plan más barato.

La primera solución piensa hacia atrás. La última parada es el km n. Antes, el mensajero estaba en el km n − 1 o en el km n − 2. Así que lo más barato hasta n es la tarifa en n más lo más barato de los dos: lo más barato hasta n − 1 y lo más barato hasta n − 2. Eso es recursión, como en la lección «Recursión». Las tarifas están en céntimos, y el contador dice cuántas veces se llamó a la función:

let calls = 0;

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapest(fee, i) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  const oneBack = cheapest(fee, i - 1);
  const twoBack = cheapest(fee, i - 2);
  return fee[i] + Math.min(oneBack, twoBack);
}

for (const km of [10, 30]) {
  calls = 0;
  const cost = cheapest(fees(km), km);
  console.log(`${km} km: ${cost} céntimos, ${calls} llamadas`);
}

10 km: 381 céntimos, 177 llamadas
30 km: 1217 céntimos, 2692537 llamadas

La respuesta es correcta, pero para 30 km se llamó a la función 2 692 537 veces. Para 50 km se llamaría 40 730 022 147 veces: a mil millones de llamadas por segundo es más de medio minuto, y una ruta de mensajero puede tener 100 km.

La idea

La misma pregunta, hecha millones de veces

¿Por qué tantas? Sigue quién pregunta qué. Lo más barato hasta el km 30 pregunta por el km 29 y el km 28. El km 29 pregunta por 28 y 27. El km 28 se pregunta dos veces, y cada vez se calcula desde cero, junto con todo lo que hay debajo. Más abajo las repeticiones se acumulan: el km 27 se pregunta tres veces, el km 26 cinco veces.

El ejemplo limpio de esto son los números de Fibonacci: cada uno es la suma de los dos anteriores, 0, 1, 1, 2, 3, 5, 8… La función tiene la misma forma, los dos más pequeños y una suma:

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

fib(30) = 832040, 2692537 llamadas

El número de llamadas es el mismo hasta la última cifra, porque el árbol de llamadas es el mismo. Y el plan es solo uno de muchos lugares con este árbol.

Estos subproblemas se llaman superpuestos: el mismo problema más pequeño lo necesitan varios más grandes. En divide y vencerás no es así. El ordenamiento por mezcla parte los pedidos en dos mitades que no comparten ni un solo pedido, y cada trozo se resuelve una vez. Aquí «lo más barato hasta el km 28» lo necesitan el km 29 y el km 30.

Míralo

El árbol y la memoria

Todo el árbol de llamadas para 6 km, y luego lo mismo con memoria. Fíjate en qué cajas se repiten y qué les pasa en cuanto se recuerda su respuesta:

function cheapestMemo(fee, i, memo) {
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

function cheapestPair(fee) {
  let twoBack = fee[0];
  let oneBack = fee[1];
  for (let i = 2; i < fee.length; i++) {
    const here = fee[i] + Math.min(oneBack, twoBack);
    twoBack = oneBack;
    oneBack = here;
  }
  return oneBack;
}

Paso a paso, en palabras

Cada caja es una llamada cheapest(k): lo más barato hasta el km k. cheapest(6) pregunta por 5 y 4, y cada uno de ellos pregunta por otros dos más pequeños.
El árbol se detiene en el km 1 y 0, donde la respuesta es la propia tarifa. Para 6 km son 25 llamadas.
Las mismas preguntas una y otra vez: cheapest(4) dos veces, cheapest(3) tres veces, cheapest(2) cinco veces. Los subproblemas se superponen.
Con memoria: las llamadas van en el mismo orden, y la primera vez que se calcula una respuesta entra en memo, abajo.
La segunda vez la respuesta ya está en memo (verde): todo el subárbol de debajo ni siquiera se ejecuta. 11 llamadas en lugar de 25.
Una tabla de abajo hacia arriba: best[0] y best[1] son las tarifas, y cada celda siguiente se construye con las dos anteriores. 5 celdas, sin recursión.
Cada celda necesita solo las dos últimas. Dos variables avanzan deslizándose en lugar de la tabla: O(n) de tiempo y O(1) de memoria.

La idea

Recordar la respuesta

La solución es no calcular lo mismo dos veces. La primera vez que calculas lo más barato hasta el km k, anótalo. La próxima vez que alguien pregunte por k, devuelve lo que anotaste.

let calls = 0;

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapestMemo(fee, i, memo) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

const fee = fees(30);
const memo = new Map();
const cost = cheapestMemo(fee, 30, memo);
console.log(`${cost} céntimos, ${calls} llamadas`);

1217 céntimos, 59 llamadas

La memoria es un Map: la clave es el kilómetro, el valor es la respuesta. memo.has(i) dice si ya está calculada.

Esto se llama memoización (recordar los resultados). La función es la misma recursión, solo que con memoria. 59 llamadas en lugar de 2 692 537: cada kilómetro se calcula una vez, y la segunda pregunta sobre él devuelve la respuesta ya hecha.

Un problema que se construye con las respuestas de problemas más pequeños, cuando esos más pequeños se repiten, se resuelve con programación dinámica: cada subproblema se resuelve una vez y se guarda su respuesta. El nombre es antiguo y no dice mucho. Recuérdalo como «recordar y reutilizar».

Pruébalo

Predice la salida

La misma función con memoria, para una ruta de 8 km. ¿Cuántas veces se llamará?

let calls = 0;

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapestMemo(fee, i, memo) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

const fee = fees(8);
const memo = new Map();
const cost = cheapestMemo(fee, 8, memo);
console.log(`${cost} céntimos, ${calls} llamadas`);

Respuesta

331 céntimos, 15 llamadas

331 céntimos, 67 llamadas

331 céntimos, 8 llamadas

La idea

De abajo hacia arriba

La recursión con memoria empieza en el km n y baja hasta llegar a los pequeños. También puedes ir al revés: empezar por los pequeños y subir. Lo más barato hasta el km 0 y el km 1 es la propia tarifa. De ahí sale el km 2, luego el km 3, y así hasta n. Cuando llegas a una celda, las dos de debajo ya están hechas.

function cheapestTable(fee) {
  const n = fee.length - 1;
  const best = new Array(n + 1).fill(0);
  best[0] = fee[0];
  best[1] = fee[1];
  for (let i = 2; i <= n; i++) {
    const cheaper = Math.min(best[i - 1], best[i - 2]);
    best[i] = fee[i] + cheaper;
  }
  return best[n];
}

Esto es programación dinámica de abajo hacia arriba, con una tabla. No hay recursión ni comprobación de «¿ya está calculado?»: el orden del bucle garantiza que todo lo necesario ya está en la tabla. Hay n − 1 celdas, con un trozo de trabajo por celda: O(n).

Una observación más. La celda i solo mira i − 1 e i − 2. Todo lo anterior ya no hace falta. Así que toda la tabla puede convertirse en dos variables que avanzan deslizándose:

function cheapestPair(fee) {
  let twoBack = fee[0];
  let oneBack = fee[1];
  for (let i = 2; i < fee.length; i++) {
    const here = fee[i] + Math.min(oneBack, twoBack);
    twoBack = oneBack;
    oneBack = here;
  }
  return oneBack;
}

const fee = fees(30);
console.log(`tabla: ${cheapestTable(fee)} céntimos`);
console.log(`dos variables: ${cheapestPair(fee)} céntimos`);

tabla: 1217 céntimos
dos variables: 1217 céntimos

El tiempo sigue siendo O(n), y la memoria O(1): dos números, por larga que sea la ruta.

Míralo

Mídelo: sin memoria, con memoria, con tabla

Ejecuta las tres en rutas de 10, 20 y 30 km. Contamos las llamadas de la función y, en la tabla, las celdas. La recursión sin memoria no se ejecuta por encima de 30 km: con 40 km son 331 160 281 llamadas y la página se congelaría.

Recursión sin memoria O(2ⁿ)
Recursión con memoria O(n)
Tabla, de abajo hacia arriba O(n)

Algoritmo	n = 10	n = 20	n = 30
Recursión sin memoria	177	21.891	2.692.537
Recursión con memoria	19	39	59
Tabla, de abajo hacia arriba	9	19	29

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

function cheapestMemo(fee, i, memo) {
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

Cada 10 km la recursión sin memoria se multiplica por unas 123, mientras que las otras dos crecen en 20 y en 10. La curva de Bench lleva la etiqueta O(2ⁿ): es exponencial, con una base de aproximadamente 1,6, la razón entre dos números de Fibonacci vecinos.

Más precisamente, para curiosos

Los mismos números en tu lenguaje: las llamadas sin memoria, con memoria y las celdas de la tabla para 10, 20 y 30 km.

let calls = 0;
let cells = 0;

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapest(fee, i) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  const oneBack = cheapest(fee, i - 1);
  const twoBack = cheapest(fee, i - 2);
  return fee[i] + Math.min(oneBack, twoBack);
}

function cheapestMemo(fee, i, memo) {
  calls++;
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

function cheapestTable(fee) {
  const n = fee.length - 1;
  const best = new Array(n + 1).fill(0);
  best[0] = fee[0];
  best[1] = fee[1];
  for (let i = 2; i <= n; i++) {
    cells++;
    const cheaper = Math.min(best[i - 1], best[i - 2]);
    best[i] = fee[i] + cheaper;
  }
  return best[n];
}

for (const km of [10, 20, 30]) {
  const fee = fees(km);
  calls = 0;
  cheapest(fee, km);
  const plain = calls;
  calls = 0;
  cheapestMemo(fee, km, new Map());
  cells = 0;
  const cost = cheapestTable(fee);
  console.log(`${km} km: ${plain} / ${calls} / ${cells}, ${cost} céntimos`);
}

10 km: 177 / 19 / 9, 381 céntimos
20 km: 21891 / 39 / 19, 822 céntimos
30 km: 2692537 / 59 / 29, 1217 céntimos

Pruébalo

Encuentra el error

Un compañero escribió la función con memoria. La respuesta es correcta, pero el contador muestra lo mismo que sin memoria:

const fee = fees(30);
const memo = new Map();
const cost = cheapestMemo(fee, 30, memo);
console.log(`${cost} céntimos, ${calls} llamadas`);

1217 céntimos, 2692537 llamadas

¿Qué línea tiene el error?

Elige la línea con el error.

Pruébalo

Completa

La celda i de la tabla es la tarifa en el km i más lo más barato de los dos lugares de los que puedes venir. ¿Cuál es el segundo?

function cheapestTable(fee) {
  const n = fee.length - 1;
  const best = new Array(n + 1).fill(0);
  best[0] = fee[0];
  best[1] = fee[1];
  for (let i = 2; i <= n; i++) {
    const cheaper = Math.min(best[i - 1], );
    best[i] = fee[i] + cheaper;
  }
  return best[n];
}

Ejercicio

Las tarifas de la entrada

Resuélvelo en tu editor.

El plan más barato. Lee las tarifas de las estaciones del km 1 al km n (en céntimos, separadas por espacios) e imprime el plan más barato. Usa cheapestPair de la lección.

77 114 61 98 45 82

Lo más barato: 265 céntimos

Más tareas

Qué estaciones. Imprime también los kilómetros donde se detiene el mensajero. Pista: junto a la tabla, guarda de dónde vino cada celda (i − 1 o i − 2), y vuelve atrás desde n.
Cuántos planes. Cuenta todos los planes, sin importar lo que cuesten. ¿Cuántos hay para 30 km? Compara los números con los de Fibonacci. (Para 30 km hay 1 346 269.)
Una batería mejor. El scooter nuevo dura 3 km. ¿Cómo cambia la fórmula y cuántas variables necesitas en lugar de dos?

Más precisamente

La profundidad y la memoria integrada

La memoria recorta el trabajo, pero la recursión sigue siendo recursión.

Más precisamente, para curiosos

Hasta dónde baja. La recursión con memoria baja primero por la cadena n, n − 1, … 1, y solo entonces empieza a guardar. La pila de llamadas tiene n marcos, como en la lección «La pila de llamadas por dentro». La tabla hace el mismo trabajo en un bucle, y la pila no crece, como en «De la recursión al bucle».

function fees(n) {
  const fee = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    fee[i] = 40 + ((i * 37) % 90);
  }
  return fee;
}

function cheapestMemo(fee, i, memo) {
  if (i <= 1) {
    return fee[i];
  }
  if (memo.has(i)) {
    return memo.get(i);
  }
  const oneBack = cheapestMemo(fee, i - 1, memo);
  const twoBack = cheapestMemo(fee, i - 2, memo);
  memo.set(i, fee[i] + Math.min(oneBack, twoBack));
  return memo.get(i);
}

function cheapestTable(fee) {
  const n = fee.length - 1;
  const best = new Array(n + 1).fill(0);
  best[0] = fee[0];
  best[1] = fee[1];
  for (let i = 2; i <= n; i++) {
    const cheaper = Math.min(best[i - 1], best[i - 2]);
    best[i] = fee[i] + cheaper;
  }
  return best[n];
}

const fee = fees(100000);
try {
  cheapestMemo(fee, 100000, new Map());
} catch (e) {
  console.log("cheapestMemo:", e.constructor.name);
}
console.log("cheapestTable:", cheapestTable(fee));

cheapestMemo: RangeError
cheapestTable: 3886659

Java y JavaScript no tienen un límite en el número de niveles, pero la pila es de aproximadamente 1 MB, y 100 000 llamadas anidadas no caben. En Python el límite es de 1000 niveles.

Memoria integrada en el lenguaje. JavaScript no tiene memoria integrada para funciones. Map es la elección correcta: un objeto normal convierte sus claves en cadenas, mientras que Map conserva un número como número. Para una clave de varios números usa una cadena, por ejemplo `${i},${j}`.

De arriba abajo o de abajo arriba. Los dos caminos resuelven los mismos subproblemas. Con memoria se calculan solo los que realmente se alcanzan, y se escribe directamente a partir de la recursión ingenua. Con una tabla no hay recursión y a menudo se puede reducir, como aquí. Si los subproblemas son muchos y la respuesta necesita pocos, gana la memoria. Si se necesitan casi todos, la tabla es más rápida y no arriesga la pila.

Test

Ponte a prueba

1. ¿Por qué la recursión sin memoria hace 2,7 millones de llamadas para 30 km, y con memoria solo 59?La memoria hace más rápida cada llamadaCon memoria la función se salta los kilómetros que no necesitaSin memoria los mismos subproblemas (lo más barato hasta el km 5, hasta el km 4…) se resuelven de nuevo cada vez que alguien los pide

2. ¿En qué se diferencia la programación dinámica de «divide y vencerás» en el ordenamiento por mezcla?En el ordenamiento por mezcla las mitades no se superponen y cada subproblema se resuelve una vez sin memoria; aquí los subproblemas se repiten y vale la pena recordarlosLa programación dinámica siempre divide por la mitadEl ordenamiento por mezcla usa una tabla y la programación dinámica no

3. La tabla para n km se llena de best[2] a best[n]. ¿Cuánta memoria necesita la versión de dos variables?O(n): toda la tablaO(1): solo los dos últimos valoresO(log n)

4. Una función con memoria consulta la memoria pero nunca escribe en ella. ¿Qué pasa?La respuesta sale malLa función no termina nuncaLa respuesta es correcta, pero las llamadas son tantas como sin memoria

5. ¿Por qué la recursión con memoria falla en Python para 5000 km, mientras que la tabla funciona?Con memoria la primera llamada baja 5000 niveles antes de guardar nada, y el límite de Python es de 1000 niveles; la tabla es un bucle sin recursiónLa memoria de Python no alcanza para 5000 númerosLa tabla usa números más pequeños

Subproblemas superpuestos

Cookies