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 detecta errores lógicos: condiciones incorrectas, índices desplazados por uno, comprobaciones de nulidad faltantes. La revisión de código consciente de la complejidad detecta una clase diferente de defecto: código que funciona correctamente con N = 100 pero crece catastróficamente con N = 100,000.
Esta lección se conecta con una investigación más profunda en el curso de unhamming: El Capítulo Faltante: Complejidad Algorítmica cubre Big O en el contexto de defectos de producción, & MOAD-0001: El Defecto Sedimentario mapea el patrón en 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: cuenta la profundidad de anidamiento de bucles primero.
Contenedor secuencial dentro de un bucle activo. Cualquier comprobación .contains(), .includes(), .find(), o in list dentro de un bucle cuesta O(N) por comprobación. En N iteraciones: O(N²) total. Este patrón aparece en código de producción en docenas de ecosistemas — el compilador GHC Haskell, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. El mismo error, diferentes bases de código.
Revisión: find_duplicates
Revisa la siguiente función de Python para la 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 código de producción en docenas de ecosistemas de software:
- GHC (compilador Haskell): resolutor de dependencias, O(N²) con N = 50,000 paquetes, compilaciones de 17 minutos
- Python pip: resolución de conflictos de dependencias
- Apache Maven: deduplicación de classpath
- Rust Cargo: unificación de características
- compilador TypeScript: resolución de módulos
- Godot / Redot motor de juegos: traversal de gráfico de nodos
Ninguno de estos equipos cometió un error. Escribieron código correcto con N pequeño. N creció. El código se calcificó. El patrón tiene un nombre: MOAD-0001, El Defecto Sedimentario. Sedimento: correcto, inofensivo en capas delgadas. Con el tiempo, las capas se acumulan y endurecen.
La Corrección
En todos los casos: reemplaza el contenedor secuencial con un contenedor hash. Una línea. Cero cambio de comportamiento en entradas correctas. Aceleración 100–1000× con N en el mundo real.
La corrección funciona porque dos operaciones necesitan mantenerse rápidas:
1. Comprobación de pertenencia: ¿se ha visto este elemento antes?
2. Salida ordenada: devuelve elementos en el orden en que aparecieron (a veces requerido, a veces no).
Un conjunto maneja (1) en O(1). Si (2) también importa, mantén una lista separada para la salida ordenada y un conjunto para la comprobación de pertenencia. Dos estructuras de datos, cada una haciendo un trabajo.
Respondiendo a un Revisor
Una solicitud de cambios corrige MOAD-0001 en la función de traversal de gráfico de un proyecto. Un revisor comenta:
> "Los conjuntos no preservan el orden de inserción — esto cambia el comportamiento."
El Patrón de Análisis de Entrevista
El Formato Esperado
El análisis de complejidad algorítmica aparece en entrevistas de ingeniería de software. Una respuesta fuerte sigue un patrón de cuatro partes:
1. Indica la complejidad actual — O(?) para tiempo, O(?) para espacio.
2. Explica por qué — identifica el constructo específico responsable (bucle anidado, escaneo lineal en bucle, ramificación recursiva).
3. Propón una optimización — nombra el cambio y la estructura de datos o algoritmo que introduce.
4. Indica la nueva complejidad — después de la corrección, ¿cuál es la complejidad de tiempo & espacio?
Ejemplo:
Código: [función que verifica pertenencia en una lista dentro de un bucle]
Actual: O(N²) — `item in seen_list` es O(N) por comprobación × N iteraciones
Optimización: reemplaza seen_list con seen_set (conjunto hash)
Después: O(N) — la comprobación de pertenencia al conjunto es O(1)Esta habilidad se transfiere más allá de las entrevistas: revisión de código consciente de la complejidad, diseño de arquitectura, depuración de rendimiento, auditorías de seguridad. Cualquier sistema que procese entradas de tamaño variable se beneficia de ella.
Esta lección se conecta hacia adelante al curso de unhamming, que aplica exactamente este patrón a la investigación de defectos de producción en 60+ proyectos de código abierto.
Entrevista: Analiza has_common_element
Aplica 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