Memoria contigua e indexación de arreglos O(1)

Al finalizar este tema

Podrás explicar matemáticamente por qué el acceso mediante índices en un arreglo es O(1), comprender las ventajas y desventajas de la memoria contigua y entender las diferencias de rendimiento entre los arreglos y las listas enlazadas.

¿Por qué son rápidos los arreglos?

numbers = [10, 20, 30, 40, 50]
print(numbers[3])  # 40 — instant access!

Ya sean 5 o 5 millones, el tiempo de acceso mediante un índice es siempre el mismo. Esto es O(1), es decir, acceso en tiempo constante.

¿Por qué ocurre esto? Porque los arreglos se almacenan de forma contigua en la memoria.

Memoria contigua: la clave de los arreglos

Memory addresses:  1000  1004  1008  1012  1016
Values:            [10]  [20]  [30]  [40]  [50]
Indices:           0     1     2     3     4

Cada elemento del array se almacena de forma consecutiva en la memoria, sin espacios intermedios. Si cada entero ocupa 4 bytes:

• numbers[0] → dirección 1000
• numbers[1] → dirección 1004
• numbers[2] → dirección 1008
• numbers[3] → dirección 1012

Fórmula de indexación

Dirección del elemento = Dirección inicial + (índice × tamaño del elemento)

numbers[3] = 1000 + (3 × 4) = 1012

Este cálculo implica una suma y una multiplicación. No importa si el tamaño del arreglo es de 5 elementos o de 500 millones; el tiempo de ejecución es el mismo. Por lo tanto, es O(1).

Comparación con listas enlazadas

En una lista enlazada, cada nodo almacena la dirección del siguiente nodo. Los datos se almacenan de forma dispersa en la memoria.

Memoria:  [10|→1500]  ...  [20|→2300]  ...  [30|→1800]  ...  [40|→2100]

Para encontrar el tercer elemento:
  Nodo 0 (1000) → sigue el puntero
  Nodo 1 (1500) → sigue el puntero
  Nodo 2 (2300) → sigue el puntero
  Nodo 3 (1800) ← ¡Aquí!

Para encontrar el tercer elemento, hay que recorrerlo uno a uno desde el índice 0. Para encontrar el enésimo elemento, se requieren n desplazamientos → O(n).

La estructura real de las listas en Python

Las listas de Python, list, son diferentes de los arreglos de C. Son un arreglo de punteros.

Python list:  [ptr0][ptr1][ptr2][ptr3]
                ↓     ↓     ↓     ↓
              [10]  ["hi"] [3.14] [[1,2]]

Dado que el tamaño de un puntero (dirección) es fijo (8 bytes en sistemas de 64 bits), el propio arreglo de punteros ocupa una región de memoria contigua. La fórmula de indexación sigue siendo aplicable, por lo que la complejidad es O(1).

# Lista de Python: posible almacenar varios tipos (como matriz de punteros)
mixed = [42, "hello", 3.14, [1, 2, 3]]
print(mixed[2])  # 3.14 — O(1)

Sin embargo, como los datos reales están dispersos por toda la memoria, la eficiencia de la caché es menor que la de los arreglos de C.

Arreglos de NumPy: memoria verdaderamente contigua

import numpy as np

# NumPy almacena datos contiguamente, como un arreglo en C
arr = np.array([1, 2, 3, 4, 5], dtype=np.int32)
# Memoria: [00000001 00000002 00000003 00000004 00000005]
#         Contiguo sin huecos, de 4 bytes cada uno

Una de las razones por las que NumPy es decenas de veces más rápido que las listas de Python es su diseño de memoria contigua.

Optimización para la caché

Cuando la CPU recupera datos de la memoria, también carga en la línea de caché (generalmente 64 bytes) los datos cercanos a la dirección solicitada.

Acceso secuencial a la matriz:
  Acceso a arr[0] → se cargan en caché arr[0]~arr[15]
  Acceso a arr[1] → ¡Acierto de caché! (ya cargado)
  Acceso a arr[2] → ¡Acierto de caché!
  ...

Acceso en lista enlazada:
  Acceso a node0 → se carga el entorno en caché
  Acceso a node1 → ¡otra dirección! Fallo de caché → recarga desde memoria
  Acceso a node2 → ¡otra dirección! Fallo de caché
  ...

Los arrays son contiguos, lo que favorece una alta tasa de aciertos de caché; las listas enlazadas están dispersas, lo que provoca frecuentes fallos de caché. En las CPU modernas, un fallo de caché es más de 100 veces más lento que un acierto de caché.

Limitaciones de los arrays: inserción y eliminación

Inserción en el medio del array (insertar 25 en el índice 2):

Before: [10][20][30][40][50]
                 ↓
Paso 1: [10][20][  ][30][40][50]  ← Mover 30, 40, 50 una posición hacia atrás
Paso 2: [10][20][25][30][40][50]  ← Insertar 25 en el espacio vacío

Dado que todos los elementos posteriores deben desplazarse, la complejidad es O(n). Lo mismo ocurre con la eliminación: los elementos restantes se desplazan hacia adelante para llenar el espacio vacío.

Disposición de memoria de una matriz bidimensional

Mayor por fila (C, Python, NumPy predeterminado):
[[1, 2, 3],     Memoria: [1][2][3][4][5][6]
 [4, 5, 6]]     → Almacenado en orden de fila

Column-major (Fortran, MATLAB):
[[1, 2, 3],     Memoria: [1][4][2][5][3][6]
 [4, 5, 6]]     → Almacenado en orden de columna

import numpy as np

arr = np.array([[1, 2, 3], [4, 5, 6]])

# Orden C (mayor por fila, predeterminado)
print(arr.flags['C_CONTIGUOUS'])  # True

# Fortran order
arr_f = np.asfortranarray(arr)
print(arr_f.flags['F_CONTIGUOUS'])  # True

Cuando hay más iteraciones en dirección de fila, el orden de almacenamiento en memoria por filas (row-major) es más eficiente para la caché; cuando hay más iteraciones en dirección de columna, el orden de almacenamiento en memoria por columnas (column-major) es más eficiente. NumPy utiliza por defecto el orden C (almacenamiento en memoria por filas). Esta es la razón por la que las operaciones en dirección de fila (axis=1) suelen ser más rápidas que las operaciones en dirección de columna (axis=0), ya que el patrón de acceso a la memoria es más favorable para la caché.

Arreglos dinámicos: arreglos cuyo tamaño aumenta

Los arreglos tienen un tamaño fijo. Las listas de Python son arreglos dinámicos: cuando se llenan, asignan un arreglo más grande y copian los datos.

import sys

items = []
prev_size = 0
for i in range(20):
    items.append(i)
    size = sys.getsizeof(items)
    if size != prev_size:
        print(f"len={len(items):2d}, capacity changed: {prev_size} → {size} bytes")
        prev_size = size

# len= 1, capacity changed: 56 → 88 bytes
# len= 5, capacity changed: 88 → 120 bytes
# len= 9, capacity changed: 120 → 184 bytes
# len=17, capacity changed: 184 → 248 bytes

Python normalmente reserva espacio adicional equivalente a 1.125 veces el tamaño actual + una constante. Si se incrementa en una unidad cada vez, es necesario copiar todo el contenido en cada paso (O(n)), pero si se amplía por múltiplos, se logra una complejidad amortizada de O(1).

Resumen clave

La razón por la que los arrays tienen una complejidad de O(1) es una fórmula sencilla: "memoria contigua + una multiplicación". Comprender este principio permite conectar de forma natural por qué NumPy es más rápido que una lista de Python, por qué las bases de datos utilizan índices y por qué la optimización de la caché es importante.

Resumen práctico: si hay muchos accesos por índice, usa arrays; si hay muchas inserciones/eliminaciones, usa listas enlazadas. La lista de Python es adecuada en la mayoría de los casos, pero para cálculos numéricos es decenas de veces más rápido usar NumPy, ya que utiliza memoria verdaderamente contigua.