Saltearse al contenido

Elegir estructura por coste

Todo el mundo aprende la misma tabla. list para secuencias, dict para búsquedas, set para pertenencia, tuple para lo inmutable. Es correcta, y es insuficiente: no distingue entre una lista de cien elementos y una de diez millones, ni entre guardar enteros y guardar diccionarios. La pregunta profesional no es cuál es la más rápida, sino cuántos elementos, de qué tipo, con qué operación dominante. Este capítulo responde esas tres preguntas con números medidos, no con adjetivos.

El contenedor casi nunca es el coste. El coste son los objetos que guardas dentro.

¿Cuántos elementos? Por debajo de mil, cualquier estructura sirve y elegir por rendimiento es ruido. Por encima de un millón, la representación decide si el programa cabe en memoria o muere con MemoryError. La frontera incómoda está en cien mil: suficientemente grande para que importe, suficientemente pequeño para que nadie lo mida.

¿Qué guardo? Un objeto Python cualquiera arrastra una cabecera de 16 bytes antes de contener un solo dato: ocho del contador de referencias, ocho del puntero al tipo. Un número entero ocupa 28. Si guardas un millón de objetos, pagas esa cabecera un millón de veces. Si guardas valores crudos en un array, no pagas ninguna.

¿Qué operación domina? Recorrer, buscar por clave, comprobar pertenencia, insertar al principio, ordenar. Cada una tiene una estructura que la hace gratuita y otra que la convierte en un bucle escondido.

Los tres criterios, resueltos
Si el uso dominante es… La estructura es… Y el rival a evitar es…
Recorrer en orden, crecer al final list insert(0, x)
Acceso por clave dict Lista de tuplas + búsqueda lineal
Comprobar pertenencia set x in list
Cola por ambos extremos deque list.pop(0)
Datos numéricos homogéneos array o numpy list[float]
Registro de campos fijos dataclass(slots=True) dict por fila

Regla de bolsillo; los capítulos siguientes justifican cada fila.

El criterio de la ABC y el criterio del coste

Sección titulada «El criterio de la ABC y el criterio del coste»

La guía canónica para elegir estructura no habla de bytes: habla de contratos. collections.abc define tres familias —Set, Sequence y Mapping—, cada una con su versión mutable e inmutable, y elegir consiste en decidir cuál describe el problema. ¿Los elementos se identifican por posición? Sequence. ¿Por pertenencia? Set. ¿Por una clave distinta del índice? Mapping.

Ese criterio es correcto y este capítulo no lo discute. Primero el contrato, porque una estructura que no expresa el problema se paga en código de más, no en memoria.

Pero el contrato no distingue entre list y tuple cuando el problema es «una secuencia que no crece» —ambas son Sequence—, ni entre un dict y una lista de tuplas cuando el problema es «cien mil filas con un id». Para eso hace falta un segundo criterio: cuánto cuesta. Lo que sigue asume el contrato como punto de partida y añade la aritmética que la guía deja fuera.

Antes de comparar contenedores hay que saber cuánto pesa lo que metes dentro, porque ese peso se multiplica.

Tamaño de los objetos, medido
Objeto bytes
int 0 28 B
int 10**18 32 B
float 3.14 24 B
str vacío 41 B
str de 12 caracteres 52 B
str de 1 000 caracteres ASCII 1 041 B
bytes de 1 000 1 033 B

python mediciones/02-11-coste.py

Dos conclusiones que cambian decisiones. La primera: el entero no es un número, es un objeto de 28 bytes, y crece a 32 cuando no cabe en 30 bits. Una lista de un millón de enteros no pesa ocho megabytes de punteros: pesa ocho de punteros más veintiocho de objetos, menos los que caen en la caché de enteros pequeños, que CPython reutiliza entre −5 y 256.

La segunda: una cadena de texto es el objeto más caro que existe por unidad de información. Mil caracteres cuestan 1 041 bytes porque str es compacto en ASCII (un byte por carácter) pero arrastra 41 de cabecera. Si guardas texto en una estructura de un millón de filas, el texto es el problema, no la estructura.

Con mil elementos dentro, estas son las estructuras que ofrece la biblioteca estándar. La columna «por elemento» es el incremental real: se mide el contenedor lleno y se le resta el vacío.

Contenedores, vacíos y con 1 000 elementos
Tipo vacío 1 000 elem. por elemento
list 56 B 7.9 KB 8.0 B
tuple 40 B 7.9 KB 8.0 B
dict 64 B 36.1 KB 36.9 B
set 216 B 32.2 KB 32.8 B
deque 760 B 8.5 KB 7.9 B
array('i') 80 B 4.1 KB 4.1 B
array('q') 80 B 8.1 KB 8.2 B
str ASCII 41 B 1.0 KB 1.0 B
bytes 33 B 1.0 KB 1.0 B

python mediciones/02-11-coste.py El incremento incluye la sobreasignación, no sólo el dato.

Cuatro lecturas.

list y tuple cuestan lo mismo por elemento: ocho bytes, un puntero. La diferencia entre ambas no está en el tamaño por elemento sino en que la tupla no sobreasigna, así que ahorra hasta un 12 % en el total. Ese 12 % rara vez justifica perder la mutabilidad.

array es cuatro veces más barato que list para enteros de 32 bits, porque guarda el valor y no el puntero al valor. Pero ese ahorro es una trampa si los enteros son grandes: array('i') desborda a partir de 2³¹−1, y array no acepta float y str mezclados.

dict y set son caros por diseño: 36,9 y 32,8 bytes por entrada. Un set de un millón de identificadores cuesta 32 MB sólo en tabla hash, antes de contar los objetos. Ese es el precio de la búsqueda en tiempo constante, y suele valer la pena, pero hay que saberlo.

deque vacío ya pesa 760 bytes porque reserva un bloque de 64 punteros al crearse. Es un contenedor con estructura interna, no una lista.

Una lista no reserva memoria de uno en uno. Cuando se llena, pide más de lo que necesita, y lo hace con un factor de sobreasignación de un octavo.

Capacidad real de una lista según su longitud
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 Capacidad deducida del tamaño asignado: (tamaño − 56) / 8.

Esa sobreasignación es lo que hace que append sea O(1) amortizado: casi siempre escribe en un hueco ya reservado. El 12 % de memoria extra es el precio. La consecuencia práctica no es el 12 %, es el pico transitorio: al redimensionar, CPython reserva el bloque nuevo antes de liberar el viejo, así que durante un instante una lista de un millón de elementos necesita casi el doble. En un contenedor con memoria justa, ese instante es un MemoryError.

Cien mil registros, cinco formas de guardarlos

Sección titulada «Cien mil registros, cinco formas de guardarlos»

Aquí es donde la elección deja de ser estética. Los mismos datos —un identificador, un nombre, una cantidad, un precio— guardados de cinco maneras, medidos con tracemalloc, que cuenta asignaciones reales y no tamaños declarados.

100 000 filas de cuatro campos
Representación pico total por fila
list[tuple] 17.9 MB 188 B
list[NamedTuple] 18.7 MB 196 B
list[dataclass(slots=True)] 17.2 MB 180 B
list[dataclass] 21.0 MB 220 B
list[dict] 28.6 MB 300 B
dict[int, tuple] 22.5 MB 236 B

python mediciones/02-11-coste.py tracemalloc, memoria pico durante la construcción.

Coste por fila, 100 000 registros de cuatro campos
dataclass(slots) 180 B tuple 188 B NamedTuple 196 B dataclass 220 B dict[int, tuple] 236 B dict 300 B

La forma que todo el mundo escribe primero —una lista de diccionarios— es la más cara: un 60 % más que una tupla (300 frente a 188 B) y un 67 % más que la misma dataclass con slots (300 frente a 180 B).

La representación que todo el mundo escribe primero —una lista de diccionarios, porque es lo que devuelve csv.DictReader— cuesta un 60 % más que una lista de tuplas. En cien mil filas son once megabytes de diferencia; en diez millones, 2,9 GB contra 1,8 GB, que es la diferencia entre que el programa corra o no.

Y el resultado más útil de la tabla es el que casi nadie espera: dataclass(slots=True) es más densa que una tupla (180 contra 188 bytes) y a la vez tiene nombres de campo, __repr__ legible, comparación por valor y tipado. Es la mejor relación entre legibilidad y memoria que ofrece el lenguaje. Sin slots, la misma dataclass cuesta 220: un 22 % más que con ellos.

El porqué de esa diferencia está en la anatomía de una sola fila:

Anatomía de una fila
Objeto bytes
tuple de 4 campos 72 B
dict de 4 claves 184 B
dataclass (instancia, sin slots) 48 B
dataclass(slots=True) (instancia) 64 B
str del nombre 52 B
int del id 28 B
float del precio 24 B

python mediciones/02-11-coste.py

Fíjate en la aparente contradicción: la instancia con slots pesa más que la instancia normal (64 contra 48), y sin embargo la fila completa pesa menos. La explicación es que la instancia normal no guarda los atributos: guarda un puntero a un diccionario, y ese diccionario es el que cuesta. Con slots, los cuatro atributos viven dentro del objeto. Pagas ocho bytes más de instancia para ahorrarte un diccionario entero.

Si el contenido es numérico y homogéneo, hay una salida que elimina los objetos por completo.

100 000 enteros
Representación pico total por elemento
list[int] 3.8 MB 39.9 B
array('i') 0.4 MB 4.1 B

python mediciones/02-11-coste.py

Diez veces menos. Los 39,9 bytes de la lista se descomponen en ocho del puntero, veintiocho del objeto entero y una fracción de sobreasignación: el contenedor es el 20 % del coste. Optimizar la lista y dejar los enteros intactos es optimizar la parte pequeña del problema.

array no es la única respuesta. Cuando el dato es numérico de verdad —muchas filas, operaciones aritméticas, álgebra— numpy gana por dos motivos a la vez: guarda valores crudos en un bloque contiguo y ejecuta las operaciones en C sobre ese bloque. La regla es simple: si vas a sumar, restar o comparar columnas, numpy; si sólo vas a guardar y recuperar, array; si vas a mezclar tipos, dataclass con slots.

La memoria decide si el programa corre. El tiempo decide si sirve.

Pertenencia: 1 000 consultas sobre 10 000 elementos
Operación total por consulta
x in list (recorrido lineal) 30.0 ms 30.0 µs
x in set (hash) 0.04 ms 0.04 µs
x in dict (hash) 0.04 ms 0.04 µs

python mediciones/02-11-coste.py

Mil veces más rápido, y la brecha crece con el tamaño: el recorrido lineal es O(n), el hash es O(1) amortizado. Un x in lista dentro de un bucle sobre otra lista convierte un programa de dos segundos en uno de dos horas sin que el código lo delate.

El mismo patrón aparece en la inserción al principio:

Crecer por el principio
Operación medido por operación
append(x) × 10 000 0.3 ms 31 ns
insert(0, x) × 1 000 en lista de 20 000 5.0 ms 5.0 µs

python mediciones/02-11-coste.py

insert(0, x) es 160 veces más caro porque mueve todos los punteros una posición a la derecha. La solución no es optimizar el insert: es usar deque, o construir la secuencia al revés y darle la vuelta una sola vez al final.

  • Por debajo de diez mil elementos, elige la estructura que haga el código más legible. La diferencia entre 36 y 8 bytes por entrada son 280 KB: no es un problema, es una distracción.
  • Cuando el cuello de botella es de entrada/salida. Si el programa espera a la red o a la base de datos, cambiar list por deque no mueve la aguja. Mide antes de optimizar, y mide el programa completo.
  • Cuando slots te cuesta más de lo que te ahorra. Sin __dict__ no puedes añadir atributos en tiempo de ejecución, y algunos patrones de serialización dinámica dejan de funcionar. Si necesitas esa flexibilidad, los 40 bytes por fila son baratos.
  • Cuando el dato es heterogéneo y disperso. Un dict de 300 bytes por fila sigue siendo la opción correcta si cada fila tiene campos distintos. La densidad no compensa un modelo de datos mentiroso.

Tienes un CSV de cinco millones de filas con id, nombre, categoría y precio. El programa debe: cargarlo, responder consultas «dame la fila con este id» y calcular el precio medio por categoría. La máquina tiene 8 GB de RAM.

Solución razonada

Paso 1 — decidir qué domina. Dos operaciones: búsqueda por id y agregación por categoría. La búsqueda exige índice; la agregación exige recorrer todo una vez.

Paso 2 — descartar por memoria. list[dict] cuesta unos 300 B por fila: 1,5 GB sólo en datos, más el CSV en memoria durante la carga. Cabe, pero deja poco margen. list[tuple] baja a 940 MB.

Paso 3 — elegir la forma. dict[int, tuple] cuesta 236 B por fila (1,2 GB) y resuelve la búsqueda en O(1) sin estructura auxiliar. Pero duplica el id —una vez como clave y otra dentro de la tupla—, así que conviene guardar la tupla sin el id.

Paso 4 — agregar sin materializar. El precio medio por categoría se calcula en una sola pasada con un defaultdict que acumula suma y conteo, no con una lista de precios por categoría.

from collections import defaultdict
import csv
filas: dict[int, tuple[str, str, float]] = {}
acumulado: dict[str, list[float]] = defaultdict(lambda: [0.0, 0])
import os
import tempfile
ruta_csv = os.path.join(tempfile.gettempdir(), "datos.csv")
with open(ruta_csv, "w", newline="", encoding="utf-8") as salida:
salida.write("id,nombre,categoria,precio\n")
salida.write("1,uno,A,10.5\n2,dos,B,7.25\n3,tres,A,3.0\n")
with open(ruta_csv, newline="", encoding="utf-8") as f:
for r in csv.DictReader(f):
id_ = int(r["id"])
filas[id_] = (r["nombre"], r["categoria"], float(r["precio"]))
for nombre, categoria, precio in filas.values():
acc = acumulado[categoria]
acc[0] += precio
acc[1] += 1
medias = {c: total / n for c, (total, n) in acumulado.items()}

Paso 5 — comprobar. Mide con tracemalloc antes de dar la solución por buena, y compara contra list[dict]. Si la diferencia no importa en tu caso concreto, quédate con la versión legible: la medición también sirve para decidir no optimizar.

Comprobación con datos de ejemplo:

print("fila 2:", filas[2])
for categoria, media in sorted(medias.items()):
print(categoria, "->", media)
assert medias["A"] == 6.75, "(10.5 + 3.0) / 2"
os.remove(ruta_csv)
  1. El contenedor son punteros; el coste son los objetos.
  2. dict y set cuestan ~35 bytes por entrada: es el precio de O(1).
  3. dataclass(slots=True) iguala la densidad de una tupla sin perder nombres.
  4. La sobreasignación de list es del 12 %, y su pico transitorio es del 100 %.
  5. tracemalloc para decidir, getsizeof para diagnosticar.
  • Ramalho, L. Fluent Python, 2ª ed. Capítulos 2 y 5: secuencias y factores de datos.
  • Lott, S. F. Modern Python Cookbook, 3ª ed. Receta 4.1, «Choosing a data structure»: el criterio por contrato (collections.abc) que este capítulo complementa con mediciones.
  • Slatkin, B. Effective Python, 3ª ed. Ítems sobre listas, diccionarios y __slots__.
  • CPython 3.13: Objects/listobject.c (sobreasignación), Objects/dictobject.c (tabla combinada y claves compartidas), Include/cpython/object.h (cabecera PyObject).
  • Script de este capítulo: mediciones/02-11-coste.py.
  • 07 · Secuencias: el protocolo que comparten todas las estructuras de esta página.
  • 08 · dict por dentro: la tabla hash, el orden de inserción y las claves compartidas.
  • 05 · Memoria y rendimiento: medir con tracemalloc y cProfile sin engañarse.