Arreglos

Leer el valor número un millón de un arreglo lleva un paso, pero poner un valor nuevo al principio del mismo arreglo mueve un millón de valores.

Qué es una estructura de datos

Un programa que guarda una lista de nombres, una cola de trabajos de impresión o una tabla de precios tiene que almacenar esos datos en algún lugar, y tiene que responder preguntas sobre ellos: ¿cuál es el tercer elemento?, ¿está este nombre en la lista?, ¿qué trabajo sigue? Una estructura de datos es una forma de guardar datos junto con los métodos que responden esas preguntas. El curso 6.006 del MIT separa aquí dos ideas. La interfaz dice qué operaciones puedes pedir, como "obtener el elemento de la posición i" o "agregar un elemento al final". La estructura de datos es cómo se llevan a cabo realmente esas operaciones en la memoria. Detrás de una misma interfaz puede haber varias estructuras de datos, y su velocidad puede ser muy distinta.

Este curso cuenta pasos, como el curso de algoritmos, para poder comparar dos estructuras sin cronómetro. En esta unidad, un paso es leer o escribir una celda de memoria. El laboratorio de abajo los cuenta por ti.

Un bloque de celdas, una junto a otra

Un arreglo guarda sus valores en un solo bloque continuo de memoria, cada valor en una celda del mismo tamaño, numeradas desde 0. Esa disposición es lo que hace que los arreglos se lean rápido. Si el bloque empieza en la dirección s y cada celda ocupa c bytes, entonces a[i] está en la dirección s + i × c. La computadora lo calcula con una multiplicación y una suma y salta directamente ahí, sea i igual a 3 o a 3 000 000. Las notas del MIT dan "get at(i)" y "set at(i, x)" de un arreglo como Θ(1), lo que significa que el costo no crece con la longitud.

La misma disposición hace que los cambios en el medio sean lentos. Supón que el arreglo contiene 7, 3, 9, 4, 6 y quieres poner 1 al principio. No hay hueco delante del 7, así que primero cada valor tiene que moverse una celda a la derecha, empezando por el último para no sobrescribir nada. Son 5 movimientos y 1 escritura: 6 pasos. Quitar el primer valor es lo contrario: leerlo y luego mover los otros 4 valores una celda a la izquierda. Insertar en la posición i de un arreglo de n valores cuesta n − i movimientos más una escritura, así que el principio es el peor lugar y el final, el mejor.

Cuando el bloque se llena

Un bloque de memoria tiene un tamaño fijo, así que ¿qué pasa cuando agregas un valor y todas las celdas están ocupadas? El arreglo tiene que pedir un bloque nuevo y más grande y copiar ahí todos los valores antes de poder escribir el nuevo. En el laboratorio, agregar un valor al bloque lleno de 5 cuesta 5 copias y 1 escritura. Si el arreglo creciera de una en una celda, cada push copiaría todo, y n push costarían unas n²/2 copias.

La solución que describen las notas del MIT es crecer mucho de una vez, por ejemplo duplicando el tamaño. Empezando con capacidad 1, las copias ocurren cuando el arreglo tiene 1, 2, 4, 8 y 16 valores, así que 17 push cuestan en total 1 + 2 + 4 + 8 + 16 = 31 copias, menos de 2 por push. Un push suelto puede seguir siendo lento, pero cualquier serie larga de push sale en promedio a un costo constante por push. Esto se llama tiempo Θ(1) amortizado. Un arreglo de JavaScript se comporta así visto desde fuera: MDN describe los arreglos como redimensionables, y push y pop trabajan en el final, que es el extremo barato.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, un paso
a.push(8);              // barato: el final
a.unshift(1);           // cada valor se mueve una celda a la derecha
console.log(a.join(" ")); // 1 7 3 9 4 6 8