Lectura de Código para Tasas de Crecimiento
Revisión de Código para Corrección vs Revisión de Código para Complejidad
La revisión de código para corrección captura errores lógicos: condiciones incorrectas, índices off-by-one, verificaciones de nulo faltantes. La revisión de código con conciencia de complejidad captura una clase diferente de defecto: código que funciona correctamente en N = 100, pero crece catastróficamente en N = 100,000.
Esta lección se conecta con una investigación más profunda en el curso deshamming: [Capítulo Faltante: Complejidad Algorítmica](/es/un/unhamming_algorithmic_complexity) cubre el Big O en el contexto de defectos de producción y [MOAD-0001: El Defecto Sedimentario](/es/un/unhamming_moad_sedimentary) mapea el patrón a través de +60 ecosistemas de software.
Dos Heurísticas de Revisión
Los bucles anidados multiplican la complejidad. Dos bucles anidados sobre N elementos producen O(N²). Tres producen O(N³). Al revisar: conte la profundidad de anidamiento de bucles primero.
Contenedor secuencial dentro de un bucle caliente. Cualquier .contains(), .includes(), .find() o verificación in list dentro de un bucle cuesta O(N) por verificación. Sobre N iteraciones: O(N²) en total. Este patrón aparece en el código de producción en decenas de ecosistemas - el compilador GHC de Haskell, pip de Python, Apache Maven, Rust Cargo, TypeScript, Godot. El mismo error, diferentes bases de código.
Revisar: find_duplicates
Revisa el siguiente función de Python para complejidad:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: El Defecto Sedimentario
El Mismo Defecto, Sesenta Ecosistemas
El patrón if x not in list: list.append(x) dentro de un bucle aparece —ha aparecido— en el código de producción en decenas de ecosistemas de software:
- GHC (compilador de Haskell): resolutor de dependencias, O(N²) a N = 50.000 paquetes, 17 minutos de compilación
- Python pip: resolución de conflictos de dependencias
- Apache Maven: deduplicación de classpath
- Rust Cargo: unificación de características
- Compilador de TypeScript: resolución de módulos
- Motor de juego Godot / Redot: recorrido de la gráfica de nodos
Ninguno de estos equipos cometió un error. Escribieron código correcto a pequeña escala. N creció. El código se calcificó. El patrón tiene un nombre: MOAD-0001, El Defecto Sedimentario. Sedimento: correcto e inocuo en capas delgadas. Con el tiempo, las capas se acumulan y se endurecen.
La Solución
En todos los casos: sustituye el contenedor secuencial por un contenedor de hash. Una línea. Sin cambio de comportamiento a los ingresos correctos. Aceleración de 100-1.000 veces a N real.
La solución funciona porque dos operaciones deben mantenerse rápidas:
1. Verificación de pertenencia: ¿este elemento se ha visto antes?
2. Salida ordenada: devuelva los elementos en el orden en que aparecieron (a veces requerido, a veces no).
Un conjunto maneja (1) en O(1). Si también importa (2), mantenga una lista separada para la salida ordenada y un conjunto para la verificación de pertenencia. Dos estructuras de datos, cada una haciendo una sola tarea.
Responder a una Revisión
Una solicitud de extracción corrige MOAD-0001 en una función de recorrido de gráfica de un proyecto. Un revisor comenta:
> "Sets don't preserve insertion order — this changes behavior."
El patrón de análisis de entrevista
El formato esperado
El análisis de complejidad algorítmica aparece en las entrevistas de ingeniería de software. Una respuesta sólida sigue un patrón de cuatro partes:
1. Establecer la complejidad actual — O(?) para el tiempo, O(?) para el espacio.
2. Explicar por qué — identifique la construcción específica responsable (bucle anidado, escaneo lineal en bucle, ramificación recursiva).
3. Proponer una optimización — nombre el cambio y la estructura de datos o algoritmo que introduce.
4. Establecer la nueva complejidad — después de la corrección, ¿cuál es la complejidad de tiempo y espacio?
Ejemplo:
Código: [función que verifica la pertenencia en una lista dentro de un bucle]
Actual: O(N²) — `item in seen_list` es O(N) por verificación × N iteraciones
Optimización: reemplazar seen_list con seen_set (conjunto hash)
Después: O(N) — la verificación de pertenencia en un conjunto es O(1)Esta habilidad se transfiere más allá de las entrevistas: revisión de código consciente de complejidad, diseño de arquitectura, depuración de rendimiento, auditorías de seguridad. Cualquier sistema que procesa entradas de tamaño variable se beneficia de ello.
Esta lección se conecta hacia adelante al curso no hamming, que aplica este patrón exacto a la investigación de defectos en producción en más de 60 proyectos de código abierto.
Entrevista: Analizar has_common_element
Aplicar el formato de entrevista de cuatro partes a esta función:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False