El arreglo dinámico por dentro

Código en:JavaC#PythonJavaScript

En resumen: Un arreglo dinámico (el array de JavaScript) tiene más espacios que elementos: leer por índice es O(1), añadir al final es O(1) de media y insertar al principio es O(n).

Problema

El carrito que se vuelve lento

La tienda en línea muestra el carrito con el último producto añadido arriba. El código lo hace sin complicaciones: cada línea nueva entra en el índice 0.

const orderLines = ["Harina 25 kg", "Azúcar 10 kg", "Aceite 5 l", "Arroz 10 kg"];
const cart = [];
for (const line of orderLines) {
  cart.unshift(line);
}
console.log("El carrito: " + cart.join(", "));

Salida

El carrito: Arroz 10 kg, Aceite 5 l, Azúcar 10 kg, Harina 25 kg

Con un cliente normal y 5 productos no se nota. Luego llega un cliente mayorista y sube un pedido desde un archivo: 50 000 líneas. La página se congela durante segundos.

La causa: cada inserción en el índice 0 mueve un espacio todos los productos ya añadidos. 50 000 líneas hacen 1 + 2 + … + 49 999 = 1 249 975 000 movimientos.

La idea

Un arreglo que se cuida solo

El array es por dentro un arreglo dinámico: un arreglo normal con más espacios que elementos y un contador de cuántos están ocupados.

• La capacidad es cuántos espacios tiene el arreglo.
• El tamaño es cuántos de ellos están ocupados, de 0 al tamaño menos uno.

Cuando se acaban los espacios, crea un arreglo nuevo, el doble de grande, y copia todo. Por qué eso es O(1) de media se explica en la lección «Complejidad amortizada». Aquí miramos qué pasa dentro del arreglo: al leer, al insertar y al quitar por índice.

Los espacios del arreglo están uno junto a otro en la memoria y son del mismo tamaño. Si el arreglo empieza en la dirección 1000 y cada espacio ocupa 8 bytes, el espacio i está en la dirección 1000 + i × 8. Por eso leer por índice es una multiplicación y una suma: O(1), sin importar cuántos elementos haya.

Míralo

Tu propio arreglo dinámico

Aquí está lo mismo, escrito a mano. El arreglo empieza con 8 espacios:

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`índice ${index}, tamaño ${this.length}`);
    }
  }
}

Mira qué pasa con los espacios al leer, insertar y quitar:

insert(index, value) {
  this.#check(index, this.length + 1);
  if (this.length === this.items.length) {
    this.#grow();
  }
  for (let i = this.length; i > index; i--) {
    this.items[i] = this.items[i - 1];
  }
  this.items[index] = value;
  this.length++;
}

removeAt(index) {
  this.#check(index, this.length);
  const removed = this.items[index];
  for (let i = index; i < this.length - 1; i++) {
    this.items[i] = this.items[i + 1];
  }
  this.length--;
  this.items[this.length] = undefined;
  return removed;
}

Paso a paso, en palabras

1. El carrito es un único bloque de 8 espacios contiguos en la memoria. Hay 5 ocupados: ese es el tamaño. Los 8 son la capacidad.
2. get(3): la dirección es inicio + 3 × 8 = 1024. Un salto, sin pasar por los demás: O(1) con cualquier tamaño.
3. insert(0, …): el espacio 0 está ocupado. Cada producto se desplaza un espacio a la derecha, de atrás hacia delante, para no borrar nada: 5 desplazamientos.
4. Solo ahora «Queso» entra en el espacio 0, y el tamaño pasa a ser 6.
5. removeAt(2) saca «Leche». Los 3 siguientes se desplazan un espacio a la izquierda para cerrar el hueco: 3 desplazamientos.
6. El tamaño baja a 5, y el último espacio recibe undefined: la referencia antigua mantendría vivo el producto en la memoria.
7. get(5): el espacio 5 existe (la capacidad es 8), pero no está en el carrito. La comprobación compara con el tamaño y lanza RangeError.
8. Leer por índice es un salto. Insertar y quitar desplazan todo lo que hay después del índice: al principio son todos los n, O(n). Al final no se desplaza nada.

const cart = new DynamicArray();
cart.add("Pan");
cart.add("Leche");
cart.add("Café");
cart.add("Mantequilla");
cart.add("Manzanas");
console.log(cart.get(3));
cart.insert(0, "Queso");
cart.removeAt(2);
for (let i = 0; i < cart.length; i++) {
  console.log(`${i}: ${cart.get(i)}`);
}
console.log("Espacios: " + cart.capacity);
try {
  cart.get(5);
} catch (e) {
  console.log("Error: " + e.message);
}

Salida

Mantequilla
0: Queso
1: Pan
2: Café
3: Mantequilla
4: Manzanas
Espacios: 8
Error: índice 5, tamaño 5

El array integrado de JavaScript no comprueba el índice: cart[5] fuera del array da undefined, sin error. Nuestra clase comprueba y lanza RangeError, como hacen Java, C# y Python.

Pruébalo

Predice la salida

Un arreglo con 8 espacios contiene 8 productos. Insertas uno más al principio:

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`índice ${index}, tamaño ${this.length}`);
    }
  }
}

const cart = new DynamicArray();
for (let i = 1; i <= 8; i++) {
  cart.add("P" + i);
}
cart.insert(0, "P0");
console.log("Productos: " + cart.length);
console.log("Espacios: " + cart.capacity);
console.log(cart.get(8));

Respuesta

Productos: 9
Espacios: 16
P0

Productos: 9
Espacios: 9
P8

Productos: 9
Espacios: 16
P8

Comprobar

La idea

Insertar y quitar cuestan O(n)

Insertar en el índice i mueve todo lo que hay desde i hasta el final un espacio a la derecha, de atrás hacia delante, para no borrar nada. Quitar mueve todo lo que hay después de i un espacio a la izquierda. Cuanto más cerca del principio, más:

• Al final: no se mueve nada. O(1), y con el crecimiento O(1) amortizado.
• Al principio: se mueve todo. O(n).
• En el medio: de media, la mitad. Sigue siendo O(n).

Por eso n inserciones al principio son O(n²), y n adiciones al final, O(n). La solución para el carrito es añadir al final y mostrar de atrás hacia delante. Recorrer desde atrás es el mismo O(n):

const orderLines = ["Harina 25 kg", "Azúcar 10 kg", "Aceite 5 l", "Arroz 10 kg"];
const cart = [];
for (const line of orderLines) {
  cart.push(line);
}
const newestFirst = cart.toReversed();
console.log("El carrito: " + newestFirst.join(", "));

Salida

El carrito: Arroz 10 kg, Aceite 5 l, Azúcar 10 kg, Harina 25 kg

Míralo

Mídelo: al final contra al principio

Ejecuta los dos caminos con los mismos productos. Contamos las escrituras de elementos en el arreglo: la del nuevo, cada movimiento y cada copia al crecer. Insertar al principio con 100 000 no se ejecuta de verdad: Bench lo estima a partir de la curva.

• Agregar al final O(n)
• Insertar al principio O(n²)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Agregar al final	18	2016	26.376	231.064
Insertar al principio	63	501.516	50.021.376	≈ 5.002.137.600

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.

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`índice ${index}, tamaño ${this.length}`);
    }
  }
}

Con 1000 productos, añadir al final hace 2016 escrituras: 1000 nuevas y las copias al crecer. Insertar al principio hace 501.516. Con 10 000 la diferencia es 26.376 contra 50.021.376.

Más precisamente, para curiosos

Los mismos números en tu lenguaje, con un contador de escrituras en la clase:

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
    this.writes = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
      this.writes++;
    }
    this.items[index] = value;
    this.writes++;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
      this.writes++;
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`índice ${index}, tamaño ${this.length}`);
    }
  }
}

for (const n of [10, 1000, 100000]) {
  const cart = new DynamicArray();
  for (let i = 0; i < n; i++) {
    cart.add(String(1001 + i));
  }
  console.log(`al final, n = ${n}: ${cart.writes} escrituras`);
}
for (const n of [10, 1000]) {
  const cart = new DynamicArray();
  for (let i = 0; i < n; i++) {
    cart.insert(0, String(1001 + i));
  }
  console.log(`al principio, n = ${n}: ${cart.writes} escrituras`);
}

Salida

al final, n = 10: 18 escrituras
al final, n = 1000: 2016 escrituras
al final, n = 100000: 231064 escrituras
al principio, n = 10: 63 escrituras
al principio, n = 1000: 501516 escrituras

Pruébalo

Encuentra el error

Un compañero ha reescrito insert. Tres productos, luego uno más al principio, y el carrito sale así:

const cart = new DynamicArray();
cart.add("Pan");
cart.add("Leche");
cart.add("Café");
cart.insert(0, "Queso");
for (let i = 0; i < cart.length; i++) {
  console.log(`${i}: ${cart.get(i)}`);
}

Salida

0: Queso
1: Pan
2: Pan
3: Pan

¿En qué línea está el error?

Elige la línea con el error.

1class DynamicArray {2 constructor() {3 this.items = new Array(8);4 this.length = 0;5 }67 get capacity() {8 return this.items.length;9 }1011 get(index) {12 this.#check(index, this.length);13 return this.items[index];14 }1516 set(index, value) {17 this.#check(index, this.length);18 this.items[index] = value;19 }2021 add(value) {22 this.insert(this.length, value);23 }2425 insert(index, value) {26 this.#check(index, this.length + 1);27 if (this.length === this.items.length) {28 this.#grow();29 }30 for (let i = index; i < this.length; i++) {31 this.items[i + 1] = this.items[i];32 }33 this.items[index] = value;34 this.length++;35 }3637 removeAt(index) {38 this.#check(index, this.length);39 const removed = this.items[index];40 for (let i = index; i < this.length - 1; i++) {41 this.items[i] = this.items[i + 1];42 }43 this.length--;44 this.items[this.length] = undefined;45 return removed;46 }4748 #grow() {49 const bigger = new Array(this.items.length * 2);50 for (let i = 0; i < this.length; i++) {51 bigger[i] = this.items[i];52 }53 this.items = bigger;54 }5556 #check(index, limit) {57 if (index < 0 || index >= limit) {58 throw new RangeError(`índice ${index}, tamaño ${this.length}`);59 }60 }61}

Comprobar

Pruébalo

Completa

removeAt cierra el hueco moviendo cada elemento posterior un espacio a la izquierda. ¿De dónde viene el elemento del espacio i?

removeAt(index) {
  this.#check(index, this.length);
  const removed = this.items[index];
  for (let i = index; i < this.length - 1; i++) {
    this.items[i] = this.items[];
  }
  this.length--;
  this.items[this.length] = undefined;
  return removed;
}

Comprobar

La idea

Reducir o no reducir

El carrito llegó a tener 10 000 productos, y luego el cliente quitó casi todos. El arreglo aún guarda 16 384 espacios. ¿Debería reducirse?

Si se reduce a la mitad en cuanto el tamaño cae por debajo de la mitad, hay una trampa. Un arreglo con 16 espacios y 9 elementos: un quitar, y pasa a 8 espacios, lleno. Un añadir, y vuelve a 16 espacios. Alterna los dos justo en ese límite, y cada operación copia todo: O(n).

Por eso la reducción espera más: a la mitad, cuando está lleno hasta un cuarto. Tras reducir, el arreglo está medio lleno, y hasta la siguiente copia hay al menos n/4 operaciones. El coste sigue siendo O(1) amortizado.

Las listas integradas deciden de otra forma:

• Java ArrayList no se reduce solo, tiene trimToSize();
• C# List<T> no se reduce solo, tiene TrimExcess();
• Python (CPython) se reduce solo por debajo de la mitad;
• JavaScript (V8) reduce la memoria del array cuando una parte grande está vacía, por ejemplo tras pop o length = 0. El lenguaje no lo promete, lo decide el motor.

Reducir ahorra memoria, pero cuesta una copia. Si el arreglo va a volver a crecer pronto, es más barato no reducirlo.

La idea

Por qué el arreglo también es rápido en la práctica: el caché

El procesador no lee la memoria byte a byte. Toma una línea entera de 64 bytes y la guarda en el caché, una memoria pequeña y muy rápida a su lado. Leer del caché es decenas de veces más rápido que leer de la memoria principal.

El arreglo es un solo bloque. Cuando lees el espacio 0, sus vecinos vienen en la misma línea y las siguientes lecturas salen del caché. El procesador también nota que lees en orden, y trae las siguientes líneas por adelantado. Por eso recorrer un arreglo es rápido no solo sobre el papel, sino también en el reloj.

Importa qué hay en los espacios: - V8 guarda un array solo de enteros pequeños como los propios números uno junto a otro, y un array de objetos o texto como referencias a ellos. Un array con huecos o con tipos mezclados se vuelve más lento. Para números juntos existen Int32Array y Float64Array.

La siguiente lección, «Lista enlazada», es lo contrario: cada elemento es un objeto aparte en algún lugar de la memoria. Allí insertar al principio es O(1), pero el caché no ayuda.

Ejercicio

Un arreglo que se reduce

Resuélvelo en tu editor.

Reducir con un cuarto. Sustituye el crecimiento de la clase por un método #resize(places) que crea un arreglo con esa cantidad de espacios y copia los elementos. insert lo llama con el doble de espacios cuando el arreglo está lleno. removeAt lo llama con la mitad cuando el tamaño llega a un cuarto de los espacios, pero nunca por debajo de 8 espacios.

Añade 20 productos e imprime el tamaño y los espacios. Luego quita desde el final hasta que queden 2, e imprime el tamaño y los espacios en cada cambio de espacios:

Salida

20 / 32
8 / 16
4 / 8

Más ejercicios

• indexOf y remove. Añade indexOf(value), que devuelve el índice o -1, y remove(value), que quita la primera aparición. ¿Cuánto cuesta cada uno?
• Quitar del principio sin mover. Una cola de pedidos quita siempre el primero. Guarda un índice head del primer espacio ocupado en lugar de mover todos. ¿Qué pasa cuando head llega al final del arreglo? (Pista: continúa desde el principio.)
• Llenar por partes. Importa 50 000 líneas de una vez: reúnelas al final y da la vuelta al arreglo una sola vez. ¿Cuántas escrituras son?

Test

Ponte a prueba

1. Un arreglo dinámico tiene 1000 elementos. ¿Cuántos elementos mueve una inserción en el índice 0? ¿Y en el índice 990?

1000 y 10001 y 11000 y 10

2. ¿Por qué leer por índice es O(1) incluso con un millón de elementos?

Porque el arreglo está ordenadoEl arreglo recuerda dónde está cada elemento en una tabla aparteLa dirección se calcula: inicio + índice × tamaño de un espacio

3. El arreglo tiene capacidad 8 y tamaño 5. ¿Qué pasa con get(6)?

Devuelve un espacio vacíoUn error de índice fuera de los límites, aunque el espacio 6 existeEl arreglo crece hasta 16

4. ¿Por qué el arreglo se reduce a la mitad solo cuando está lleno hasta un cuarto, y no hasta la mitad?

Porque reducir es lentoCon el límite en «la mitad», alternar añadir y quitar justo ahí reduciría y ampliaría cada vez, y cada una copia todoPorque la memoria solo se libera por cuartos

5. El carrito debe mostrar arriba el último producto añadido. ¿Cuál es la solución rápida?

Añadir al final y mostrarlo de atrás hacia delanteOrdenar después de cada adiciónInsertar en el índice 0

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Big-O: cómo crece el trabajo · Mejor caso, caso promedio y peor caso · Complejidad en espacio · Complejidad amortizada
• Continúa en: Lista enlazada · Pila y cola · Tabla hash
• Ejercicios sobre el tema: Estructuras de datos