The Professor
Índice Índice del curso

Módulo 1 · Fundamentos que sostienen todo

Lección 04 — Estructuras de datos y algoritmos

Complejidad y rendimiento con criterio: qué estructura aguanta el pico de venta y cuál se hunde.

Publicada
En esta lección
  1. Ejercicio 1 — La prueba de la lista vs el set
  2. Ejercicio 2 — Agrupar y contar (tu disponibilidad)
  3. Ejercicio 3 — Top-K de expiraciones
  4. Ejercicio 4 — El bloque contiguo (dos punteros)
  5. Ejercicio 5 — La complejidad oculta de tu API
  6. Ejercicio 6 — Análisis Big-O de tu serializer (lectura crítica)
  7. Entrega

Los ejercicios 1-4 se hacen en un script suelto (structures_lab.py); el 5-6, en tu TicketFlow. No mires solutions.md hasta entregar.

Preparación:

bash
cd ~/dev/ticketflow && source .venv/bin/activate

Ejercicio 1 — La prueba de la lista vs el set

  1. Construye una lista de 100.000 IDs y mide:
python
import time, random

ids = list(range(100_000))
objetivo = random.sample(ids, 1000)

t0 = time.perf_counter()
encontrados = [x for x in objetivo if x in ids]      # ¿O(?) por búsqueda
t1 = time.perf_counter()
print(f"lista: {t1 - t0:.4f}s")
  1. Repite con ids_set = set(ids). Anota ambos tiempos y la aceleración.
  2. ¿Cuándo NO compensa el set? (pista: construir el set es O(n); ¿cuántas búsquedas necesitas para amortizarlo?)

Ejercicio 2 — Agrupar y contar (tu disponibilidad)

Dada esta lista de asientos simulados:

python
asientos = [
    {"sector": "A", "fila": "1", "numero": n, "tipo": "VIP" if n < 5 else "GENERAL"}
    for n in range(1, 51)
] + [
    {"sector": "B", "fila": "1", "numero": n, "tipo": "GENERAL"}
    for n in range(1, 31)
]
  1. Agrupa por sector con defaultdict(list) y devuelve {sector: cantidad}.
  2. Cuenta por tipo con Counter.
  3. Calcula el asiento de menor número libre por sector... y luego ordena los sectores por "hueco más pequeño" (pista: heapq o min + sorted; ¿cuál es más limpio aquí y por qué?)

Ejercicio 3 — Top-K de expiraciones

  1. Genera 10.000 reservas con expires_at aleatorios. Con heapq, extrae las 10 que antes expiran en O(n log k).
  2. Compara con sorted(reservas, key=...)\[:10] y mide ambos. ¿Gana el heap? ¿Merece la diferencia la complejidad de lectura?
  3. Ahora escribe la query SQL/Django equivalente (Reservation.objects.filter(status=...).order_by("expires_at")\[:10]) y compara el enfoque: ¿dónde vive cada costo (memoria del proceso vs BD + red)?

Ejercicio 4 — El bloque contiguo (dos punteros)

Un usuario quiere 4 asientos juntos en la fila "A" del sector "B". Los asientos libres de la fila son: [3, 4, 5, 6, 12, 13, 20, 21, 22, 23, 24].

  1. Escribe una función mejor_bloque(numeros_libres: list[int], k: int) -> list[int] | None que devuelva el primer bloque de k consecutivos (o None). Debe ser O(n) — dos punteros o un solo pase; prohibido el doble bucle.
  2. Pruébala: mejor_bloque([3,4,5,6,12,13,20,21,22,23,24], 4) → [20,21,22,23] y mejor_bloque([3,4,20], 3) → None.
  3. ¿Qué cambia si "mejor" significa "el más centrado en la fila" y no "el primero"?

Ejercicio 5 — La complejidad oculta de tu API

Abre tu available_seats(event_id) (la escribiste en la 00b):

  1. Cuenta cuántas queries ejecuta con 3 eventos, 500 asientos cada uno. ¿Es 1, n o n²? (pista: from django.db import connection; print(len(connection.queries))).
  2. Si hiciera N+1, arréglalo con select_related/prefetch_related o con la subconsulta que ya viste en las soluciones de la 00b. Mide antes y después.
  3. La respuesta agrupa por sector (Ejercicio 2): ¿dónde sería más caro agrupar, en Python o en SQL (GROUP BY)? Justifica con el tamaño esperado de la respuesta y el ancho de banda.

Ejercicio 6 — Análisis Big-O de tu serializer (lectura crítica)

Coge cualquier serializer de DRF de tu proyecto (o escribe uno que valide 10 campos):

  1. ¿Cuántas veces se valida cada campo? ¿Qué coste tiene validate() global?
  2. DRF hace to_representation por objeto: si un listado serializa 200 eventos y cada uno accede a event.organizer.name sin select_related, ¿qué complejidad de queries tiene la respuesta completa?
  3. Escribe la regla que usarás desde hoy: "cada O(n) en memoria que acompaña a un acceso por objeto debe comprobarse contra ___".

Entrega

Pega resultados, mediciones y diffs en el chat. Con la corrección cerramos la 04 y pasamos a la Lección 05 — Linux y terminal: los procesos que acabas de multiplicar en Gunicorn, desde la consola que los opera.

^ arriba