Complejidad y rendimiento: por qué dos scripts iguales en apariencia tardan distinto
Una demostración con diez elementos tiene una virtud extraordinaria: permite que casi cualquier algoritmo parezca una decisión excelente. El programa devuelve lo esperado, la ejecución termina enseguida y alguien da por resuelto el rendimiento. Después llegan cincuenta mil registros y descubrimos que, para encontrar cada código, estamos volviendo a leer el catálogo entero. La máquina no se ha vuelto perezosa. Está obedeciendo con una paciencia que yo no pienso imitar.
Vamos a comparar dos maneras de consultar un catálogo de códigos de espacios: recorrer una lista o buscar en un diccionario. Los resultados deberán coincidir, incluidos los códigos desconocidos y las consultas repetidas. Mediremos por separado la construcción del índice y su reutilización, con programas completos en Python y C#. El objetivo es entender cómo crece el trabajo y aprender a medirlo; no proclamar un ganador universal a partir del cronómetro de un portátil.
Antes de cronometrar, decide qué resultado debes conservar
Nuestro catálogo contendrá parejas de código y descripción. Una consulta devolverá la descripción correspondiente o un valor nulo si el código no existe. Mantendremos el orden de las consultas y sus repeticiones: preguntar dos veces por el mismo código producirá dos posiciones en la respuesta. Una descripción vacía seguirá siendo una descripción existente. Convertirla en «desconocido» sería cambiar el comportamiento mientras presumimos de haberlo optimizado.
Trabajaremos con textos y una comparación exacta, sensible a mayúsculas. P01, p01 y P01 serán claves diferentes. No estamos decidiendo cómo debería normalizarse un catálogo real; estamos fijando la misma regla para las dos versiones. Si el proyecto necesita equivalencias, habrá que definirlas antes y comprobar cómo afectan a los duplicados. La explicación de diccionarios y mapas desarrolla esa relación entre identidad y clave.
Cada código del catálogo deberá ser único. La función que construye el índice rechazará un duplicado, incluso si sus dos descripciones coinciden. Antes de comparar las búsquedas construiremos ese índice una vez para validar el catálogo. La búsqueda secuencial recibirá el mismo catálogo ya comprobado. Así no enfrentaremos una versión que devuelve la primera coincidencia con otra que conserva la última: esa competición sería rápida de montar y bastante inútil de interpretar.
El ejemplo opera sobre colecciones en memoria que ya cumplen esos tipos. No descarga datos, interpreta CSV ni consulta una API. Esta separación permite estudiar la búsqueda sin mezclarla con otras tareas. En una aplicación tendrás que conservar también las validaciones de entrada, la relación entre modelo e identificador y el tratamiento de errores. Una mejora que pierde esas garantías merece otro nombre; yo sugiero «regresión con buena presentación».
Contar el trabajo explica lo que el cronómetro solo observa
Llamemos n al número de consultas y m al número de entradas del catálogo. Si buscamos una clave recorriendo la lista, podemos encontrarla al principio, al final o no encontrarla. En este último caso tendremos que comparar las m entradas. Si todas las consultas fallan, realizaremos exactamente n × m comparaciones de códigos. El programa no sabe que no va a encontrar nada hasta terminar cada recorrido.
Cuando ambas colecciones tienen diez elementos, ese caso necesita cien comparaciones; con cien elementos en cada una serán diez mil, y con mil serán un millón. Estas cifras salen de contar operaciones del algoritmo, no de una prueba de velocidad. Si solo crece una colección, el crecimiento será distinto: duplicar las consultas con un catálogo fijo duplica ese trabajo; duplicar las dos colecciones lo multiplica por cuatro. Decir «hay dos bucles, luego es cuadrático» sin nombrar los tamaños es una forma muy solemne de saltarse la explicación.
La notación O(n × m) describe aquí cómo crece el coste en el peor caso de la búsqueda secuencial. Si identificamos ambos tamaños con uno solo, n = m, podemos escribir O(n²). No significa que el programa tarde una cantidad concreta de segundos, ni que cada entrada cueste lo mismo en cualquier máquina. Las comparaciones entre textos largos, las asignaciones de memoria y la forma de los datos también tienen coste.
Un índice basado en una tabla hash cambia la organización: primero asociamos cada código a su descripción y después consultamos por clave. Bajo las condiciones habituales de un buen reparto de hashes y claves de longitud acotada, construirlo y resolver el lote tiene un coste esperado cercano a O(m + n). Si el índice ya existe, el lote de consultas queda cerca de O(n). Son estimaciones de crecimiento, no garantías de tiempo constante absoluto. Microsoft explica la recuperación cercana a O(1) y su dependencia del hash en la documentación de Dictionary.
El índice ocupa memoria adicional, aproximadamente proporcional al catálogo, mientras que las dos soluciones crean una respuesta proporcional al número de consultas. Si solo vas a hacer una búsqueda en una lista corta, construir otra estructura puede no compensar. Si vas a consultar miles de veces el mismo catálogo, repetir el recorrido merece una justificación mejor que «siempre se ha hecho así». No hace falta inventar una arquitectura nueva: a veces basta con dejar de empezar desde el principio.
Ejecutar una comparación que incluya el coste del índice
Guarda el siguiente programa como medir_busquedas.py. Funciona con Python 3.10 o posterior y su biblioteca estándar. Primero comprueba un caso pequeño con resultado conocido. Después usa catálogos de 10, 100 y 1.000 entradas y el mismo número de consultas. Todas las consultas del experimento grande serán desconocidas: elegimos deliberadamente el caso que obliga a agotar cada recorrido. No representa la mezcla de aciertos de todos los proyectos.
import timeit
def crear_indice(catalogo):
indice = {}
for codigo, descripcion in catalogo:
if codigo in indice:
raise ValueError("codigo duplicado")
indice[codigo] = descripcion
return indice
def buscar_lista(catalogo, consultas):
resultado = []
for codigo in consultas:
descripcion = None
for clave, valor in catalogo:
if clave == codigo:
descripcion = valor
break
resultado.append(descripcion)
return resultado
def buscar_indice(indice, consultas):
return [indice.get(codigo) for codigo in consultas]
def buscar_desde_cero(catalogo, consultas):
return buscar_indice(crear_indice(catalogo), consultas)
def medir_ms(accion):
accion()
muestras = timeit.repeat(accion, repeat=5, number=3)
return min(muestras) * 1000 / 3
catalogo = [("P01", "Aula"), ("P02", "")]
consultas = ["P02", "X", "P01", "P01"]
indice = crear_indice(catalogo)
esperado = ["", None, "Aula", "Aula"]
assert buscar_lista(catalogo, consultas) == esperado
assert buscar_indice(indice, consultas) == esperado
assert buscar_desde_cero(catalogo, consultas) == esperado
for tamano in (10, 100, 1000):
catalogo = [(f"P{i:04}", f"Uso {i}") for i in range(tamano)]
consultas = [f"X{i:04}" for i in range(tamano)]
indice = crear_indice(catalogo)
esperado = [None] * tamano
assert buscar_lista(catalogo, consultas) == esperado
assert buscar_indice(indice, consultas) == esperado
assert buscar_desde_cero(catalogo, consultas) == esperado
acciones = {
"lista": lambda: buscar_lista(catalogo, consultas),
"construir": lambda: crear_indice(catalogo),
"indice_preparado": lambda: buscar_indice(indice, consultas),
"indice_desde_cero": lambda: buscar_desde_cero(catalogo, consultas),
}
for nombre, accion in acciones.items():
print(f"n=m={tamano} | {nombre} | {medir_ms(accion):.6f} ms")
Ejecútalo desde la carpeta donde lo hayas guardado:
python medir_busquedas.py
Obtendrás cuatro líneas por tamaño. lista mide la resolución secuencial del lote; construir mide solo la creación del índice y el rechazo de duplicados; indice_preparado mide las consultas sobre el índice existente; indice_desde_cero incluye construir y consultar en cada ejecución. La creación de los datos sintéticos, las comprobaciones de igualdad y la impresión quedan fuera de la región medida. El tiempo de construir no debe sumarse alegremente a otra cifra para fingir una medición conjunta: precisamente por eso medimos también la operación completa.
Cada acción se ejecuta una vez antes de medir y después en cinco muestras de tres ejecuciones. Mostramos el menor tiempo por ejecución como aproximación al coste con menos interferencias en este ensayo pequeño. timeit ayuda a repetir la medida, pero no elimina las diferencias de equipo, versión, carga o gestión de memoria. Sus valores por defecto también desactivan temporalmente el recolector cíclico durante la medida; si ese trabajo importa en tu caso, tendrás que incluirlo. No conviertas la mejor muestra en una promesa de tiempo de respuesta.
Para repetir el ejercicio con C#, crea una aplicación de consola .NET 8:
dotnet new console --framework net8.0 -n MedirBusquedas
Sustituye Program.cs por este contenido. El comparador ordinal conserva la misma intención de comparar claves exactamente. Se generan únicamente claves ASCII en la medición; no estamos midiendo políticas lingüísticas ni normalización Unicode.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
static Dictionary<string, string> CrearIndice((string Codigo, string Texto)[] catalogo)
{
var indice = new Dictionary<string, string>(StringComparer.Ordinal);
foreach (var (codigo, texto) in catalogo)
if (!indice.TryAdd(codigo, texto))
throw new ArgumentException("codigo duplicado");
return indice;
}
static string?[] BuscarLista((string Codigo, string Texto)[] catalogo, string[] consultas)
{
var resultado = new string?[consultas.Length];
for (int i = 0; i < consultas.Length; i++)
foreach (var (codigo, texto) in catalogo)
if (codigo == consultas[i])
{
resultado[i] = texto;
break;
}
return resultado;
}
static string?[] BuscarIndice(Dictionary<string, string> indice, string[] consultas)
{
var resultado = new string?[consultas.Length];
for (int i = 0; i < consultas.Length; i++)
resultado[i] = indice.TryGetValue(consultas[i], out var texto) ? texto : null;
return resultado;
}
static string?[] BuscarDesdeCero((string Codigo, string Texto)[] catalogo, string[] consultas)
=> BuscarIndice(CrearIndice(catalogo), consultas);
static double MedirMs(Action accion)
{
accion();
double mejor = double.PositiveInfinity;
for (int muestra = 0; muestra < 5; muestra++)
{
var reloj = Stopwatch.StartNew();
for (int repeticion = 0; repeticion < 3; repeticion++)
accion();
reloj.Stop();
mejor = Math.Min(mejor, reloj.Elapsed.TotalMilliseconds / 3);
}
return mejor;
}
var pequeno = new[] { ("P01", "Aula"), ("P02", "") };
var preguntas = new[] { "P02", "X", "P01", "P01" };
var preparado = CrearIndice(pequeno);
string?[] esperadoPequeno = { "", null, "Aula", "Aula" };
if (!BuscarLista(pequeno, preguntas).SequenceEqual(esperadoPequeno) ||
!BuscarIndice(preparado, preguntas).SequenceEqual(esperadoPequeno) ||
!BuscarDesdeCero(pequeno, preguntas).SequenceEqual(esperadoPequeno))
throw new Exception("resultados diferentes");
foreach (int tamano in new[] { 10, 100, 1000 })
{
var catalogo = Enumerable.Range(0, tamano)
.Select(i => ($"P{i:0000}", $"Uso {i}")).ToArray();
var consultas = Enumerable.Range(0, tamano).Select(i => $"X{i:0000}").ToArray();
var indice = CrearIndice(catalogo);
var esperado = new string?[tamano];
if (!BuscarLista(catalogo, consultas).SequenceEqual(esperado) ||
!BuscarIndice(indice, consultas).SequenceEqual(esperado) ||
!BuscarDesdeCero(catalogo, consultas).SequenceEqual(esperado))
throw new Exception("resultados diferentes");
var acciones = new (string Nombre, Action Ejecutar)[]
{
("lista", () => { _ = BuscarLista(catalogo, consultas); }),
("construir", () => { _ = CrearIndice(catalogo); }),
("indice_preparado", () => { _ = BuscarIndice(indice, consultas); }),
("indice_desde_cero", () => { _ = BuscarDesdeCero(catalogo, consultas); })
};
foreach (var (nombre, accion) in acciones)
Console.WriteLine($"n=m={tamano} | {nombre} | " +
MedirMs(accion).ToString("F6", CultureInfo.InvariantCulture) + " ms");
}
Ejecuta la configuración Release:
dotnet run --project MedirBusquedas --configuration Release
Stopwatch mide el intervalo que rodea las tres llamadas. La llamada previa reduce algunos efectos de la primera ejecución, pero no estabiliza por completo la compilación y las optimizaciones del entorno .NET. Este pequeño banco permite observar tendencias; una evaluación de producción necesitaría más control del calentamiento, las asignaciones y las condiciones. Tampoco enfrentes sus milisegundos a los de Python como si hubiéramos preparado una comparación rigurosa entre lenguajes. No la hemos preparado.
Optimizar el cuello de botella, no el fragmento más vistoso
Al interpretar las salidas, comprueba primero que el programa termina sin fallos de igualdad y después observa cómo cambia cada operación al crecer el tamaño. El ensayo fuerza búsquedas fallidas y utiliza claves cortas. Si todas las consultas reales aciertan en la primera entrada, la lista hará mucho menos trabajo; si el catálogo cambia en cada consulta, no podrás amortizar el índice de la misma forma. Repite con la distribución de tu tarea antes de justificar una decisión con la distribución que acabamos de inventar.
Hay otra diferencia que suele desaparecer de las diapositivas: el índice preparado conserva una copia de las asociaciones de aquel momento. Si modificas el catálogo, tendrás que reconstruirlo o actualizarlo con una política explícita. Reutilizar un índice obsoleto puede producir errores con una rapidez admirable. En un proceso BIM conviene vincular esa estructura a la versión o al lote del que procede, en lugar de confiar en que nadie toque los datos entre dos pasos.
Para una aplicación mayor, mediría primero lectura, consultas externas, transformación, búsqueda y escritura por separado. Si descargar datos ocupa casi todo el recorrido, acelerar una búsqueda que apenas consume tiempo tendrá un efecto pequeño sobre el total. No afirmes que Revit o una API son el cuello de botella sin medirlos; tampoco hagas peticiones reales innecesarias para probar una comparación que puedes estudiar con datos preparados. Este artículo no ejecuta ninguna integración.
Python incluye un perfilador que ayuda a localizar funciones costosas. Sobre el archivo anterior puedes ejecutar:
python -m cProfile -s cumulative medir_busquedas.py
La salida de cProfile permite observar llamadas y tiempo acumulado. Aquí incluirá también el propio mecanismo de repetición, las comprobaciones y la impresión, por lo que no equivale a los intervalos anteriores. El perfilado añade sobrecoste y sirve para encontrar dónde investigar; volvería a medir la operación aislada después del cambio. Para memoria necesitarás una medición específica de asignaciones y picos: contar entradas del diccionario no demuestra cuántos bytes consume el proceso.
Yo conservaría una optimización cuando mantenga los resultados, reduzca un coste relevante y pueda explicarse sin ocultar sus condiciones. En este caso, preparar un índice reutilizable tiene sentido para muchos lotes de consultas; en otro, un recorrido sencillo puede bastar. Si quieres contrastar un caso en los comentarios, indica tamaño del catálogo, número de consultas, porcentaje de aciertos y si el índice se reutiliza. «Con muchos elementos va lento» deja demasiadas decisiones a la imaginación, y ya tenemos bastante de eso en las estimaciones de entrega.
Respuestas