Complejidad en espacio en JavaScript

Problema

La exportación que se come la memoria

Cada noche un servicio exporta a un archivo los logs del día de la tienda. Para poder continuar donde se quedó después de una caída, escribe un punto de control después de cada línea. Solo que el punto de control es una copia de todo el archivo hasta ese momento:

function exportLogs(logs) {
  const file = [];
  const checkpoints = [];
  for (const line of logs) {
    file.push(line);
    checkpoints.push([...file]);
  }
  let places = 0;
  for (const saved of checkpoints) {
    places += saved.length;
  }
  return places;
}

¿Cuántos espacios ocupan las copias? El programa los cuenta:

for (const n of [5, 1000]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`línea ${i}`);
  }
  console.log(`${n} líneas: ${exportLogs(logs)} espacios`);
}

5 líneas: 15 espacios
1000 líneas: 500500 espacios

Con 1000 líneas son 500 500 espacios. Los logs de un día son 100 000 líneas, y eso son 5 000 050 000 espacios. Cada espacio guarda una referencia de 4 a 8 bytes: entre 20 y 40 GB solo para las copias. En la prueba con 1000 líneas todo pasa, y por la noche la exportación se detiene con JavaScript heap out of memory.

La idea

La memoria también es un costo

Hasta ahora contabas operaciones. La memoria se cuenta igual: cuántos espacios aparta el algoritmo por sí mismo, aparte de la entrada que recibe. Esa es la complejidad en espacio del algoritmo. También se escribe con Big-O:

O(1): unas pocas variables, sea cual sea el tamaño de la entrada;
O(n): una copia de la entrada, una lista auxiliar, un conjunto con todos los elementos;
O(n²): una copia de la copia en cada paso, como en la exportación.

La entrada no cuenta, porque existe sin el algoritmo. Tampoco cuenta el resultado que pide la tarea: el archivo con n líneas es el trabajo de la exportación. Lo que cuenta son las copias que hace por el camino.

Míralo

Las copias se quedan

const file = [];
let checkpoint = 0;
for (const line of logs) {
  file.push(line);
  checkpoint = file.length;
}

Paso a paso, en palabras

file es el archivo que escribe la exportación, y logs tiene 4 líneas. checkpoints guarda desde dónde continuar tras una caída.
La línea 1 va al archivo. El punto de control es una copia de todo el archivo: 1 espacio.
Línea 2. El nuevo punto de control copia las dos líneas, y el viejo se queda en la lista: 1 + 2 = 3 espacios.
Tras 4 líneas la memoria guarda 1 + 2 + 3 + 4 = 10 espacios. Tras n líneas son n(n + 1)/2: cinco mil millones con 100 000 líneas.
Para continuar tras una caída solo necesitas saber hasta dónde llegaste. Las copias desaparecen, queda un número.
Cada línea cambia el número: checkpoint = 4. La memoria extra es 1 espacio, sean cuantas sean las líneas.

Cada copia es una lista nueva en la memoria, y nadie borra las viejas: la lista checkpoints las guarda. Por eso los espacios crecen como 1 + 2 + 3 + … + n. Para continuar después de una caída, a la exportación solo le hace falta saber hasta dónde llegó:

function exportLogs(logs) {
  const file = [];
  let checkpoint = 0;
  for (const line of logs) {
    file.push(line);
    checkpoint = file.length;
  }
  return checkpoint;
}

for (const n of [5, 1000]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`línea ${i}`);
  }
  console.log(`${n} líneas, checkpoint: ${exportLogs(logs)}`);
}

5 líneas, checkpoint: 5
1000 líneas, checkpoint: 1000

El archivo es el mismo, y la memoria extra es un número: O(1) en lugar de O(n²).

Pruébalo

Predice la salida

La exportación con copias recibe 6 líneas. ¿Cuántos espacios ocupan los puntos de control?

function exportLogs(logs) {
  const file = [];
  const checkpoints = [];
  for (const line of logs) {
    file.push(line);
    checkpoints.push([...file]);
  }
  let places = 0;
  for (const saved of checkpoints) {
    places += saved.length;
  }
  return places;
}

for (const n of [6]) {
  const logs = [];
  for (let i = 1; i <= n; i++) {
    logs.push(`línea ${i}`);
  }
  console.log(`${n} líneas: ${exportLogs(logs)} espacios`);
}

Respuesta

6 líneas: 36 espacios

6 líneas: 21 espacios

6 líneas: 6 espacios

Míralo

Una copia o en el sitio

El administrador quiere las líneas de log más nuevas primero. Hay dos maneras. Una crea una lista nueva en orden inverso, y la otra intercambia los elementos de la propia lista: el primero con el último, el segundo con el penúltimo, hasta que los dos extremos se encuentran.

function newestFirst(logs) {
  const result = [];
  for (let i = logs.length - 1; i >= 0; i--) {
    result.push(logs[i]);
  }
  return result;
}

function reverseInPlace(logs) {
  let left = 0;
  let right = logs.length - 1;
  while (left < right) {
    [logs[left], logs[right]] = [logs[right], logs[left]];
    left++;
    right--;
  }
}

const logs = ["09:00 inicio de sesión", "09:05 carrito", "09:07 pago"];
const newest = newestFirst(logs);
console.log("Copia:    " + newest.join(", "));
console.log("Original: " + logs.join(", "));
reverseInPlace(logs);
console.log("En sitio: " + logs.join(", "));

Copia:    09:07 pago, 09:05 carrito, 09:00 inicio de sesión
Original: 09:00 inicio de sesión, 09:05 carrito, 09:07 pago
En sitio: 09:07 pago, 09:05 carrito, 09:00 inicio de sesión

La copia necesita n espacios nuevos, pero el original se queda como estaba. El cambio en el sitio necesita un espacio para el intercambio, pero el orden viejo desaparece. Cuál es mejor depende de si alguien más sigue leyendo el original.

Más precisamente, para curiosos

Las funciones incorporadas toman la misma decisión, y el nombre no siempre la delata:

const logs = ["09:00 inicio de sesión", "09:05 carrito", "09:07 pago"];
const copy = logs.toReversed();
logs.reverse();
console.log("En sitio: " + logs.join(", "));
console.log("Copia:    " + copy.join(", "));

En sitio: 09:07 pago, 09:05 carrito, 09:00 inicio de sesión
Copia:    09:07 pago, 09:05 carrito, 09:00 inicio de sesión

reverse() invierte en el sitio, y toReversed() (desde 2023, Node 20) hace una copia. slice() y [...logs] también copian: en una recursión logs.slice(1) copia casi todo el array en cada llamada.

La copia es superficial: la lista nueva guarda referencias a los mismos textos, no textos nuevos. Por eso los espacios se cuentan uno por elemento.

Pruébalo

Completa

Termina el intercambio de los dos extremos:

[logs[left], logs[right]] = [logs[right], ];

Míralo

La recursión también guarda memoria

No solo una lista ocupa espacio. Cada llamada a una función guarda sus parámetros y variables locales en la pila de llamadas hasta que regresa. Aquí se cuentan los errores del log con recursión y con un bucle:

function errorsFrom(logs, i) {
  if (i === logs.length) {
    return 0;
  }
  const here = logs[i].startsWith("ERROR") ? 1 : 0;
  return here + errorsFrom(logs, i + 1);
}

function errors(logs) {
  let count = 0;
  for (const line of logs) {
    if (line.startsWith("ERROR")) {
      count++;
    }
  }
  return count;
}

const small = makeLogs(500);
const big = makeLogs(1_000_000);
console.log(`500 líneas: ${errorsFrom(small, 0)} errores`);
try {
  console.log(`1000000 líneas: ${errorsFrom(big, 0)} errores`);
} catch (e) {
  console.log(`1000000 líneas: ${e.name}`);
}
console.log(`Con bucle: ${errors(big)} errores`);

500 líneas: 5 errores
1000000 líneas: RangeError
Con bucle: 10000 errores

La recursión no crea ni una sola lista, pero con n líneas hay n llamadas sin terminar en la pila: memoria O(n). La pila es pequeña, y un millón de llamadas no caben. El bucle tiene una variable count: O(1).

Más precisamente, para curiosos

Qué tan profunda puede ser la recursión depende del tamaño de la pila y del tamaño de un marco. En Node la pila es de unos 1 MB, que son de unos pocos miles a decenas de miles de llamadas según el marco. RangeError es el nombre del error.

Cuando la llamada recursiva es la última acción de la función (sin here + después), algunos lenguajes la convierten en un bucle (tail call). Java, C#, Python y Node no lo hacen, así que en ellos la profundidad siempre cuesta memoria.

La idea

Tiempo contra memoria

La tienda comprueba si dos pedidos del día tienen el mismo número. La primera manera compara cada par. La segunda recuerda en un conjunto los números que ya vio:

function hasDuplicateLoops(orders) {
  for (let i = 0; i < orders.length; i++) {
    for (let j = i + 1; j < orders.length; j++) {
      if (orders[i] === orders[j]) {
        return true;
      }
    }
  }
  return false;
}

function hasDuplicateSet(orders) {
  const seen = new Set();
  for (const order of orders) {
    if (seen.has(order)) {
      return true;
    }
    seen.add(order);
  }
  return false;
}

const today = [100512, 100513, 100514, 100512];
console.log(hasDuplicateLoops(today), hasDuplicateSet(today));

true true

Las dos dan la misma respuesta, pero pagan de forma distinta:

los bucles anidados: memoria O(1) y tiempo O(n²);
el conjunto: memoria O(n) (hasta n números) y tiempo O(n).

Es un intercambio común: memoria por tiempo. Cuántas comparaciones y comprobaciones hacen las dos cuando no hay repetido (el peor caso):

function comparisonsLoops(orders) {
  let count = 0;
  for (let i = 0; i < orders.length; i++) {
    for (let j = i + 1; j < orders.length; j++) {
      count++;
      if (orders[i] === orders[j]) {
        return count;
      }
    }
  }
  return count;
}

function checksSet(orders) {
  const seen = new Set();
  let count = 0;
  for (const order of orders) {
    count++;
    if (seen.has(order)) {
      return count;
    }
    seen.add(order);
  }
  return count;
}

for (const n of [10, 1000]) {
  const orders = [];
  for (let i = 0; i < n; i++) {
    orders.push(100000 + i);
  }
  console.log(`${n} pedidos: ${comparisonsLoops(orders)} comparaciones con bucles, ${checksSet(orders)} comprobaciones con set`);
}

10 pedidos: 45 comparaciones con bucles, 10 comprobaciones con set
1000 pedidos: 499500 comparaciones con bucles, 1000 comprobaciones con set

Bucles anidados, sin memoria O(n²)
Un conjunto de números vistos, n lugares O(n)

Algoritmo	n = 10	n = 1000	n = 100.000
Bucles anidados, sin memoria	45	499.500	≈ 4.995.000.000
Un conjunto de números vistos, n lugares	10	1000	100.000

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.

Con 100 000 pedidos los bucles hacen casi 5 mil millones de comparaciones, y el conjunto hace 100 000 comprobaciones y guarda 100 000 números. Cuando hay memoria, gana el conjunto. Cuando no la hay (un dispositivo pequeño, una entrada enorme), o ordenas los números (así los repetidos quedan juntos) o lees por partes.

Más precisamente, para curiosos

Contamos una comprobación en el conjunto como una operación. Es O(1) en promedio, porque el conjunto es una tabla hash: el número se convierte en un hash, y el hash dice en qué cubeta mirar. Un espacio en un conjunto cuesta más que un número en un array: en un Set unos 20–40 bytes según el motor. Así que «memoria O(n)» para 10 millones de pedidos son cientos de MB, no 40.

Pruébalo

Encuentra el error

Un compañero reescribió la comprobación con un conjunto, pero nunca encuentra un repetido:

function hasDuplicateSet(orders) {
  for (const order of orders) {
    const seen = new Set();
    if (seen.has(order)) {
      return true;
    }
    seen.add(order);
  }
  return false;
}

const today = [100512, 100513, 100514, 100512];
console.log(hasDuplicateSet(today));

false

El número 100512 está dos veces, y la respuesta es «no». ¿En qué línea está el error?

Elige la línea con el error.

Ejercicio

Las últimas tres líneas

Resuelve la tarea en tu editor.

Las últimas líneas. Cuando algo se rompe, el administrador quiere solo las últimas k líneas del log. Escribe lastLines(logs, k), que las devuelva guardando en memoria como máximo k líneas, no todo el log: memoria O(k). Ejecútalo con 1000 líneas («línea 1» … «línea 1000») y k = 3.

línea 998
línea 999
línea 1000

Una posible solución

Mantén una cola: cada línea nueva entra por detrás y, cuando hay más de k líneas, la más antigua sale por delante.

function lastLines(logs, k) {
  const recent = [];
  for (const line of logs) {
    recent.push(line);
    if (recent.length > k) {
      recent.shift();
    }
  }
  return recent;
}

shift() mueve todos los elementos un lugar a la izquierda, pero hay como máximo k, así que un paso es O(k).

Más tareas

El promedio de longitud sin copia. Calcula la longitud promedio de una línea del log con memoria extra O(1): sin una lista nueva de longitudes.
Errores por hora. Cuenta los errores de cada hora (09, 10 …). ¿Cuánta memoria necesita tu solución si hay 24 horas y un millón de líneas?
Los números repetidos. Devuelve no solo «sí o no», sino todos los números repetidos. ¿Cuánta memoria necesita la solución con un conjunto, y se puede hacer sin él?

Test

Ponte a prueba

1. Una función crea una lista nueva con n líneas de log en orden inverso. ¿Cuánta memoria extra necesita?O(n)O(n²)O(1)

2. La exportación guarda después de cada línea una copia de todo el archivo hasta ese momento. ¿Cuántos espacios ocupa la memoria con n líneas?n(n + 1)/2, es decir, O(n²)n2n

3. Una función recursiva sin ninguna lista se llama a sí misma 1 000 000 de veces, una dentro de otra. ¿Cuánta memoria necesita?O(n): cada llamada se queda en la pila hasta que regresaO(1), porque no hay listasNinguna, la memoria es solo para objetos

4. Buscas un número repetido entre 10 000 000 de pedidos en un servidor con unos pocos GB de memoria libre. ¿Qué eliges?El conjunto: memoria O(n), pero tiempo O(n) en lugar de O(n²)Los bucles anidados, porque no necesitan memoriaNo hay diferencia

5. ¿Qué no cuenta en la memoria extra de una función?La pila de su recursiónLa entrada que recibe la funciónUna copia de la entrada que hace la función

Complejidad en espacio

Cookies