Cinco formas de MOAD-0001

MOAD-0001 aparece en cinco formas documentadas en más de 60 ecosistemas de software. La estructura: una prueba de pertenencia que usa un contenedor secuencial, anidada dentro de un bucle sobre la misma colección o una relacionada.

Las cinco formas

Los cinco comparten la misma estructura: una comprobación de pertenencia anidada en un bucle, usando un contenedor que requiere un escaneo lineal para responder a la pregunta de pertenencia.

La lista de palabras clave de escaneo

Auditar MOAD-0001 significa buscar palabras clave de comprobación de pertenencia dentro de bucles:

- Python: in con una variable list, .count(), list.index()

- Java: ArrayList.contains(), List.contains(), LinkedList.contains()

- JavaScript: Array.includes(), Array.indexOf(), Array.find()

- C++: std::vector::find(), bucle manual con comparación == [BLOCK_TYPE SECTION/STEP]

- Go: slices.Contains(), bucle manual sobre un slice [BLOCK_TYPE SECTION/STEP]

La solución en cada caso: reemplaza el contenedor secuencial por un contenedor hash. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}. [BLOCK_TYPE SECTION/STEP]

Una palabra clave. Una sustitución. Cero cambio de comportamiento. Aceleración de 1 000× con N=1 000. [BLOCK_TYPE SECTION/STEP]

Auditar un fragmento de código [BLOCK_TYPE SECTION/STEP]

Aplica el reconocimiento de patrones MOAD-0001 a un fragmento de código real. [BLOCK_TYPE SECTION/STEP]

Una línea, cuatro lenguajes

La solución para MOAD-0001 en cuatro lenguajes:

# Python
visited = []       # ANTES: pertenencia O(N)
visited = set()    # DESPUÉS: O(1) membership

// Java
List<Node> visited = new ArrayList<>();    // ANTES
Set<Node> visited = new HashSet<>();       // DESPUÉS

// JavaScript
const visited = [];      // ANTES: Array.includes() O(N)
const visited = new Set(); // DESPUÉS: Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)

// Go
visited := []NodeID{}              // ANTES: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // DESPUÉS: búsqueda en mapa O(1)
// _, ok := visited[n]  para comprobar pertenencia
// visited[n] = struct{}{}  para inserción

En todos los casos: mismo comportamiento, misma salida, mismos tests aprobados. Solo cambia la tasa de crecimiento.

Lo que la corrección NO cambia

- El comportamiento lógico del algoritmo: depth-first sigue visitando en profundidad

- Correctitud de salida: los mismos nodos se visitan en el mismo orden (dentro de DFS)

- Resultados de las pruebas: cualquier prueba que verifique la correctitud sigue aprobando

Qué SÍ cambia la corrección

- Prueba de pertenencia: O(N) → O(1)

- Bucle total: O(N²) → O(N)

- En N=1.000: 1.000× más rápido

- En N=10.000: 10.000× más rápido

Un límite: el orden

Los contenedores hash (set, HashSet, unordered_set) no preservan el orden de inserción. En Python 3.7+, dict sí preserva el orden de inserción; set simple no. En Java, HashSet no preserva el orden; LinkedHashSet sí.

Si el orden importa junto con la pertenencia: mantén dos estructuras. Un set (o HashSet) para pruebas de pertenencia O(1). Una list (o ArrayList) separada para recorrido ordenado. O usa LinkedHashSet en Java, que proporciona ambas.

Para MOAD-0001 en recorrido de grafos: visited responde una pregunta binaria (¿este nodo ya se ha visto?). El orden no importa para la pregunta de pertenencia. El orden de recorrido proviene de la pila o cola, no de visited.

Pertenencia vs Orden

En el algoritmo de componentes fuertemente conectados de Tarjan, onStack rastrea qué nodos permanecen en la pila de llamadas DFS actual. Debe responder dos preguntas: (1) pertenencia — ¿este nodo está actualmente en la pila? (2) al final de un camino DFS, extraer nodos en orden hasta que aparezca este nodo.

Una implementación ingenua usa una List para onStack, respondiendo la pregunta de pertenencia con contains() — O(N) por verificación, O(N²) en total para grafos grandes.

Por qué esto es una divulgación, no un parche

MOAD-0001 existe en más de 1.000 sitios verificados en más de 60 ecosistemas de software. Recorrido de grafos en herramientas de compilación, deduplicación de rutas en demonios de enrutamiento de red, detección de colisiones en motores de juegos, asignación de recursos en planificadores de sistemas operativos.

Cada sitio: código correcto. Cada sitio: crecimiento O(N²) esperando a que N cruce un umbral.

El pipeline de divulgación

Un parche sin divulgación upstream corrige un solo sitio. El patrón reaparece en la siguiente versión, la siguiente biblioteca, el siguiente puerto a otro lenguaje. Divulgación: nombrar el patrón, documentarlo como CWE-407 (Complejidad Algorítmica: Complejidad Algorítmica Ineficiente), publicar las heurísticas de reconocimiento y la corrección de una línea. Así, cada desarrollador que lea la divulgación podrá reconocer y corregir su propia instancia.

Hamming lo llamó «dar un pez vs. enseñar a pescar». El parche da un pez. La divulgación —MOAD-0001 nombrado, patrón documentado, corrección generalizada— enseña la heurística.

La Extensión Permacomputadora

Hamming trabajaba en soluciones puntuales: arreglar este filtro, mejorar este código. Unhamming añade la capa de divulgación: nombrar el patrón, publicar la heurística y entregarla al común.

El principio de conocimiento compuesto se aplica aquí a escala de ecosistema. Un investigador nombra un patrón. Cien desarrolladores lo reconocen en sus propias bases de código. Mil líneas de código O(N²) se convierten en O(N). La infraestructura se vuelve más rápida para todos los que construyen sobre ella.

Este es el dragón que crece: mismo fuego (trabajar en problemas importantes, conocimiento compuesto, pensamiento sistémico), vuelo diferente (divulgación abierta, propiedad común, sin necesidad de patrocinador).