Lección 04 — Soluciones: Estructuras de datos y algoritmos

La medición manda. Si tu número no coincide con estos, ejecuta con tamaños mayores y verás la forma de la curva.

Ejercicio 1 — Lista vs set

1-2. Resultados típicos: con lista ~2-4 s (1000 búsquedas × O(100.000) comparaciones = ~10⁸ operaciones); con set ~0.0002-0.0005 s. Aceleración: ×10.000. El mismo código semánticamente, dos mundos de coste.

Construir el set cuesta O(n) y O(n) de memoria extra. Si buscas 1 vez, la lista gana (no pagas la construcción). Punto de equilibrio aproximado: si vas a buscar más de 2-3 veces, el set ya amortiza. En APIs, la regla práctica: si la colección vive en un request y se consulta más de una vez, es un set.

Ejercicio 2 — Agrupar y contar

python

from collections import defaultdict, Counter

por_sector = defaultdict(list)
for a in asientos:
    por_sector[a["sector"]].append(a)
conteo_sector = {sector: len(seats) for sector, seats in por_sector.items()}

conteo_tipo = Counter(a["tipo"] for a in asientos)

Para "el hueco más pequeño por sector", min(por_sector["A"], key=lambda s: s["numero"]) es O(n) por sector y es la opción más legible. heapq brilla cuando necesitas el top-K repetidamente o sobre un flujo creciente; aquí solo pides un mínimo por grupo: el heap sería sobre-ingeniería (y su coste O(n log n) para construirlo es peor que un min O(n)). Criterio transversal de la lección: la estructura correcta es la que resuelve el problema al coste justo, no la más sofisticada.

Ejercicio 3 — Top-K de expiraciones

heapq.nsmallest(10, reservas, key=lambda r: r["expires_at"]) — O(n log k) con k=10.
sorted(...)\[:10] es O(n log n). Con n=10.000 y k=10, nsmallest gana (típicamente ×3-5) pero ambos tardan milisegundos. Merece el heap solo si n es enorme o se repite a cada segundo. Merece la pena saberlo y no necesitarlo a menudo.
La query con order_by("expires_at")[:10] mueve el coste a la BD: con el índice (status, expires_at) de la 00b es un index scan que devuelve 10 filas — nada de memoria del proceso, nada de 10.000 filas por la red. El coste vive en la BD (que ya lo pagó con el índice) en vez del proceso Python (que lo pagaría en RAM y GC). En backend, la respuesta con mejor Big-O es muchas veces "ninguna": deja que la BD te dé solo lo que necesitas.

Ejercicio 4 — El bloque contiguo

python

def mejor_bloque(numeros_libres: list[int], k: int) -> list[int] | None:
    """Primer bloque de k números consecutivos en un solo pase (O(n))."""
    inicio = 0
    for i, numero in enumerate(numeros_libres):
        if i > 0 and numero != numeros_libres[i - 1] + 1:
            inicio = i                      # se rompe la consecución: nueva ventana
        if numero - numeros_libres[inicio] == k - 1:
            return numeros_libres[inicio:inicio + k]
    return None

[20, 21, 22, 23] y None, respectivamente.
Con "mejor = más centrado": se recorren todos los bloques (mismo pase), se puntúa cada candidato por distancia al centro de la fila y se devuelve el de puntuación mínima. Sigue O(n) — los bloques contiguos se detectan en el mismo recorrido. La variante cambia el criterio de selección, no el patrón algorítmico.

Ejercicio 5 — La complejidad de tu API

Con la solución de la 00b (subconsulta/exclude con Q), la función ejecuta 1 query sea cual sea el número de eventos: el filtrado lo hace la BD en una SELECT.
Si contaste n queries (una por evento o una por asiento), el arreglo es prefetch_related("reservation_items__reservation") (por relación inversa) o la subconsulta. Medición típica: de ~500 queries y segundos, a 1 query y decenas de ms. Es exactamente la Lección 09 adelantada.
GROUP BY en SQL: la agregación ocurre junto a los datos y viaja por la red el resultado agregado (pocas filas). Agrupar en Python obliga a traer todas las filas (o a hacer varias queries). Para respuestas API: agrega en SQL, agrupa/transforma en Python solo cuando necesites la fila completa. Ancho de banda y memoria viajan en la dirección contraria a lo que pide la intuición del junior ("en Python controlo mejor").

Ejercicio 6 — Lectura crítica del serializer

DRF valida campo a campo (cada validate_<campo> una vez por objeto) y validate() global después. El coste por objeto es pequeño y lineal; el peligro no está ahí, sino en lo que tocas dentro de los validadores (¿accedes a la BD por cada objeto?).
to_representation por objeto + event.organizer.name sin select_related = 1 query extra por evento (O(n) queries, el N+1 de siempre). Con 200 eventos: 201 queries por request. La regla: en cualquier listado, el coste no está en serializar, está en qué tocas por objeto.
La regla que ya conoces de la 00b y la 03: "cada O(1) en memoria que acompaña a un acceso por objeto debe comprobarse contra la BD y la red" — un O(1) que dispara una query es un O(latencia) real.

Resumen del profesor

Elige la estructura al coste justo: set para pertenencia, defaultdict para agrupar, deque para colas, heap para top-K repetido.
En backend, el Big-O que duele es el que multiplica viajes a la BD, no el que multiplica ciclos de CPU.
"Un índice B-tree es tu heap persistente": delega el orden y el filtro en la BD cuando puedas.
Mide siempre (y en la Lección 37 lo sistematizamos). La intuición sobre rendimiento miente con elegancia.

Cuando entregues, cerramos la 04 y abrimos la Lección 05 — Linux y terminal: todo lo que acabas de medir, desde la consola donde viven los procesos.

Lección 04 — Estructuras de datos y algoritmos