Ir al contenido
Ayotl
English

← Estructuras de datos desde cero · Lección 5/32

Recorrer, meter y sacar

✕
1/7

Recorrer

Recorrer es visitar cada casilla una vez: O(n). En JavaScript hay dos formas que vas a usar todo el tiempo:

  • for (let i = 0; i < arr.length; i++) cuando necesitas el índice.
  • for (const x of arr) cuando sólo te importa el valor.

Buscar un valor sin saber dónde está también es un recorrido: indexOf e includes revisan casilla por casilla hasta encontrarlo. Es la búsqueda lineal, O(n) en el peor caso.

leccion.js

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

  • El primer ciclo da índice y valor; el segundo, sólo el valor.
  • indexOf devuelve -1 cuando no lo encuentra: para saberlo tuvo que revisar las cuatro casillas.
Toda la lección en una página

Recorrer

Recorrer es visitar cada casilla una vez: O(n). En JavaScript hay dos formas que vas a usar todo el tiempo:

  • for (let i = 0; i < arr.length; i++) cuando necesitas el índice.
  • for (const x of arr) cuando sólo te importa el valor.

Buscar un valor sin saber dónde está también es un recorrido: indexOf e includes revisan casilla por casilla hasta encontrarlo. Es la búsqueda lineal, O(n) en el peor caso.

const tianguis = ["jitomate", "cebolla", "chile", "aguacate"];

for (let i = 0; i < tianguis.length; i++) {
  console.log(i, tianguis[i]);
}
for (const cosa of tianguis) {
  console.log(cosa.toUpperCase());
}

console.log(tianguis.indexOf("chile"));   // dónde está
console.log(tianguis.indexOf("mango"));   // -1: no está
console.log(tianguis.includes("mango"));
  • El primer ciclo da índice y valor; el segundo, sólo el valor.
  • indexOf devuelve -1 cuando no lo encuentra: para saberlo tuvo que revisar las cuatro casillas.

Al final es barato; al principio, caro

push mete al final y pop saca del final: no hay que mover a nadie, así que cuestan O(1).

unshift mete al principio y shift saca del principio. Como las casillas van seguidas y numeradas, todos los demás tienen que recorrerse un lugar para dejar o tapar el hueco: O(n). splice, que mete o saca en medio, también recorre a los que quedan detrás.

El programa mide cuánto tarda cada uno con 20 000 elementos.

ZABCD01234unshift ↓
function medir(nombre, hacer) {
  const arr = [];
  const t0 = Date.now();
  for (let i = 0; i < 20000; i++) hacer(arr, i);
  console.log(nombre, Date.now() - t0, "ms");
}

medir("push   ", (a, i) => a.push(i));
medir("unshift", (a, i) => a.unshift(i));

const letras = ["a", "b", "c", "d"];
letras.splice(1, 2);        // desde el 1, saca 2
console.log(letras);
letras.splice(1, 0, "x");   // desde el 1, saca 0 y mete "x"
console.log(letras);
  • unshift tarda muchas veces más que push con la misma cantidad: cada uno recorre a todos los anteriores. (Los milisegundos cambian de una corrida a otra; la diferencia no.)
  • splice(inicio, cuántos, ...nuevos) saca y mete en medio.

map, filter y reduce

Tres recorridos tan comunes que tienen nombre propio. Los tres devuelven algo nuevo y no cambian el original:

  • map(f): un arreglo del mismo tamaño, con f aplicada a cada elemento.
  • filter(f): sólo los elementos para los que f da true.
  • reduce(f, inicial): junta todo en un solo valor, como una suma.

Siguen siendo O(n): son ciclos escritos de otra forma.

const precios = [20, 45, 12, 80];

const conIva = precios.map(p => p * 1.16);
console.log(conIva);

const baratos = precios.filter(p => p < 30);
console.log(baratos);

const total = precios.reduce((suma, p) => suma + p, 0);
console.log(total);

console.log(precios); // el original no cambió
  • map da cuatro precios con IVA (con decimales feos: así son los números de punto flotante).
  • filter se queda con 20 y 12.
  • reduce empieza en 0 y va sumando: 157.