Ordenar sin ordenar de más
Ordenar parece resuelto: llamas a sorted() y ya. Pero hay tres decisiones dentro de esa llamada —qué algoritmo, qué clave, y si hace falta ordenar— y las tres mueven el tiempo en órdenes de magnitud. La primera no la eliges: Python usa Timsort. Las otras dos sí.
En una línea
Sección titulada «En una línea»Timsort es O(n) si los datos ya están casi ordenados y O(n log n) si no; tú decides cuál de los dos casos le das.
El algoritmo que aprovecha lo que hay
Sección titulada «El algoritmo que aprovecha lo que hay»Veintitrés veces. Timsort detecta secuencias ya ordenadas (runs) y las fusiona; con datos aleatorios no hay nada que detectar y hace el trabajo completo.
Eso tiene una consecuencia práctica que casi nunca se aprovecha: si los datos llegan casi ordenados, ordenarlos es barato. Un informe que se reordena por una columna distinta cada vez parte de un orden parcial; uno que se genera desordenado paga el precio completo.
La segunda consecuencia: ordenar dos veces por criterios distintos es más barato que ordenar una vez por una clave compuesta mal construida. Y ordenar para quedarse con los diez mayores es tirar el trabajo:
sorted(datos)[-10:] # ordena todo para 10heapq.nlargest(10, datos) # O(n log 10)La clave decide el coste
Sección titulada «La clave decide el coste»| Forma | Tiempo | Frente a reverse |
|---|---|---|
sorted(v, reverse=True) |
26.8 ms | 1.00× |
sorted(v) |
27.8 ms | 1.04× |
sorted(v, key=lambda x: -x) |
52.0 ms | 1.94× |
python mediciones/02-05-07-dict-set-orden.py
Invertir el orden con reverse=True es gratis. Hacerlo negando la clave dentro de una función Python cuesta el doble: la lambda se ejecuta una vez por elemento y el intérprete paga la llamada.
Y dentro de las claves, no todas cuestan lo mismo:
| Clave | Tiempo |
|---|---|
key=operator.itemgetter(0) |
42.1 ms |
key=lambda p: p[0] |
47.6 ms |
python mediciones/02-05-07-dict-set-orden.py
Un 13 % por cambiar una lambda por una función de C. No es una optimización para perseguir, pero sí para conocer: cuando el perfil señale el sorted, ahí está.
Estabilidad: el orden de los empates
Sección titulada «Estabilidad: el orden de los empates»sorted() es estable: dos elementos con la misma clave conservan su orden relativo.
filas = [("ana", 3), ("luis", 1), ("eva", 3)]sorted(filas, key=lambda f: f[1])# [('luis', 1), ('ana', 3), ('eva', 3)] ← ana antes que eva, como estabanEso permite ordenar por criterios múltiples sin clave compuesta: ordenas por el secundario y después por el principal, y lo segundo no deshace lo primero.
datos.sort(key=lambda f: f.nombre) # secundariodatos.sort(key=lambda f: f.grupo) # principal, estableLa alternativa de una sola pasada con tupla funciona si todos los criterios van en la misma dirección:
datos.sort(key=lambda f: (f.grupo, f.nombre))Si uno va descendente y otro ascendente, la clave compuesta necesita negar los números o invertir cadenas, lo que es frágil. Ahí las dos pasadas estables son más claras y casi igual de rápidas.
La trampa
Sección titulada «La trampa»Cuándo NO ordenar
Sección titulada «Cuándo NO ordenar»- Si sólo necesitas el máximo o el mínimo,
max()ymin()son O(n) y no copian. - Si necesitas los k mayores,
heapq.nlargest(k, datos). - Si los datos ya están ordenados y sólo añades elementos,
bisect.insortencuentra el hueco en O(log n) y desplaza los punteros en O(n) (capítulo 08). - Si el orden es sólo para agrupar, un
dicto undefaultdictagrupa en O(n) sin ordenar.
Ejercicio
Sección titulada «Ejercicio»Ordena una lista de empleados por departamento ascendente y, dentro de cada departamento, por salario descendente, sin construir una clave compuesta con números negados. Explica por qué tu solución es estable.
Solución
from types import SimpleNamespace
empleados = [ SimpleNamespace(nombre="ana", departamento="datos", salario=3000), SimpleNamespace(nombre="luis", departamento="datos", salario=3500), SimpleNamespace(nombre="eva", departamento="web", salario=2800),]
empleados.sort(key=lambda e: e.salario, reverse=True) # secundario: descendenteempleados.sort(key=lambda e: e.departamento) # principal: ascendenteLa primera pasada ordena por salario de mayor a menor. La segunda ordena por departamento; como sort es estable, dentro de cada departamento se conserva el orden que dejó la primera pasada, es decir, salario descendente.
Ese es el truco que hace innecesaria la clave compuesta: ordenar del criterio menos importante al más importante, aprovechando que cada orden respeta el anterior. Funciona con direcciones mezcladas, que es justo donde key=(a, -b) se vuelve ilegible o imposible (no puedes negar una cadena).
Coste: dos pasadas O(n log n) en lugar de una. En la práctica, la segunda pasada parte de datos casi ordenados por departamento y Timsort la resuelve cerca de O(n).
Referencias
Sección titulada «Referencias»- Ramalho, L. Fluent Python, 2ª ed. Capítulo 2:
list.sortysorted. - CPython 3.13:
Objects/listobject.c(list_sort),Objects/listsort.txtpara Timsort. - Mediciones:
mediciones/02-05-07-dict-set-orden.py.
Capítulos relacionados
Sección titulada «Capítulos relacionados»- 08 ·
heapqybisect: ordenar sólo lo necesario. - 02 ·
listpor dentro: por quésortno puede ser O(1) en memoria extra. - 10 ·
collections:Counter.most_common, que ordena por frecuencia sin que lo escribas.