Optimización y complejidad

Objetivos del módulo

Al completar este módulo serás capaz de:

  • Entender la notación Big-O y complejidad algorítmica
  • Usar herramientas de profiling para identificar cuellos de botella
  • Aplicar técnicas de optimización de código
  • Elegir las estructuras de datos más eficientes

¿Por qué optimizar?

Tu código funciona. Hace lo que tiene que hacer. ¡Genial! Pero… ¿es rápido? ¿Usa la memoria de forma eficiente? ¿Podría ser mejor?

Piensa en un coche. Un utilitario y un deportivo te llevan del punto A al punto B. Ambos “funcionan”. Pero si necesitas llegar rápido, o si la gasolina es cara, o si tienes que hacer el viaje mil veces al día… de repente el rendimiento importa.

En programación ocurre lo mismo:

  • Una app móvil que tarda 10 segundos en cargar pierde usuarios
  • Un servidor que procesa 100 peticiones por segundo en lugar de 10.000 necesita más máquinas (= más dinero)
  • Un script que tarda 8 horas en procesar datos te hace perder el tiempo
La regla de oro

“La optimización prematura es la raíz de todos los males” - Donald Knuth

Antes de optimizar, mide. Muchos programadores pierden horas optimizando código que no era el cuello de botella. Primero haz que funcione, luego mide dónde está el problema real, y solo entonces optimiza esa parte.

Complejidad algorítmica

Imagina que tienes que buscar a “García López, María” en una guía telefónica con un millón de nombres. ¿Cómo lo harías?

Opción A - Búsqueda lineal: Empezar por la primera página y pasar una por una hasta encontrarla. En el peor caso, revisarías el millón de nombres. Si la guía crece a 10 millones, tardarías 10 veces más.

Opción B - Búsqueda binaria: Abrir por la mitad. “Estoy en la M… García está antes”. Abrir la primera mitad por la mitad. “Estoy en la F… García está después”. Y así sucesivamente. Con cada paso eliminas la mitad de las opciones. Para un millón de nombres, necesitas unos 20 pasos. Para 10 millones, solo 24.

La complejidad algorítmica mide exactamente esto: cómo crece el tiempo (o memoria) cuando crece el tamaño del problema. Y la diferencia puede ser brutal.

Notación Big-O

La notación Big-O es la forma estándar de expresar la complejidad. Ignora las constantes y se centra en cómo escala el algoritmo:

Notación Nombre En español Ejemplo
O(1) Constante “Siempre igual de rápido” Acceso a lista por índice
O(log n) Logarítmica “Crece muy lentamente” Búsqueda binaria
O(n) Lineal “Crece proporcional” Recorrer una lista
O(n log n) Linealítmica “Un poco peor que lineal” Ordenar con mergesort
O(n²) Cuadrática “Se dispara rápido” Bucles anidados
O(2ⁿ) Exponencial “Explota” Fibonacci recursivo 
graph LR
    subgraph Crecimiento["Cómo crece el tiempo con n elementos"]
        A["O(1): ━━━"]
        B["O(log n): ━━━━"]
        C["O(n): ━━━━━━━━"]
        D["O(n²): ━━━━━━━━━━━━━━━━━━━━"]
    end
 1# O(1) - Constante
 2def acceso_directo(lista, indice):
 3    return lista[indice]
 4
 5# O(n) - Lineal
 6def buscar_lineal(lista, elemento):
 7    for item in lista:
 8        if item == elemento:
 9            return True
10    return False
11
12# O(n²) - Cuadrática
13def tiene_duplicados(lista):
14    for i in range(len(lista)):
15        for j in range(i + 1, len(lista)):
16            if lista[i] == lista[j]:
17                return True
18    return False

Comparación de complejidades

 1import time
 2
 3def medir(func, *args):
 4    inicio = time.perf_counter()
 5    resultado = func(*args)
 6    fin = time.perf_counter()
 7    return fin - inicio, resultado
 8
 9# Demostración: búsqueda lineal vs conjunto
10numeros = list(range(1000000))
11conjunto = set(numeros)
12buscar = 999999
13
14# O(n) - Lista
15tiempo_lista, _ = medir(lambda: buscar in numeros)
16print(f"Lista: {tiempo_lista:.6f}s")
17
18# O(1) - Conjunto
19tiempo_conjunto, _ = medir(lambda: buscar in conjunto)
20print(f"Conjunto: {tiempo_conjunto:.6f}s")

Profiling: El diagnóstico antes de la receta

Imagina que vas al médico porque te sientes cansado. Un mal médico te recetaría vitaminas sin más. Un buen médico primero te haría análisis de sangre, mediría tu tensión, preguntaría por tu sueño… Diagnostica antes de recetar.

Con el código es igual. Antes de optimizar, necesitas saber dónde está el problema. El 90% del tiempo de ejecución suele concentrarse en el 10% del código. Si optimizas la parte equivocada, pierdes el tiempo.

Python te da varias herramientas de “diagnóstico”:

timeit: El cronómetro de precisión

Para comparar alternativas y medir tiempos con exactitud:

 1import timeit
 2
 3# Medir tiempo de una expresión
 4tiempo = timeit.timeit('"-".join(str(n) for n in range(100))', number=10000)
 5print(f"Tiempo: {tiempo:.4f}s")
 6
 7# Comparar alternativas
 8setup = "texto = 'hola mundo' * 1000"
 9
10tiempo1 = timeit.timeit("len(texto)", setup=setup, number=100000)
11tiempo2 = timeit.timeit("texto.__len__()", setup=setup, number=100000)
12
13print(f"len(): {tiempo1:.4f}s")
14print(f"__len__(): {tiempo2:.4f}s")

cProfile: La radiografía de tu código

Cuando necesitas ver qué funciones consumen más tiempo:

 1import cProfile
 2import pstats
 3
 4def funcion_lenta():
 5    total = 0
 6    for i in range(10000):
 7        for j in range(100):
 8            total += i * j
 9    return total
10
11# Ejecutar con profiling
12profiler = cProfile.Profile()
13profiler.enable()
14resultado = funcion_lenta()
15profiler.disable()
16
17# Ver estadísticas
18stats = pstats.Stats(profiler)
19stats.sort_stats('cumulative')
20stats.print_stats(10)  # Top 10 funciones

memory_profiler: El medidor de consumo

A veces el problema no es el tiempo, sino la memoria. Tu programa puede ser rápido pero consumir gigabytes de RAM. Para detectar esto:

1from memory_profiler import profile
2
3@profile
4def funcion_memoria():
5    lista_grande = [i ** 2 for i in range(100000)]
6    return sum(lista_grande)
7
8resultado = funcion_memoria()

Técnicas de optimización

Una vez que has identificado el cuello de botella, aquí tienes las técnicas más efectivas para solucionarlo.

1. Elegir la herramienta correcta para cada trabajo

No usarías un destornillador como martillo, ¿verdad? Pues en programación, usar la estructura de datos incorrecta es exactamente eso.

 1# Malo: buscar en lista O(n)
 2usuarios = ["ana", "luis", "maria", "pedro"]
 3if "maria" in usuarios:  # Lento para listas grandes
 4    pass
 5
 6# Mejor: usar conjunto O(1)
 7usuarios_set = {"ana", "luis", "maria", "pedro"}
 8if "maria" in usuarios_set:  # Muy rápido
 9    pass
10
11# Malo: concatenar strings en bucle
12resultado = ""
13for i in range(1000):
14    resultado += str(i)  # Crea nuevo string cada vez
15
16# Mejor: usar join
17resultado = "".join(str(i) for i in range(1000))

2. No hagas el mismo trabajo dos veces

Si ya contaste cuántos invitados hay en la fiesta, ¿para qué volver a contarlos cada vez que alguien pregunta?

 1# Malo: calcular len() en cada iteración
 2lista = list(range(10000))
 3for i in range(len(lista)):  # len() se llama muchas veces
 4    pass
 5
 6# Mejor: calcular una vez
 7longitud = len(lista)
 8for i in range(longitud):
 9    pass
10
11# O mejor aún: iterar directamente
12for elemento in lista:
13    pass

3. Deja que los expertos hagan el trabajo pesado

Las funciones built-in de Python (sum, max, min, sorted, etc.) están implementadas en C y optimizadas por expertos. Usarlas es como contratar a un profesional en lugar de hacerlo tú mismo con las manos.

 1import time
 2
 3numeros = list(range(1000000))
 4
 5# Malo: implementación propia
 6inicio = time.perf_counter()
 7maximo = numeros[0]
 8for n in numeros:
 9    if n > maximo:
10        maximo = n
11print(f"Manual: {time.perf_counter() - inicio:.4f}s")
12
13# Mejor: función built-in (implementada en C)
14inicio = time.perf_counter()
15maximo = max(numeros)
16print(f"max(): {time.perf_counter() - inicio:.4f}s")

4. Comprensiones: la forma pythonica

Las comprensiones de lista no solo son más legibles, también son más rápidas porque Python las optimiza internamente.

 1import timeit
 2
 3# Bucle tradicional
 4def con_bucle():
 5    resultado = []
 6    for i in range(1000):
 7        resultado.append(i ** 2)
 8    return resultado
 9
10# Comprensión de lista
11def con_comprension():
12    return [i ** 2 for i in range(1000)]
13
14print(f"Bucle: {timeit.timeit(con_bucle, number=10000):.4f}s")
15print(f"Comprensión: {timeit.timeit(con_comprension, number=10000):.4f}s")

5. Recuerda lo que ya calculaste (memoización)

¿Recuerdas cuando en el colegio apuntabas las respuestas de ejercicios que ya habías resuelto? Eso es exactamente la memoización: guardar resultados para no recalcularlos.

 1from functools import lru_cache
 2
 3# Sin caché: O(2^n) - muy lento
 4def fib_lento(n):
 5    if n < 2:
 6        return n
 7    return fib_lento(n-1) + fib_lento(n-2)
 8
 9# Con caché: O(n) - muy rápido
10@lru_cache(maxsize=None)
11def fib_rapido(n):
12    if n < 2:
13        return n
14    return fib_rapido(n-1) + fib_rapido(n-2)
15
16import time
17
18inicio = time.perf_counter()
19print(fib_rapido(35))
20print(f"Con caché: {time.perf_counter() - inicio:.4f}s")

6. Generadores: produce bajo demanda

Como vimos en el capítulo de funciones, los generadores son perfectos cuando trabajas con datos grandes. En lugar de crear una lista gigante en memoria, producen valores uno a uno.

1import sys
2
3# Lista: ocupa memoria
4lista = [i ** 2 for i in range(1000000)]
5print(f"Lista: {sys.getsizeof(lista) / 1024 / 1024:.2f} MB")
6
7# Generador: memoria mínima
8gen = (i ** 2 for i in range(1000000))
9print(f"Generador: {sys.getsizeof(gen)} bytes")

Errores comunes al optimizar

Trampas a evitar

  1. Optimizar antes de medir: “Creo que esta función es lenta” no es suficiente. Usa profiling para confirmar dónde está realmente el problema.

  2. Optimizar lo que no importa: Si una función tarda 0.001 segundos y se llama una vez, optimizarla no tiene sentido aunque puedas hacerla 10 veces más rápida.

  3. Sacrificar legibilidad por micro-optimizaciones: Un código un 5% más rápido pero imposible de mantener es un mal negocio. La claridad casi siempre gana.

  4. Ignorar la complejidad algorítmica: Ninguna micro-optimización salvará un algoritmo O(n²) cuando n crece. Primero arregla el algoritmo, luego optimiza los detalles.

Guía rápida: ¿Qué optimizar?

Si tu problema es… La solución típica es…
Búsquedas lentas en listas grandes Usar set o dict en lugar de list
Concatenar strings en bucle Usar “".join()
Función costosa llamada muchas veces @lru_cache o memoización manual
Procesar archivos enormes Generadores y lectura por chunks
Bucles lentos con transformaciones Comprensiones de lista
Calcular lo mismo repetidamente Guardar el resultado en una variable
Código Python puro muy lento Considerar NumPy, Cython o PyPy
La regla del 80/20

El 80% de las mejoras de rendimiento vienen del 20% del código. Encuentra ese 20% con profiling antes de tocar nada.

Ejercicios prácticos

Ejercicio 1: Optimizar búsqueda de duplicados

Optimiza esta función que encuentra duplicados en una lista:

1def encontrar_duplicados(lista):
2    duplicados = []
3    for i in range(len(lista)):
4        for j in range(i + 1, len(lista)):
5            if lista[i] == lista[j] and lista[i] not in duplicados:
6                duplicados.append(lista[i])
7    return duplicados
 1def encontrar_duplicados_optimizado(lista):
 2    vistos = set()
 3    duplicados = set()
 4    for elemento in lista:
 5        if elemento in vistos:
 6            duplicados.add(elemento)
 7        else:
 8            vistos.add(elemento)
 9    return list(duplicados)
10
11# La versión original es O(n³), la optimizada es O(n)
Ejercicio 2: Comparar rendimiento

Mide y compara el rendimiento de estas dos formas de crear un diccionario:

  1. Usando un bucle for
  2. Usando comprensión de diccionario
 1import timeit
 2
 3def con_bucle():
 4    resultado = {}
 5    for i in range(1000):
 6        resultado[i] = i ** 2
 7    return resultado
 8
 9def con_comprension():
10    return {i: i ** 2 for i in range(1000)}
11
12tiempo_bucle = timeit.timeit(con_bucle, number=10000)
13tiempo_comprension = timeit.timeit(con_comprension, number=10000)
14
15print(f"Bucle: {tiempo_bucle:.4f}s")
16print(f"Comprensión: {tiempo_comprension:.4f}s")
17print(f"Diferencia: {abs(tiempo_bucle - tiempo_comprension) / tiempo_bucle * 100:.1f}%")

Quiz

🎮 Quiz: Optimización

0 / 0
Cargando preguntas...

Anterior: POO Siguiente: Paralelismo