Lección 04 — Estructuras de datos y algoritmos

Stack: Django + DRF · Proyecto: TicketFlow Estado: Publicada — impartición tras corregir la 03 Prerrequisito: Lección 03 — Concurrencia

Objetivos

Al terminar esta lección podrás:

1. Analizar el coste de un algoritmo con Big-O y, más importante, saber cuándo el Big-O no importa.
2. Elegir la estructura de datos correcta para cada problema del dominio (carrito, disponibilidad, mapa de asientos).
3. Reconocer los costes ocultos de las colecciones de Python (listas, sets, dicts, defaultdict, Counter).
4. Traducir estructuras de memoria a índices de base de datos — y entender por qué la Lección 09 es la continuación natural de esta.

1. Big-O sin pánico (y sin fanatismo)

Big-O describe cómo crece el coste cuando crece la entrada. Los órdenes que usarás:

Dos verdades incómodas que los juniors no saben:

1. El Big-O no dice el tiempo real. Un O(n) con n=50 puede ser más rápido que un O(1) que hace una query a la BD. La constante importa hasta que n es grande; y en backend, "grande" suele ser n>10.000.
2. Tu cuello de botella casi nunca está en el algoritmo: está en la I/O. Un O(n²) en memoria con n=1000 son milisegundos; un O(n) que hace 1000 queries a la BD son segundos. El O(N+1) (Lección 09) es el asesino número uno de APIs, y su nombre completo es "n+1 idas por red".

Clave: primero mide (Lección 37), luego optimiza el algoritmo correcto. Pero elige la estructura correcta desde el día uno, porque esa decisión no se ve en el perfiler: se ve en la legibilidad del código.

2. Las estructuras de Python que usarás cada semana

Costes que sorprenden a todos:

• x in lista es O(n); x in set es O(1) medio. El bug de rendimiento más común del backend junior es buscar en listas dentro de bucles.
• Concatenar strings con += en un bucle es O(n²) en el peor caso; ''.join(pieces) es O(n).
• list.pop(0) es O(n); deque.popleft() es O(1). La cola que crece es una deque, no una lista.
• Copiar listas grandes dentro de bucles es un asesino silencioso de memoria.

3. Elegir estructura: los problemas reales de TicketFlow

Problema A — "¿Este conjunto de asientos está libre?" (carrito de la compra)

El usuario selecciona [A-12, B-3, C-9] y quieres saber si TODOS están libres antes de reservar.

# O(k · n): para cada asiento elegido (k), buscar en la lista de libres (n)
for seat in requested_seats:
    if seat not in available_list:   # O(n) por iteración → O(k·n)
        return conflict(seat)

# O(k): convierte los libres en un set una vez, pregunta k veces en O(1)
available_set = set(available_seats)          # O(n)
missing = [s for s in requested_seats if s not in available_set]  # O(k)
if missing:
    return conflict(missing)

Con n=20.000 asientos y k=6, la diferencia no se nota en tu portátil. Se nota el día del concierto, con 200 peticiones por segundo, donde son ciclos de CPU que se multiplican por latencia de cola del worker.

Problema B — "Agrupar asientos por sector" (respuesta de disponibilidad)

# Menos eficiente: recorrer asientos y sectores (anidado)
# Eficiente: un solo pase con defaultdict
from collections import defaultdict

by_sector = defaultdict(list)
for seat in seats:                    # O(n)
    by_sector[seat.sector].append(seat)   # O(1) por asiento

Problema C — "Las 10 reservas que antes expiran" (job de expiración)

Para un top-K de mínimos, un heap (o simplemente ORDER BY expires_at LIMIT 10 en SQL — con el índice (status, expires_at) que ya creaste en la 00b). La estructura "correcta" en backend muchas veces es un índice bien elegido: el B-tree es tu heap persistente, ordenado, transaccional y compartido entre procesos. Por eso el orden de prioridad del backend senior es:

1. Deja que la BD ordene/filtre (índices, LIMIT).
2. Si hay que procesar en memoria, elige la estructura con el coste correcto.
3. Mide. El resto es superstición.

4. Complejidad que se esconde en el código "normal"

Peces gordos que verás en revisiones:

# 1. N+1: O(n) queries — el clásico (Lección 09 lo mata con select_related)
for reservation in reservations:
    print(reservation.user.email)     # 1 query por reserva

# 2. Doble bucle donde basta un dict: O(n²) → O(n)
for a in asientos:
    for r in reservas:
        if r.seat_id == a.id: ...

asientos_por_id = {a.id: a for a in asientos}   # O(n) una vez
for r in reservas:
    a = asientos_por_id.get(r.seat_id)          # O(1) por búsqueda

# 3. "¿Está en la lista?" dentro de bucle: O(n·m)
if user.id in lista_de_ids_vip:  # lista → set()

# 4. Construir strings en bucle: O(n²)
html = ""
for fila in filas:
    html += f"<tr>{fila}</tr>"    # usa list + "".join()

Y la regla que une todo: cada uno de estos errores es invisible con datos de desarrollo y explosivo con datos de producción. No porque el algoritmo cambie; porque n cambia.

5. Algoritmos concretos que sí conocerás de memoria

• Búsqueda binaria: sobre listas ordenadas, O(log n). La usa el índice B-tree de PostgreSQL cada vez que filtras. Entenderla es entender EXPLAIN (Lección 09).
• Merge / sort estable: Django order_by y los rankings; saber que ordenar es O(n log n) y que ordenar dos veces (por dos campos) puede hacerse en una sola llamada con tuplas.
• BFS/DFS (recorrido de grafos): aparece al calcular "sectores contiguos disponibles" o relaciones de dependencia. No los implementarás a diario, pero reconocer el patrón de "grafo de dependencias" te salvará en el Módulo 12 (resiliencia: dependencias entre servicios).
• Ventana deslizante / dos punteros: para "mejor bloque contiguo de asientos" (el usuario quiere 4 juntos): punteros sobre la fila ordenada de asientos, O(n) en vez de O(n²).

Autoevaluación (respóndeme en el chat)

1. Un endpoint tarda 800 ms: el algoritmo es O(n) sobre 500 elementos. ¿Qué harías primero y por qué el Big-O no está (aún) en el camino?
2. ¿Por qué seat in lista_libres dentro de un bucle es el bug más común? Reescríbelo y nombra el coste antes y después.
3. ¿Qué estructura usarías para el "top 10 de eventos por ventas de las últimas 2 horas" en memoria? ¿Y si la fuente es SQL? ¿Por qué cambia la respuesta?
4. El "mejor bloque contiguo de 4 asientos en una fila" — ¿qué patrón algorítmico aplicas y cuál sería su coste?
5. ¿Por qué decimos que "un índice B-tree es un heap persistente y compartido"? ¿Qué gana y qué pierde frente a un heapq en memoria del proceso?

Continúa con los ejercicios. Las soluciones solo tras intentarlo.