Pięć form MOAD-0001

MOAD-0001 występuje w pięciu udokumentowanych formach w ponad 60 ekosystemach oprogramowania. Struktura: test przynależności przy użyciu kontenera sekwencyjnego, zagnieżdżony wewnątrz pętli po tym samym lub powiązanym zbiorze.

Pięć form

Wszystkie pięć mają tę samą strukturę: sprawdzenie przynależności zagnieżdżone w pętli, używające kontenera, który wymaga liniowego skanowania, aby odpowiedzieć na pytanie o przynależność.

Lista słów kluczowych skanowania

Audyt pod kątem MOAD-0001 oznacza wyszukiwanie słów kluczowych testu przynależności wewnątrz pętli:

- Python: in z zmienną typu list, .count(), list.index()

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

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

- C++: std::vector::find(), ręczna pętla z porównaniem ==

- Go: slices.Contains(), ręczna pętla po slice'u

Rozwiązanie w każdym przypadku: zastąp sekwencyjny kontener kontenerem haszującym. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Jedno słowo kluczowe. Jedna zamiana. Zero zmian w zachowaniu. 1 000× przyspieszenie przy N=1 000.

Audyt fragmentu kodu

Zastosuj rozpoznawanie wzorca MOAD-0001 do rzeczywistego fragmentu kodu.

Jedna linia, cztery języki

Rozwiązanie problemu MOAD-0001 w czterech językach:

# Python
visited = []       # PRZED: O(N) na sprawdzenie przynależności
visited = set()    # AFTER:  O(1) membership

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

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

// Go
visited := []NodeID{}              // PRZED: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // PO: wyszukiwanie w mapie O(1)
// _, ok := visited[n]  – sprawdzenie przynależności
// visited[n] = struct{}{}  – wstawianie elementu

We wszystkich przypadkach: to samo zachowanie, ten sam wynik, te same testy przechodzą. Zmienia się jedynie złożoność obliczeniowa.

Czego Naprawa NIE Zmienia

- Logicznego działania algorytmu: przeszukiwanie w głąb nadal odwiedza w kolejności głębokości

- Poprawność wyniku: te same węzły są odwiedzane w tej samej kolejności (w ramach DFS)

- Wyniki testów: wszystkie testy sprawdzające poprawność nadal przechodzą

Co zmienia poprawka

- Test przynależności: O(N) → O(1)

- Całkowity czas pętli: O(N²) → O(N)

- Przy N=1 000: 1 000× szybciej

- Przy N=10 000: 10 000× szybciej

Jedno ograniczenie: kolejność

Kontenery haszujące (set, HashSet, unordered_set) nie zachowują kolejności wstawiania. W Pythonie 3.7+ dict zachowuje kolejność wstawiania; zwykły set nie. W Javie HashSet nie zachowuje kolejności; LinkedHashSet tak.

Jeśli kolejność ma znaczenie obok przynależności: utrzymuj dwie struktury. set (lub HashSet) do testów przynależności w czasie O(1). Oddzielną list (lub ArrayList) do przechodzenia w kolejności. Lub użyj LinkedHashSet w Javie, który zapewnia obie rzeczy.

Dla MOAD-0001 w przechodzeniu grafu: visited odpowiada na pytanie binarne (czy ten węzeł został już odwiedzony?). Kolejność nie ma znaczenia dla pytania o przynależność. Kolejność przechodzenia wynika ze stosu lub kolejki, a nie z visited.

Przynależność a kolejność

W algorytmie Tarjana silnie spójnych składowych onStack śledzi, które węzły pozostają na bieżącym stosie wywołań DFS. Musi odpowiadać na dwa pytania: (1) przynależność — czy ten węzeł jest aktualnie na stosie? (2) na końcu ścieżki DFS usuń węzły ze stosu w kolejności aż do pojawienia się tego węzła.

Naiwna implementacja używa List dla onStack, odpowiadając na pytanie o przynależność za pomocą contains() — O(N) na sprawdzenie, O(N²) łącznie dla dużych grafów.

Dlaczego to jest ujawnienie, a nie łatka

MOAD-0001 występuje w ponad 1000 zweryfikowanych miejscach w ponad 60 ekosystemach oprogramowania. Przechodzenie grafów w narzędziach do budowania, deduplikacja tras w demonach routingu sieciowego, wykrywanie kolizji w silnikach gier, alokacja zasobów w schedulerach systemów operacyjnych.

Każde miejsce: poprawny kod. Każde miejsce: wzrost O(N²) czekający, aż N przekroczy pewien próg.

Potok ujawniania

Łatka bez ujawnienia u dostawcy naprawia tylko jedno miejsce. Wzorzec powraca w kolejnej wersji, kolejnej bibliotece, kolejnym porcie na inny język. Ujawnienie: nazwij wzorzec, udokumentuj go jako CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity), opublikuj heurystyki rozpoznawania i jednoliniową poprawkę. Wtedy każdy programista, który przeczyta ujawnienie, będzie mógł rozpoznać i naprawić własną instancję.

Hamming nazwał to „dać rybę vs nauczyć łowić”. Łatka daje rybę. Ujawnienie — nazwanie MOAD-0001, udokumentowanie wzorca, uogólnienie poprawki — uczy heurystyki.

Rozszerzenie Permakomputera

Hamming pracował nad rozwiązaniami punktowymi: napraw ten filtr, ulepsz ten kod. Unhamming dodaje warstwę ujawnienia: nazwij wzorzec, opublikuj heurystykę i oddaj ją do wspólnego zasobu.

Zasada wiedzy złożonej działa tu na poziomie ekosystemu. Jeden badacz nazywa wzorzec. Setka programistów rozpoznaje go we własnych bazach kodu. Tysiąc linii kodu O(N²) staje się O(N). Infrastruktura staje się szybsza dla wszystkich, którzy na niej budują.

To jest smok, który rośnie: ten sam ogień (praca nad ważnymi problemami, wiedza złożona, myślenie systemowe), inny lot (otwarte ujawnianie, własność wspólna, brak wymaganego patrona).