Tercera batería: optimización. Aquí ejercitamos el Módulo 5 completo —medir primero (05-01), memoria (05-02) y paralelización (05-03)— usando el análisis del Módulo 2 como herramienta de diagnóstico. El material de trabajo es código de RutaBus lento pero realista: el tipo de código que de verdad aparece en producción, no ejemplos de laboratorio.

Cómo trabajar esta lección: antes de mirar cada solución, escribe tu propio diagnóstico siguiendo el método destilado al final del Módulo 5 — medir → algoritmo → código → memoria → paralelizar — y solo después compara. Si tienes Python a mano, mide de verdad con timeit versiones antes/después con datos sintéticos: comprobar que tu estimación de ganancia se cumple (o no) es la mitad del aprendizaje.

1. Leer un perfil: decidir dónde atacar primero.
2. El informe de puntualidad lento: la jerarquía completa aplicada.
3. Memoria: el job nocturno que se ahoga.
4. ¿Paralelizo o no?: clasificar CPU/I-O y aplicar Amdahl con números.
5. Cuándo NO optimizar.

Dificultad: básica

El proceso cierre_diario() de RutaBus tarda 21,5 segundos. Antes de tocar código, alguien hizo lo correcto (05-01): pasarle cProfile. Salida resumida:

Preguntas: (a) ¿qué función atacas primero y por qué?; (b) ¿es la que más veces se llama?; (c) 180 000 llamadas con percall casi nulo pero tottime enorme: ¿eso sugiere una optimización de nivel algoritmo o de nivel micro en la jerarquía de 05-01?; (d) si dejases buscar_tarifa en tiempo despreciable, ¿cuál sería el speedup máximo del cierre?

(a) buscar_tarifa: acumula 17,8 de los 21,5 segundos (el 83 %). La columna que manda es tottime (tiempo propio de la función), como vimos en 05-01. Optimizar cualquier otra cosa primero es trabajar sobre el 17 % restante.

(b) Trampa evitada: redondear_importe se llama las mismas 180 000 veces y solo acumula 0,9 s. El número de llamadas no es el criterio; el tiempo total sí.

(c) Nivel algoritmo. Cada llamada individual es barata (percall ≈ 0,0001 s) pero se hace 180 000 veces con coste que, a juzgar por el total, crece con los datos: el patrón típico es una búsqueda lineal repetida (una tarifa buscada con in/bucle sobre una lista por cada fichaje → O(n·m), como analizamos en 02-01). La solución de nivel algoritmo es cambiar la estructura: un dict de tarifas convierte cada búsqueda en O(1). Micro-optimizar el interior de buscar_tarifa (nivel micro) dejaría intacto el O(n·m).

(d) Tiempo restante ≈ 21,5 − 17,8 = 3,7 s → speedup máximo ≈ 21,5 / 3,7 ≈ ×5,8. Es la misma aritmética de la ley de Amdahl (05-03) aplicada a optimización secuencial: la parte que no tocas acota la ganancia total.

Error típico: abrir el código y "optimizar lo que parece lento" sin perfil. El perfil aquí desmiente dos intuiciones razonables: ni la ordenación (2,1 s, ¡a la vista y con nombre sospechoso!) ni la función más llamada eran el problema.

Dificultad: media

Este informe tarda minutos con los volúmenes actuales (n ≈ 200 000 llegadas, m ≈ 500 paradas críticas, y ~30 % de las llegadas ocurren en paradas críticas):

Tareas: (a) deriva la complejidad actual con el análisis de 02-01, identificando el coste de (1), (2) y (3); (b) aplica la jerarquía de 05-01: qué cambias, en qué orden y en qué nivel está cada cambio; (c) reescribe la función; (d) estima la ganancia con los números dados.

Pista: uno de los tres problemas es órdenes de magnitud peor que los otros dos. Encuéntralo primero: es el que decide por dónde empezar.

(a) Diagnóstico.

• (1) parada in paradas_criticas sobre lista: O(m) por iteración → O(n·m) total = 200 000 × 500 = 10⁸ comparaciones.
• (2) max(...) recorre las n llegadas dentro del bucle, y es invariante: calcula lo mismo en cada pasada. Se ejecuta en cada acierto (~0,3·n = 60 000 veces) × O(n) → 1,2 × 10¹⁰ operaciones. Este es el monstruo.
• (3) Concatenación de cadenas: cada += copia el informe entero (02-01). Con k ≈ 60 000 líneas, coste Θ(k²) en caracteres copiados: ~10⁹–10¹⁰ según longitud de línea.

(b) Plan según la jerarquía (05-01: primero lo que más rinde):

1. Algoritmo — sacar el invariante: peor se calcula una vez, fuera del bucle. Elimina el término 10¹⁰.
2. Algoritmo/estructura — lista → set: set(paradas_criticas) una vez (O(m)) y cada consulta pasa a O(1). Elimina el 10⁸.
3. Código — acumular y join: construir una lista de líneas y unirlas al final, Θ(longitud total) en vez de Θ(k²).

(c) Reescritura:

(d) Ganancia. Antes: dominado por (2), ~10¹⁰ operaciones elementales — decenas de segundos o minutos en CPython. Después: Θ(n + m) ≈ 4 × 10⁵ operaciones — decenas de milisegundos. Ganancia estimada: 3–4 órdenes de magnitud. Y el paso final obligatorio del método: confirmarlo midiendo con timeit sobre datos sintéticos del mismo tamaño (05-01) — las estimaciones se comprueban, no se declaran.

Errores típicos: (1) empezar por el join porque "la concatenación de strings es lo famoso" — aquí era el tercer problema en magnitud; la jerarquía existe para ordenar los ataques; (2) no reconocer (2) como invariante porque "está dentro de un if"; (3) convertir a set dentro del bucle (if parada in set(paradas_criticas)), que vuelve a ser O(m) por iteración con coste extra de construcción — peor que la lista original.

Dificultad: media

Este job procesa el fichero de fichajes del día (varios GB) y muere con MemoryError en el servidor de 8 GB:

Preguntas: (a) ¿cuántas estructuras proporcionales al fichero conviven en memoria en el peor momento?; (b) reescríbelo para que la memoria auxiliar sea O(k) con k = 10, usando lo visto en 05-02 y el top-k de 04-04; (c) ¿con qué herramienta confirmarías la mejora?; (d) ¿en qué situación no bastaría con generadores y habría que procesar por lotes?

(a) En el momento del sorted conviven: lineas (todas las cadenas), fichajes (todos los objetos), validos (referencias a casi todos ellos) y la lista nueva que sorted construye. Entre 3 y 4 estructuras O(n) simultáneas — con un fichero de varios GB, el MemoryError está garantizado. Nota de 02-02: validos guarda referencias, no copias de los objetos, pero lineas y fichajes sí son contenido nuevo cada una.

(b) El fichero puede recorrerse perezosamente (un fichero abierto ya es un iterador línea a línea) y el top-10 no necesita ordenar nada: es un problema de k mayores, y para k pequeño en streaming la herramienta es un heap (04-05 nos dio heapq; 04-04 nos dio la alternativa quickselect, que aquí no sirve porque exige tener la lista entera en memoria):

Memoria auxiliar: O(k) — el generador produce los fichajes de uno en uno (05-02) y nlargest solo retiene los 10 mejores vistos. Tiempo: Θ(n log k) frente al Θ(n log n) de ordenar todo; con k = 10, en la práctica lineal.

(c) tracemalloc (05-02): medir el pico de memoria de ambas versiones con un fichero de prueba. La versión original pica en gigabytes; la nueva, en kilobytes. (Para el tiempo, timeit; para saber dónde se gasta, cProfile — cada herramienta responde una pregunta distinta.)

(d) Cuando el cálculo necesita agrupar un estado que también crece sin límite — por ejemplo, "importe total por billete único" con cientos de millones de billetes distintos: el dict acumulador acabaría siendo el nuevo problema. Ahí entran los lotes de 05-02: procesar por tramos (por hora, por línea), volcar resultados parciales y combinar después — que es exactamente la ordenación externa que esbozamos en 04-03.

Errores típicos: (1) "arreglarlo" cambiando readlines() por list(f) — la misma materialización con otra sintaxis; (2) construir el generador y luego hacerle sorted(validos, ...): sorted materializa el iterable completo y la mejora se evapora en silencio; (3) convertir el generador en lista "un momento, para depurar" y olvidarlo ahí.

Dificultad: alta

Dos jobs de RutaBus son candidatos a paralelización:

• Job A: consulta la API municipal de tráfico para 60 zonas; cada llamada tarda ~0,5 s, casi todo espera de red, y las respuestas se procesan en microsegundos.
• Job B: recalcula Dijkstra desde cada una de las 300 paradas de la red (CPU pura; los orígenes son independientes entre sí). Medido: el 90 % del tiempo son los Dijkstra; el 10 % restante (cargar el grafo y volcar resultados) es secuencial.

Preguntas: (a) clasifica cada job (CPU-bound / I-O-bound) y elige hilos o procesos, justificando con el GIL (05-03); (b) ¿qué executor de concurrent.futures usarías en cada caso?; (c) para el Job B, calcula con la ley de Amdahl el speedup con 4 y con 8 procesos, y el límite teórico con infinitos; (d) la máquina tiene 8 núcleos: ¿merece la pena configurar 16 procesos?

(a) Job A: I/O-bound — el tiempo se va esperando la red, no computando. Durante una espera de E/S el hilo libera el GIL, así que los hilos funcionan perfectamente (y son más baratos que procesos). Job B: CPU-bound — el GIL impide que dos hilos ejecuten bytecode Python a la vez, así que hilos no aportarían nada; hacen falta procesos, cada uno con su intérprete y su GIL. Y es el caso ideal: como vimos en 05-03, Dijkstra por origen es vergonzosamente paralelo — cero dependencias ni comunicación entre tareas.

(b) Job A → ThreadPoolExecutor (p. ej. max_workers=20; al ser espera de red, más workers que núcleos es razonable). Job B → ProcessPoolExecutor con max_workers ≈ número de núcleos:

(c) Amdahl (05-03) con fracción paralelizable p = 0,9: S(N) = 1 / ((1 − p) + p/N).

Con 8 procesos no obtienes ×8: obtienes ×4,7, porque el 10 % secuencial no se acelera y pesa cada vez más en proporción.

(d) No. Dos razones que se suman: (i) Amdahl da S(16) = 1/(0,1 + 0,05625) ≈ ×6,4 teórico — pasar de 8 a 16 procesos añadiría como mucho un ×1,36 más; (ii) ese teórico ni siquiera se alcanza: con 8 núcleos físicos, 16 procesos CPU-bound compiten por los mismos núcleos y añaden sobrecoste de cambios de contexto y memoria (cada proceso duplica el grafo). Más workers que núcleos solo tiene sentido cuando hay espera (Job A), no cuando hay cómputo.

Error típico: paralelizar como primer recurso. La jerarquía del Módulo 5 pone paralelizar al final por algo: si dentro de dijkstra_desde hubiera una lista donde toca un heap, arreglar eso daría más que los 8 núcleos juntos — y las dos mejoras se multiplican si haces primero la barata.

Dificultad: media

Dos situaciones reales en el equipo de RutaBus:

• Caso 1: informe_mensual.py se ejecuta una vez al mes, tarda 4 segundos y son 80 líneas legibles. Un compañero propone dedicar 2 días a reescribirlo con multiprocessing, lru_cache y __slots__ para dejarlo en 0,5 s.
• Caso 2: el endpoint buscar_conexion de la app responde en 900 ms y recibe 50 000 peticiones al día. Los usuarios se quejan de lentitud. Nadie lo ha perfilado.

Preguntas: (a) ¿cuál de los dos merece esfuerzo de optimización? Cuantifica; (b) ¿qué harías primero en el caso que sí lo merece?; (c) ¿qué riesgos concretos tiene optimizar el Caso 1?

(a) El Caso 2, sin discusión. Cuantifiquemos ambos:

• Caso 1: ahorro de 3,5 s/mes = 42 segundos al año, a cambio de 2 días de ingeniería. Aunque el sueldo fuera gratis, no recuperas la inversión ni en un siglo.
• Caso 2: 50 000 × 0,9 s = 45 000 s = 12,5 horas diarias de espera agregada de usuarios, en el camino crítico de la experiencia de la app. Cada 100 ms que rasques son ~1,4 horas diarias devueltas a los usuarios.

(b) Medirlo (05-01): cProfile sobre el endpoint con peticiones representativas, antes de tocar una línea. "Nadie lo ha perfilado" significa que nadie sabe si los 900 ms son la consulta de rutas (¿un Dijkstra sobre una representación torpe del grafo? ¿una búsqueda lineal de paradas?), la base de datos o la serialización. Optimizar sin perfil es apostar; con 12,5 horas/día en juego, se apuesta poco y se mide mucho. Después, la jerarquía: algoritmo → código → memoria → paralelizar.

(c) Riesgos del Caso 1: (i) bugs nuevos en un proceso que funcionaba — todo cambio tiene probabilidad de error, y aquí sin beneficio que lo compense; (ii) mantenibilidad: 80 líneas legibles se convierten en multiprocessing con estado compartido, que el siguiente compañero tardará horas en entender (y recordemos de 05-03 que compartir estado entre procesos exige Lock y serialización: complejidad real); (iii) coste de oportunidad: esos 2 días no se dedican al Caso 2, que sí sangra. La regla del Módulo 5 era exactamente esta: el código optimizado se paga en legibilidad y riesgo, así que se optimiza lo que está en el camino crítico y se deja en paz lo que no.

Matiz final para no convertir la regla en dogma: si el informe mensual pasara a ejecutarse cada 5 minutos, o su fichero de entrada se multiplicara por 100, el análisis cambia — las decisiones de optimización caducan con los datos, por eso se apoyan en números medidos y no en opiniones.

Error típico: optimizar por satisfacción técnica ("sé hacerlo más rápido") en lugar de por impacto. La pregunta profesional no es "¿puede ir más rápido?" — casi todo puede — sino "¿cuánto vale que vaya más rápido y cuánto cuesta conseguirlo?".

Has aplicado el método completo del Módulo 5 sobre código ajeno y realista: leer un perfil y elegir el objetivo por tottime y no por intuición; atacar un informe lento en el orden correcto (invariante fuera del bucle, lista → set, join) estimando ganancias de órdenes de magnitud; convertir un job glotón de memoria en un flujo O(k) con generadores y heap; decidir hilos o procesos con el GIL y poner números al speedup con Amdahl; y —la habilidad más rentable de todas— reconocer cuándo la mejor optimización es no optimizar.

Ya tienes los tres músculos entrenados por separado: análisis (06-01), diseño (06-02) y optimización (06-03). En la última lección del curso los usaremos todos a la vez: tres proyectos finales que construyen, de principio a fin, piezas completas de RutaBus.