Saltearse al contenido

list por dentro

Una list no es una estructura de datos sofisticada. Es un bloque contiguo de punteros que crece por bloques y que guarda tres cosas: dónde empieza, cuántos elementos usa y cuántos caben. Entender esas tres cifras explica por qué append es gratis, por qué insert(0) no lo es y por qué una lista de mil elementos ocupa más de lo que parece.

Una lista es un array de punteros con sitio de sobra al final; todo lo demás se deduce de ahí.

Una lista con cinco elementos y capacidad para ocho
len() = 5 · capacidad = 8 → 8 B → 8 B → 8 B → 8 B → 8 B libre 8 B libre 8 B libre 8 B = 56 B + 8 × capacidad

Los tres huecos de la derecha ya están reservados y pagados. `append` escribe en el primero libre y sube la longitud: no pide memoria.

La capacidad crece con un factor de 1/8, no de uno en uno:

Cuándo se redimensiona una lista
len() Capacidad reservada
1 4
5 8
9 16
17 24
25 32
33 40
41 52
53 64

python mediciones/02-11-coste.py

Ese 12,5 % de más es lo que convierte append en O(1) amortizado: casi siempre escribe en un hueco, y sólo de vez en cuando paga una copia de toda la lista a un bloque nuevo. El coste medio es constante; el coste puntual de esa copia es O(n), y en un contenedor con memoria justa es el momento en que el proceso muere.

Añadir por el final y por el principio
Operación Coste Por qué
append(x) 31 ns escribe en el hueco reservado
insert(0, x) en lista de 20 000 5.0 µs mueve los 20 000 punteros

python mediciones/02-11-coste.py

Ciento sesenta veces. Y en un bucle de n inserciones al principio, el total es O(n²): con cien mil elementos, 1,2 segundos en lugar de 5 milisegundos.

Construir un millón de elementos
Forma Tiempo Frente a la comprensión
Comprensión [i*2 for i in ...] 55.0 ms 1.00×
for con append 61.9 ms 1.13×
list(map(lambda ...)) 86.7 ms 1.58×

python mediciones/02-01-04-secuencias.py

La comprensión gana por dos motivos: no llama a un método por elemento y crea la lista con el tamaño ya estimado. El map con lambda pierde porque paga una llamada a función Python por elemento; con una función de C (map(str, datos)) sería la más rápida de las tres.

Tres operaciones de lista copian y una no:

a = [3, 1, 2]
b = a[:] # copia
c = sorted(a) # copia (y ordena la copia)
a.sort() # NO copia: ordena en su sitio, devuelve None
d = a[::-1] # copia invertida
a.reverse() # NO copia: invierte en su sitio

La confusión clásica es a = a.sort(), que deja a en None. Los métodos que mutan devuelven None a propósito, para que no se pueda encadenar y creer que hay un objeto nuevo. Las funciones que no mutan (sorted, reversed) devuelven un objeto nuevo, y por eso reversed(a) no gasta memoria: devuelve un iterador, no una lista.

  • Como cola. pop(0) es O(n); usa deque (capítulo 01).
  • Como almacén de números. Un millón de enteros son 40 MB en lista y 4 en array (capítulo 04).
  • Como conjunto de pertenencia. x in lista recorre; un set responde en 30 ns (capítulo 06).
  • Como registro de campos fijos. Una tupla o una dataclass con slots comunica mejor y pesa menos (capítulo 03).

Este código tarda 40 segundos con 200 000 filas. Explica dónde está el problema y reescríbelo:

def agrupar(filas):
grupos = []
for fila in filas:
for g in grupos:
if g[0] == fila.categoria:
g[1].append(fila)
break
else:
grupos.append([fila.categoria, [fila]])
return grupos
Solución

Hay dos problemas, y el segundo es el grave.

El primero: la búsqueda del grupo es lineal (for g in grupos), así que con 200 000 filas y muchas categorías el bucle interno recorre la lista de grupos cada vez.

El segundo: grupos.append(...) es barato, pero el for g in grupos crece con el número de categorías. Si hay 50 000 categorías distintas, son 5 000 millones de comparaciones.

La solución es un diccionario, que encuentra el grupo en tiempo constante:

from collections import defaultdict
def agrupar(filas):
grupos = defaultdict(list)
for fila in filas:
grupos[fila.categoria].append(fila)
return grupos

De O(n × k) a O(n). Y si hace falta el formato de lista de pares, list(grupos.items()) al final.

Comprobación con datos de ejemplo:

from types import SimpleNamespace
filas = [SimpleNamespace(categoria=c, valor=i)
for i, c in enumerate(["vigas", "pilares", "vigas", "losas", "pilares", "vigas"])]
grupos = agrupar(filas)
for categoria, items in sorted(grupos.items()):
print(categoria, "->", [f.valor for f in items])
assert len(grupos["vigas"]) == 3, "hay tres filas de vigas"
print("como lista de pares:", len(list(grupos.items())))
  • Ramalho, L. Fluent Python, 2ª ed. Capítulo 2: secuencias y sus implementaciones.
  • CPython 3.13: Objects/listobject.c (list_resize, list_preallocate_exact).
  • Mediciones: mediciones/02-01-04-secuencias.py y mediciones/02-11-coste.py.
  • 01 · Secuencias: el mapa donde encaja la lista.
  • 03 · tuple: la versión sin reserva ni mutabilidad.
  • 06 · set y tablas hash: la estructura que resuelve el ejercicio en O(1).