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.
En una línea
Sección titulada «En una línea»Una lista es un array de punteros con sitio de sobra al final; todo lo demás se deduce de ahí.
Tres números, no uno
Sección titulada «Tres números, no uno»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:
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.
Las dos caras: append y insert
Sección titulada «Las dos caras: append y insert»| 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.
Cómo construir una lista
Sección titulada «Cómo construir una lista»| 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.
Copiar sin darse cuenta
Sección titulada «Copiar sin darse cuenta»Tres operaciones de lista copian y una no:
a = [3, 1, 2]b = a[:] # copiac = sorted(a) # copia (y ordena la copia)a.sort() # NO copia: ordena en su sitio, devuelve None
d = a[::-1] # copia invertidaa.reverse() # NO copia: invierte en su sitioLa 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.
La trampa
Sección titulada «La trampa»Cuándo NO usar list
Sección titulada «Cuándo NO usar list»- Como cola.
pop(0)es O(n); usadeque(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 listarecorre; unsetresponde en 30 ns (capítulo 06). - Como registro de campos fijos. Una tupla o una
dataclassconslotscomunica mejor y pesa menos (capítulo 03).
Ejercicio
Sección titulada «Ejercicio»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 gruposSolució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 gruposDe O(n × k) a O(n). Y si hace falta el formato de lista de pares, list(grupos.items()) al final.
Referencias
Sección titulada «Referencias»- 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.pyymediciones/02-11-coste.py.
Capítulos relacionados
Sección titulada «Capítulos relacionados»- 01 · Secuencias: el mapa donde encaja la lista.
- 03 ·
tuple: la versión sin reserva ni mutabilidad. - 06 ·
sety tablas hash: la estructura que resuelve el ejercicio en O(1).