Fem former av MOAD-0001

MOAD-0001 förekommer i fem dokumenterade former över 60+ mjukvaruekosystem. Strukturen: ett medlemskapstest med en sekventiell behållare, nästlad inuti en loop över samma eller relaterad samling.

De fem formerna

Alla fem delar samma struktur: ett medlemskapstest nästlat i en loop, med en behållare som kräver en linjär sökning för att besvara medlemskapsfrågan.

Nyckelordslistan för scanning

Att granska för MOAD-0001 innebär att söka efter medlemskapstest-nyckelord inuti loopar:

- Python: in med en list-variabel, .count(), list.index()

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

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

- C++: std::vector::find(), manuell loop med ==-jämförelse

- Go: slices.Contains(), manuell loop över en slice

Fixen i varje fall: ersätt den sekventiella containern med en hash-container. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Ett nyckelord. En substitution. Noll beteendeförändring. 1 000× snabbare vid N=1 000.

Granska ett kodfragment

Tillämpa MOAD-0001-mönsterigenkänning på ett riktigt kodfragment.

En Rad, Fyra Språk

Fixen för MOAD-0001 i fyra språk:

# Python
visited = []       # FÖRE: O(N) medlemskap
visited = set()    # EFTER:  O(1) membership

// Java
List<Node> visited = new ArrayList<>();    // FÖRE
Set<Node> visited = new HashSet<>();       // EFTER

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

// Go
visited := []NodeID{}              // FÖRE: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // EFTER: map lookup O(1)
// _, ok := visited[n]  för medlemskoll
// visited[n] = struct{}{}  för insättning

I varje fall: samma beteende, samma utdata, samma tester som passerar. Endast tillväxttakten ändras.

Vad fixen INTE ändrar

- Algoritmens logiska beteende: depth-first besöker fortfarande depth-first

- Korrekt utdata: samma noder besöks i samma ordning (inom DFS)

- Testresultat: alla tester som kontrollerar korrekthet fortsätter att passera

Vad fixen ÄNDRAR

- Medlemskapstest: O(N) → O(1)

- Total tid för loop: O(N²) → O(N)

- Vid N=1 000: 1 000× snabbare

- Vid N=10 000: 10 000× snabbare

En begränsning: Ordning

Hash-containrar (set, HashSet, unordered_set) bevarar inte insättningsordningen. I Python 3.7+ bevarar dict insättningsordningen; vanlig set gör det inte. I Java bevarar HashSet inte ordningen; LinkedHashSet gör det.

Om ordning är viktig tillsammans med medlemskap: underhåll två strukturer. Ett set (eller HashSet) för O(1)-medlemskapstester. En separat list (eller ArrayList) för ordnad genomgång. Eller använd LinkedHashSet i Java, som ger båda.

För MOAD-0001 i grafgenomgång: visited besvarar en binär fråga (har denna nod setts tidigare?). Ordning spelar ingen roll för medlemskapsfrågan. Genomgångsordningen kommer från stacken eller kön, inte från visited.

Medlemskap vs ordning

I Tarjans algoritm för starkt sammanhängande komponenter spårar onStack vilka noder som fortfarande finns på den aktuella DFS-anropsstacken. Den måste besvara två frågor: (1) medlemskap — finns denna nod för närvarande på stacken? (2) i slutet av en DFS-väg, poppa noder i ordning tills denna nod dyker upp.

En naiv implementation använder en List för onStack och besvarar medlemskapsfrågan med contains() — O(N) per kontroll, O(N²) totalt för stora grafer.

Varför detta är en disclosure, inte en patch

MOAD-0001 finns i över 1 000 verifierade platser i 60+ mjukvaruekosystem. Graftraversering i byggverktyg, ruttavdragning i nätverksroutrar, kollisionsdetektering i spelmotorer, resursallokering i operativsystemets schemaläggare.

Varje plats: korrekt kod. Varje plats: O(N²)-tillväxt som väntar på att N ska passera en tröskel.

Disclosure-pipeline

En patch utan upstream-disclosure fixar bara en plats. Mönstret återkommer i nästa version, nästa bibliotek, nästa språkportning. Disclosure: namnge mönstret, dokumentera det som CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity), publicera igenkänningsheuristiken och den enkla fixen. Då kan varje utvecklare som läser disclosuren känna igen och åtgärda sitt eget fall.

Hamming kallade detta ”ge en fisk vs lära ut fiske”. Patchen ger en fisk. Disclosuren — MOAD-0001 namngiven, mönstret dokumenterat, fixen generaliserad — lär ut heuristiken.

Permadatorns utvidgning

Hamming arbetade med punktlösningar: fixa detta filter, förbättra denna kod. Avhamming lägger till avslöjandelagret: namnge mönstret, publicera heuristiken och ge den till allmänningen.

Principen om sammansatt kunskap gäller här på ekosystemnivå. En forskare namnger ett mönster. Hundra utvecklare känner igen det i sina egna kodbaser. Tusen rader O(N²)-kod blir O(N). Infrastrukturen blir snabbare för alla som bygger på den.

Detta är draken som växer: samma eld (arbeta med viktiga problem, sammansatt kunskap, systemtänkande), annan flygning (öppet avslöjande, gemensamt ägande, ingen mecenat krävs).