Cinque Forme di MOAD-0001

MOAD-0001 appare in cinque forme documentate in oltre 60 ecosistemi software. La struttura: un test di appartenenza che utilizza un contenitore sequenziale, annidato all'interno di un ciclo sulla stessa o su una collezione correlata.

Le Cinque Forme

Tutti e cinque condividono la stessa struttura: un controllo di appartenenza annidato in un ciclo, che utilizza un contenitore che richiede una scansione lineare per rispondere alla domanda di appartenenza.

L’elenco delle parole chiave di scansione

L’audit per MOAD-0001 significa cercare con grep le parole chiave di test di appartenenza all’interno dei cicli:

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

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

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

- C++: std::vector::find(), ciclo manuale con confronto ==

- Go: slices.Contains(), ciclo manuale su uno slice

La correzione in ogni caso: sostituire il contenitore sequenziale con un contenitore hash. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Una parola chiave. Una sostituzione. Zero cambiamenti comportamentali. Velocità 1.000× a N=1.000.

Esegui l’audit di un frammento di codice

Applica il riconoscimento del pattern MOAD-0001 a un frammento di codice reale.

Una riga, quattro linguaggi

La correzione per MOAD-0001 in quattro linguaggi:

# Python
visited = []       # PRIMA: membership O(N)
visited = set()    # AFTER:  O(1) membership

// Java
List<Node> visited = new ArrayList<>();    // BEFORE
Set<Node> visited = new HashSet<>();       // AFTER

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

// Go
visited := []NodeID{}              // PRIMA: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // DOPO: map lookup O(1)
// _, ok := visited[n]  per il controllo di appartenenza
// visited[n] = struct{}{}  per l'inserimento

In ogni caso: stesso comportamento, stesso output, stessi test superati. Cambia solo il tasso di crescita.

Cosa la correzione NON cambia

- Il comportamento logico dell'algoritmo: la ricerca in profondità resta in profondità

- Correttezza dell'output: gli stessi nodi vengono visitati nello stesso ordine (all'interno della DFS)

- Risultati dei test: tutti i test che verificano la correttezza continuano a passare

Cosa cambia con la correzione

- Test di appartenenza: O(N) → O(1)

- Ciclo totale: O(N²) → O(N)

- Con N=1.000: 1.000× più veloce

- Con N=10.000: 10.000× più veloce

Un limite: l'ordine

I contenitori hash (set, HashSet, unordered_set) non preservano l'ordine di inserimento. In Python 3.7+, dict mantiene l'ordine di inserimento; il semplice set no. In Java, HashSet non mantiene l'ordine; LinkedHashSet sì.

Se l'ordine è importante insieme all'appartenenza: mantieni due strutture. Un set (o HashSet) per i test di appartenenza in O(1). Una list (o ArrayList) separata per la scansione ordinata. Oppure usa LinkedHashSet in Java, che fornisce entrambe.

Per MOAD-0001 nella visita di grafi: visited risponde a una domanda binaria (questo nodo è già stato visto?). L'ordine non conta per la domanda di appartenenza. L'ordine di visita deriva dallo stack o dalla coda, non da visited.

Appartenenza vs Ordinamento

Nell'algoritmo di Tarjan per le componenti fortemente connesse, onStack tiene traccia dei nodi ancora presenti nello stack di chiamate DFS corrente. Deve rispondere a due domande: (1) appartenenza — questo nodo è attualmente nello stack? (2) alla fine di un percorso DFS, rimuovi nodi in ordine finché non appare questo nodo.

Un'implementazione ingenua usa una List per onStack, rispondendo alla domanda di appartenenza con contains() — O(N) per controllo, O(N²) totale per grafi grandi.

Perché si tratta di una Disclosure, non di una Patch

MOAD-0001 è presente in oltre 1.000 siti verificati in più di 60 ecosistemi software. Attraversamento di grafi negli strumenti di build, deduplicazione di route nei demoni di routing di rete, rilevamento di collisioni nei motori di gioco, allocazione di risorse negli scheduler dei sistemi operativi.

Ogni sito: codice corretto. Ogni sito: crescita O(N²) in attesa che N superi una soglia.

La Pipeline di Disclosure

Una patch senza disclosure upstream corregge un solo sito. Il pattern si ripresenta nella versione successiva, nella prossima libreria, nel prossimo porting linguistico. Disclosure: nominare il pattern, documentarlo come CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity), pubblicare le euristiche di riconoscimento e la correzione a una riga. Così ogni sviluppatore che legge la disclosure può riconoscere e correggere la propria istanza.

Hamming lo definiva 'dare un pesce vs insegnare a pescare'. La patch dà un pesce. La disclosure — MOAD-0001 nominato, pattern documentato, correzione generalizzata — insegna l'euristica.

L’Estensione Permacomputer

Hamming lavorava su soluzioni puntuali: correggere questo filtro, migliorare questo codice. L’Unhamming aggiunge il livello di disclosure: nominare il pattern, pubblicare l’euristica e donarla ai commons.

Il principio della conoscenza composta si applica qui su scala ecosistemica. Un ricercatore nomina un pattern. Cento sviluppatori lo riconoscono nei propri codebase. Mille righe di codice O(N²) diventano O(N). L’infrastruttura diventa più veloce per tutti coloro che vi costruiscono sopra.

Questo è il drago che cresce: stesso fuoco (lavorare su problemi importanti, conoscenza composta, pensiero sistemico), volo diverso (disclosure aperta, proprietà comune, nessun patron richiesto).