Fünf Formen von MOAD-0001

MOAD-0001 tritt in fünf dokumentierten Formen in über 60 Software-Ökosystemen auf. Die Struktur: ein Membership-Test mit einem sequentiellen Container, verschachtelt in einer Schleife über dieselbe oder eine verwandte Collection.

Die fünf Formen

Alle fünf teilen dieselbe Struktur: eine Mitgliedschaftsprüfung, die in einer Schleife verschachtelt ist und einen Container verwendet, der einen linearen Scan benötigt, um die Mitgliedschaftsfrage zu beantworten.

Die Scanning-Schlüsselwortliste

Das Auditieren von MOAD-0001 bedeutet, nach Mitgliedschafts-Test-Schlüsselwörtern innerhalb von Schleifen zu greppen:

- Python: in mit einer list-Variablen, .count(), list.index()

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

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

- C++: std::vector::find(), manuelle Schleife mit ==-Vergleich

- Go: slices.Contains(), manuelle Schleife über ein Slice

Die Lösung in jedem Fall: Ersetze den sequentiellen Container durch einen Hash-Container. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Ein Schlüsselwort. Eine Substitution. Keine Verhaltensänderung. 1.000× Beschleunigung bei N=1.000.

Code-Fragment prüfen

Wende MOAD-0001-Mustererkennung auf ein reales Code-Fragment an.

Eine Zeile, vier Sprachen

Die Lösung für MOAD-0001 in vier Sprachen:

# Python
visited = []       # VORHER: O(N)-Mitgliedschaft
visited = set()    # NACHHER: O(1)-Mitgliedschaft

// Java
List<Node> visited = new ArrayList<>();    // VORHER
Set<Node> visited = new HashSet<>();       // NACHHER

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

// Go
visited := []NodeID{}              // VORHER: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // NACHHER: Map-Lookup O(1)
// _, ok := visited[n]  für die Mitgliedschaftsprüfung
// visited[n] = struct{}{}  für das Einfügen

In jedem Fall: gleiches Verhalten, gleiche Ausgabe, gleiche Tests bestanden. Nur die Wachstumsrate ändert sich.

Was die Korrektur NICHT ändert

- Das logische Verhalten des Algorithmus: Tiefensuche bleibt Tiefensuche

- Korrektheit der Ausgabe: dieselben Knoten werden in derselben Reihenfolge besucht (innerhalb von DFS)

- Testergebnisse: alle Tests, die auf Korrektheit prüfen, bleiben weiterhin bestanden

Was die Optimierung ÄNDERT

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

- Gesamtlaufzeit: O(N²) → O(N)

- Bei N=1.000: 1.000× schneller

- Bei N=10.000: 10.000× schneller

Eine Einschränkung: Reihenfolge

Hash-Container (set, HashSet, unordered_set) speichern keine Einfügereihenfolge. In Python 3.7+ erhält dict die Einfügereihenfolge; ein normales set nicht. In Java behält HashSet keine Reihenfolge bei; LinkedHashSet schon.

Wenn Reihenfolge neben der Mitgliedschaft wichtig ist: zwei Strukturen parallel führen. Ein set (oder HashSet) für O(1)-Mitgliedschaftstests. Eine separate list (oder ArrayList) für die geordnete Traversierung. Oder LinkedHashSet in Java verwenden, das beides bietet.

Für MOAD-0001 bei der Graph-Traversierung: visited beantwortet eine binäre Frage („Wurde dieser Knoten bereits gesehen?“). Die Reihenfolge spielt für die Mitgliedschaftsfrage keine Rolle. Die Traversierungsreihenfolge ergibt sich aus dem Stack oder der Queue, nicht aus visited.

Mitgliedschaft vs. Reihenfolge

In Tarjans Algorithmus für stark zusammenhängende Komponenten verfolgt onStack, welche Knoten noch auf dem aktuellen DFS-Aufrufstack liegen. Es muss zwei Fragen beantworten: (1) Mitgliedschaft – liegt dieser Knoten gerade auf dem Stack? (2) Am Ende eines DFS-Pfads Knoten in der richtigen Reihenfolge entfernen, bis dieser Knoten erscheint.

Eine naive Implementierung verwendet eine List für onStack und beantwortet die Mitgliedschaftsfrage mit contains() – O(N) pro Prüfung, insgesamt O(N²) bei großen Graphen.

Warum dies eine Disclosure und kein Patch ist

MOAD-0001 existiert in über 1.000 verifizierten Sites in mehr als 60 Software-Ökosystemen. Graphentraversierung in Build-Tools, Routen-Deduplizierung in Netzwerk-Routing-Daemons, Kollisionserkennung in Game-Engines, Ressourcenzuweisung in Betriebssystem-Schedulern.

Jede Site: korrekter Code. Jede Site: O(N²)-Wachstum, das darauf wartet, dass N einen Schwellenwert überschreitet.

Die Disclosure-Pipeline

Ein Patch ohne Upstream-Disclosure behebt nur eine einzelne Site. Das Muster tritt in der nächsten Version, der nächsten Bibliothek, dem nächsten Sprach-Port erneut auf. Disclosure: Benennen Sie das Muster, dokumentieren Sie es als CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity), veröffentlichen Sie die Erkennungsheuristiken und den Einzeiler-Fix. Dann kann jeder Entwickler, der die Disclosure liest, seine eigene Instanz erkennen und beheben.

Hamming nannte dies „einen Fisch geben vs. Fischen lehren“. Der Patch gibt einen Fisch. Die Disclosure – MOAD-0001 benannt, Muster dokumentiert, Fix verallgemeinert – lehrt die Heuristik.

Die Permacomputer-Erweiterung

Hamming arbeitete an punktuellen Lösungen: diesen Filter reparieren, diesen Code verbessern. Unhamming fügt die Offenlegungsschicht hinzu: das Muster benennen, die Heuristik veröffentlichen und sie dem Gemeingut übergeben.

Das Prinzip des zusammengesetzten Wissens gilt hier auf Ökosystemebene. Ein Forscher benennt ein Muster. Hundert Entwickler erkennen es in ihren eigenen Codebasen. Tausend Zeilen O(N²)-Code werden zu O(N). Die Infrastruktur wird schneller für alle, die darauf aufbauen.

Das ist der Drache, der wächst: dasselbe Feuer (an wichtigen Problemen arbeiten, Wissen kumulieren, systemisches Denken), anderer Flug (offene Offenlegung, Gemeingut-Besitz, kein Patron erforderlich).