Estructuras de datos y su coste real¶

De un vistazo

Materia: Capa 0 · Cimientos · Tiempo de lectura: ~30 min · Requisitos previos: Modelo de ejecución (memoria, direcciones, stack vs heap).

En una frase: una estructura de datos es cómo colocas los datos en la memoria, y esa colocación decide qué operaciones te salen baratas y cuáles carísimas. Vas a entender el coste real de las estructuras que usas cada día —no su nombre, sino qué pagas por cada cosa.

Por qué esto importa¶

Casi nadie elige mal un algoritmo; casi todo el mundo elige mal una estructura de datos, y ni se entera. El código funciona con 100 elementos y se arrastra con 100.000. La causa casi siempre es la misma: se usó una estructura cuyo coste no encajaba con las operaciones que más se hacían.

Preguntas que solo se responden entendiendo esto:

¿Por qué buscar "¿está este email en la lista?" es instantáneo con un Set y una tortura recorriendo un array?
¿Por qué insertar por el medio de un array es caro pero al final es barato?
¿Por qué una lista enlazada, que "en teoría" inserta en O(1), en la práctica suele ir más lenta que un array?
¿Qué es de verdad un array en PHP y por qué no es un array?

La estructura de datos es la decisión de diseño más apalancada y más invisible que tomas. Cambiar de estructura convierte código de 10 segundos en código de 10 milisegundos sin tocar el algoritmo.

Intuición primero: la forma manda sobre la operación¶

Recupera el archivador de la lección anterior: la memoria es una fila de cajones numerados. Una estructura de datos es una manera de repartir tus datos por esos cajones y de recordar dónde está cada cosa.

Y aquí está la idea que lo gobierna todo:

No existe la estructura "buena". Existe la estructura buena para las operaciones que vas a hacer más. Cada estructura es un trato: te abarata unas operaciones a cambio de encarecerte otras.

Piensa en cómo guardarías 1.000 libros:

Todos en una estantería, pegados y en orden de compra (como un array): coger el libro nº 738 es instantáneo (cuentas posiciones). Pero meter un libro nuevo en medio obliga a correr todos los de la derecha.
Cada libro con una nota que dice dónde está el siguiente (como una lista enlazada): meter uno nuevo es solo reescribir dos notas. Pero para llegar al nº 738 tienes que seguir 737 notas una a una.
Ordenados por título en baldas etiquetadas A, B, C… (como un hash table): encuentras "El Quijote" yendo directo a la balda Q sin mirar los demás. Pero pierdes el orden de compra.

Ninguna gana en todo. La pregunta correcta nunca es "¿cuál es mejor?", sino "¿qué voy a hacer más: acceder por posición, insertar por el medio, o buscar por contenido?".

El detalle¶

1. El array: contigüidad y acceso directo¶

Un array guarda sus elementos en cajones consecutivos de memoria. Si sabes dónde empieza y cuánto ocupa cada elemento, la dirección del elemento i es pura aritmética:

dirección(i) = inicio + i × tamaño_elemento

Eso es acceso aleatorio O(1): llegar al elemento 5 o al 5.000.000 cuesta lo mismo, una multiplicación y una suma. Es la superpotencia del array.

graph LR
  subgraph "Array en memoria (cajones contiguos)"
    direction LR
    a0["índice 0<br/>'ana'"] --- a1["índice 1<br/>'luis'"] --- a2["índice 2<br/>'eva'"] --- a3["índice 3<br/>'juan'"]
  end

La contigüidad tiene un segundo regalo, casi más importante que el primero: la caché. Recuerda que ir a RAM cuesta ~100 ns, pero la CPU no trae un byte, trae un bloque entero (una línea de caché, ~64 bytes) a su caché rápida. Como el array está pegado, cuando lees el elemento 0 te traes "gratis" el 1, 2, 3… Recorrer un array es acariciar la caché: rapidísimo. Esto se llama localidad espacial y es la razón oculta de por qué los arrays vuelan.

El precio del array:

Insertar/borrar por el medio es O(n): hay que desplazar todos los elementos posteriores un hueco.
Tamaño: un array "puro" (como en C, o SplFixedArray en PHP) tiene tamaño fijo; para crecer hay que pedir uno más grande y copiar.

2. El array dinámico: crecer sin que duela (casi nunca)¶

¿Cómo tienen entonces PHP, Python o Java "arrays que crecen"? Con el truco del array dinámico: por dentro hay un array de tamaño fijo con capacidad de sobra. Mientras haya hueco, añadir al final es O(1). Cuando se llena, se reserva uno del doble de tamaño y se copia todo (O(n) esa vez).

Parece que añadir es "a veces O(1), a veces O(n)", pero si repartes el coste de las copias entre todas las inserciones, sale O(1) amortizado: duplicar hace que las copias caras sean cada vez más raras. (La palabra amortizado la desarrollamos en la lección de Complejidad; quédate con la intuición: un coste caro pero tan infrecuente que, repartido, es barato.)

Por qué se dobla y no se suma

Si al llenarse creciera de 10 en 10, cada pocas inserciones habría que copiar todo → coste total O(n²). Doblando, el número de copias totales es proporcional a n, no a n². Es la diferencia entre que array[] = x sea usable o inutilizable a escala.

3. La lista enlazada: punteros en vez de contigüidad¶

Una lista enlazada no guarda los elementos juntos. Cada elemento (nodo) vive donde sea en el heap y contiene su dato más la dirección del siguiente nodo. Los une una cadena de punteros.

graph LR
  n0["'ana'<br/>next →"] --> n1["'luis'<br/>next →"] --> n2["'eva'<br/>next →"] --> nil["∅ (fin)"]

El trato se invierte respecto al array:

Insertar/borrar es O(1) si ya tienes el nodo en la mano: solo reescribes un par de punteros, sin desplazar nada.
Acceder al elemento i es O(n): no hay aritmética posible; hay que seguir la cadena desde el principio, salto a salto.

Y aquí el desengaño que casi nadie te cuenta:

La lista enlazada es más lenta de lo que promete la teoría

Sus nodos están dispersos por el heap, así que recorrerla es un festival de saltos a direcciones aleatorias → cada salto es un posible fallo de caché (~100 ns). Un array del mismo tamaño se recorre pegado a la caché. En la práctica, para el 90% de los usos, un array dinámico le gana a una lista enlazada incluso en operaciones donde la lista "debería" ganar, por pura localidad. La lista brilla en casos concretos: inserciones/borrados frecuentes en los extremos o en posiciones que ya tienes referenciadas, sin necesidad de recorrer.

Esta es una lección de fondo de toda la Capa 0: la complejidad asintótica (la teoría) no es toda la historia; la realidad de la máquina —la caché— manda tanto como la O grande.

4. El hash table: buscar por contenido en O(1)¶

Array y lista te encuentran cosas por posición. Pero muchísimas veces quieres encontrarlas por contenido: "¿existe el usuario con email X?", "dame el precio del producto con SKU Y". Recorrer buscando es O(n). El hash table (tabla hash) lo hace en O(1) promedio.

La idea: una función hash convierte tu clave (el email, el SKU) en un número, y ese número dice en qué cubo (posición de un array interno) guardar el valor. Para buscar, vuelves a aplicar la función a la clave y vas directo al cubo. No recorres nada.

graph LR
  k["clave<br/>'ana@x.com'"] --> h["función hash"] --> idx["cubo 3"]
  idx --> bucket["array interno<br/>[_, _, _, (ana), _, _, _]"]

El truco tiene una arruga: dos claves distintas pueden caer en el mismo cubo (colisión). Se resuelve, por ejemplo, guardando en cada cubo una pequeña lista de los que colisionaron. Si la función hash reparte bien y la tabla no está saturada, las colisiones son raras y la búsqueda sigue siendo O(1) de media.

El O(1) del hash es promedio, no garantizado

Con una función hash mala (o un atacante que fabrica claves que colisionan a propósito), todo cae en el mismo cubo y el hash degenera en una lista: O(n). De ahí ataques reales de hash-flooding contra servidores web. El O(1) es un promedio bajo buenas condiciones, no una ley.

El otro precio del hash: pierde el orden y no responde bien a "dame el rango de claves entre A y M" (para eso están los árboles, abajo).

5. Árboles balanceados: el término medio ordenado¶

¿Y si quieres buscar rápido y mantener el orden (rangos, "el siguiente mayor que X", recorrer ordenado)? Un árbol de búsqueda balanceado (como un árbol rojo-negro o un B-tree) da O(log n) en búsqueda, inserción y borrado, manteniendo los datos ordenados.

O(log n) significa que doblar los datos solo añade un nivel al árbol: buscar en mil millones de elementos son ~30 pasos. No es tan rápido como el O(1) del hash, pero conserva el orden. Los índices de las bases de datos son B-trees precisamente por esto — lo verás a fondo en la Capa 2.

6. Pilas y colas: disciplina de acceso¶

Pila (stack) y cola (queue) no son estructuras de almacenamiento nuevas, sino disciplinas de acceso que impones encima de un array o una lista:

Pila (LIFO): solo entras/sales por un extremo. Último en entrar, primero en salir. Es lo que usa la máquina para las llamadas a funciones (lección anterior), deshacer/rehacer, evaluar expresiones.
Cola (FIFO): entras por un extremo, sales por el otro. Primero en entrar, primero en salir. Colas de tareas, buffers, procesamiento por lotes.

Ambas ofrecen sus operaciones en O(1). Su valor no es la velocidad, sino que el orden de salida modela el problema (una cola de impresión respeta quién llegó antes).

Cómo se ve en la práctica¶

El array de PHP no es un array. Es la trampa más común. Lo que PHP llama array es en realidad un hash table ordenado (un ordered map): mantiene el orden de inserción y te deja usar claves. Es comodísimo, pero pagas por dentro el coste de un hash (más memoria por elemento, menos localidad de caché) aunque solo lo uses como lista numérica.

// Esto NO es un array contiguo de C; es un hashmap ordenado.
$nums = [10, 20, 30];       // claves 0,1,2 en un hash table
$nums['x'] = 99;            // ...y le puedes meter una clave string sin quejarse

// ¿Necesitas de verdad millones de enteros pegados y con poca memoria?
$fijo = new SplFixedArray(1_000_000);  // esto sí es contiguo y compacto

Y la elección que de verdad cambia el rendimiento:

// ❌ ¿Está este id entre los 100.000 bloqueados? Recorriendo: O(n) por consulta
if (in_array($id, $listaBloqueados)) { ... }   // lento a lo bestia en un bucle

// ✅ Metiendo los ids como CLAVES de un hash: O(1) por consulta
$bloqueados = array_flip($listaBloqueados);     // una vez
if (isset($bloqueados[$id])) { ... }            // instantáneo

La segunda versión no cambia el algoritmo: cambia la estructura con la que preguntas. Eso es toda la lección.

Lo que sacrificas / errores comunes¶

Elegir por costumbre, no por operación dominante. Antes de elegir, pregunta: ¿qué operación haré millones de veces? Optimiza esa.
Fiarse solo de la O grande e ignorar la caché. Un array suele ganar a una lista enlazada aunque la teoría diga lo contrario. Mide.
Usar un array/lista para pertenencia ("¿está X?"). Eso casi siempre pide un Set/hash. El in_array en un bucle es el clásico asesino de rendimiento.
Creer que el hash siempre es O(1). Es O(1) promedio y con buen reparto. Puede degenerar.
Meter en un hash algo que necesitas ordenado o por rangos. Ahí quieres un árbol.

Resumen¶

Una estructura de datos es cómo colocas los datos en memoria; esa forma decide qué operaciones son baratas y cuáles caras. No hay "la mejor", hay "la mejor para tus operaciones".
Array: acceso por índice O(1) y amor por la caché; insertar por el medio O(n). El array dinámico crece doblando → append O(1) amortizado.
Lista enlazada: insertar/borrar O(1) con el nodo en mano, acceso O(n); en la práctica la caché la penaliza más de lo que la teoría sugiere.
Hash table: búsqueda por contenido O(1) promedio, a cambio de perder el orden y depender de una buena función hash.
Árbol balanceado: O(log n) manteniendo el orden (la base de los índices de BD). Pila/cola: disciplinas de acceso (LIFO/FIFO) que modelan el orden del problema.

Ejercicios socráticos¶

Razónalos con lo de esta lección y la de memoria. No busques fuera.

Tienes que comprobar, para cada uno de 50.000 pedidos, si su cliente está en una lista negra de 20.000 ids. Con in_array sobre la lista tarda una eternidad. Sin cambiar el algoritmo, ¿qué estructura usas para la lista negra y por qué pasa de O(n) a O(1) cada comprobación? ¿Cuántas comprobaciones te ahorras en total, en órdenes de magnitud?
La teoría dice que insertar al principio de una lista enlazada es O(1) y al principio de un array es O(n). Aun así, para recorrer y sumar un millón de enteros, el array suele ganar. Explica por qué, usando la palabra "caché".
¿Por qué un array dinámico dobla su capacidad al llenarse en vez de crecer de uno en uno o de diez en diez? ¿Qué complejidad total tendría añadir n elementos en cada caso?
Quieres, sobre un conjunto de precios: (a) preguntar "¿existe el precio exacto 9,99?" muy a menudo, y (b) a veces pedir "todos los precios entre 5 y 10 ordenados". ¿Una sola estructura te da las dos baratas? Si no, ¿cuál eliges para cada una y qué sacrificas?
El array de PHP mantiene el orden de inserción y admite claves string. ¿Qué estructura de las de esta lección crees que tiene por debajo, y qué precio pagas (en memoria y en caché) por usarlo como si fuera una simple lista de enteros?

Repaso espaciado¶

A Anki (repasos.md). Preguntas que obliguen a razonar.

[ ] ¿Por qué el acceso por índice en un array es O(1)? (Responde con la fórmula de la dirección.)
[ ] ¿Por qué recorrer un array es más rápido que recorrer una lista enlazada del mismo tamaño, aunque ambas sean O(n)?
[ ] ¿Qué es una colisión en un hash table y en qué caso hace que el O(1) degenere a O(n)?
[ ] ¿Cuándo eliges un árbol balanceado (O(log n)) en lugar de un hash table (O(1))?
[ ] ¿Qué operación es cara en un array y barata en una lista enlazada, y viceversa?

Para seguir tirando del hilo¶

Grokking Algorithms (Aditya Bhargava) — visual y muy accesible para asentar arrays, listas y hashes.
Charla "Why you should never use linked lists" y benchmarks array-vs-list: para ver la caché mandando sobre la teoría.
Experimento: en tu lenguaje, mide el tiempo de sumar 10M de enteros en un array dinámico vs. una lista enlazada. La diferencia te asienta la lección 3 más que releerla.