Geometryczna intuicja Hamminga
Hamming widział geometrię wszędzie
Rozdział 9 Hamminga zaczyna się ostrzeżeniem: geometryczna intuicja zawodzi w wysokich wymiarach. W wymiarze 3D sfera zajmuje większość swojego otaczającego sześcianu. W wymiarze 10D sfera zajmuje mniej niż 0,2% objętości sześcianu. W wymiarze 100D frakcja zaokrągla się do zera. Objętość skupia się blisko powierzchni. Punkty skupiają się blisko narożników, nie w centrum.
Jego kody korygujące błędy wykorzystywały to bezpośrednio. Kody Hamminga pakują słowa kodowe w n-wymiarową przestrzeń binarną w taki sposób, że każde słowo kodowe jest otoczone sferą błędów, które można poprawić. Geometria określa, ile błędów można poprawić. Pakowanie sfer w przestrzeni n-wymiarowej jest problemem matematycznym z rzeczywistymi stawkami: upakuj sfery gęściej, poprawiaj więcej błędów.
Ten sam geometryczny tryb awarii dotyczy złożoności algorytmicznej. Przy małych N, O(N²) i O(N) wyglądają na wykresie prawie identycznie. Różnica między nimi wydaje się do opanowania. Przy dużych N różnica eksploduje — dokładnie jak ułamek objętości sfery zawala się w wysokich wymiarach. To, co wydaje się opłacalne w małej skali, становится niemożliwe w dużej skali.
Kształt każdej klasy złożoności
Rysowanie złożoności
Każda klasa złożoności ma kształt geometryczny:
- O(1): linia pozioma. Ten sam koszt niezależnie od N. Bez nachylenia.
- O(log N): łagodna krzywa rosnąca, która się spłaszcza. Podwaja się za każdym razem, gdy N się podnosi do kwadratu. Rośnie proporcjonalnie do liczby cyfr w N.
- O(N): linia diagonalna przez początek. Koszt rośnie proporcjonalnie do N.
- O(N log N): linia diagonalna nieco bardziej stroma. Linia, która bardzo delikatnie się wygina w górę.
- O(N²): parabola. Przy N=100: 10 000 operacji. Przy N=1 000: 1 000 000 operacji.
Kluczowa obserwacja: stosunek między dwiema klasami złożoności sam jest funkcją N. Przy N=10, O(N²) kosztuje 10× więcej niż O(N). Przy N=1 000, O(N²) kosztuje 1 000× więcej. Przy N=1 000 000, kosztuje 1 000 000× więcej. Różnica nie tylko rośnie — rośnie w tempie samego N.
To jest geometryczny argument, dlaczego patche MOAD-0001 mają znaczenie. Przeniesienie resolvera zależności z O(N²) do O(N) nie jest stałym przyspieszeniem. Przy N=50 000 pakietów, jest to przyspieszenie 50 000×. Przy N=100 000, jest to przyspieszenie 100 000×. Wartość patcha rośnie wraz z rozmiarem problemu.
Poszerzająca się przepaść
O(N²) i O(N) obaj produkują poprawne wyniki.
Przy N=10: O(N²) kosztuje 100 operacji, O(N) kosztuje 10 operacji. Stosunek: 10×.
Przy N=1 000: O(N²) kosztuje 1 000 000 operacji, O(N) kosztuje 1 000 operacji.
Grafy jako geometria
Skierowany graf acykliczny
DAG (directed acyclic graph) jest strukturą geometryczną: węzły połączone skierowanymi krawędziami bez cykli. Grafy zależności oprogramowania, potoki kompilacji i architektury przepływu danych wszystkie tworzą DAG.
Każdy węzeł ma właściwości geometryczne mierzone przez liczenie jego krawędzi:
- Stopień wejściowy: liczba krawędzi przybywajacej do węzła. Wysoki stopień wejściowy oznacza, że wiele zależności ze źródeł zasilających ten węzeł.
- Stopień wyjściowy: liczba krawędzi opuszczających węzeł. Wysoki stopień wyjściowy oznacza, że wielu konsumentów zależy od tego węzła.
- Pośredniość: stopień wejściowy + stopień wyjściowy. Mierzy, ile ścieżek przechodzi przez ten węzeł. Węzeł o wysokiej pośredniości siedzi na rozdrożu w grafie.
- Wynik surge'a: przyspieszenie × stopień wejściowy. Mierzy, ile pracy zalewu węzłów poniżej, gdy to wąskie gardło się wyjaśni.
Model fabryki daje tym właściwościom geometrycznym znaczenie fizyczne:
- Wysoka pośredniość + wysoki wynik surge'a = węzeł workaholic. Usunięcie tego wąskiego gardła bez przygotowania węzłów poniżej = zapaść.
- Wysoki stopień wyjściowy + niski wynik surge'a = węzeł glutton. Konsumuje bez produkowania. Maszyna, która zapomina się zatrzymać.
Surge i pośredniość w praktyce
Czytanie DAG
Rozważ łańcuch 5 węzłów: A → B → C → D → E, plus dodatkową krawędź B → D.
- A: stopień wejściowy 0, stopień wyjściowy 1, pośredniość 1. Węzeł źródła. Nic go nie zasilą. Jeden konsument.
- B: stopień wejściowy 1 (od A), stopień wyjściowy 2 (do C i do D), pośredniość 3. Zasilą dwa węzły poniżej — punkt rozwidlenia.
- C: stopień wejściowy 1 (od B), stopień wyjściowy 1 (do D), pośredniość 2. Węzeł przejściowy.
- D: stopień wejściowy 2 (od B i od C), stopień wyjściowy 1 (do E), pośredniość 3. Otrzymuje z dwóch ścieżek.
- E: stopień wejściowy 1 (od D), stopień wyjściowy 0, pośredniość 1. Węzeł odpływu.
B i D dzielą najwyższą pośredniość (3). B jest rozwidleniem: zasilą dwa węzły. D jest punktem konwergencji: otrzymuje z dwóch ścieżek. Po patchu MOAD-0001 w C, D otrzymuje surge z obu ścieżki B→D i ścieżki C→D jednocześnie.
Obliczanie metryk węzła
Graf zależności: A → B → C → D → E (łańcuch), plus dodatkowa krawędź B → D.
Węzeł C ma zmierzone przyspieszenie 50× po patchu MOAD-0001.
Defekt Flatland
MOAD-0007: Dane przestrzenne zapytane jako lista flat
MOAD-0007 (Defekt Flatland): dane przestrzenne zapytane jako lista flat ignorują geometryczną strukturę danych. Każde zapytanie sprawdza wszystkie N obiektów. O(N) na zapytanie. Z M zapytaniami: O(M × N). W dużej skali: katastrofalne.
Rzeczywisty raytracer sprawdza każdy obiekt w scenie względem każdego promienia. Przy 60 klatkach na sekundę, z 100 promieniami na klatkę i 10 000 obiektami sceny: 60 000 000 testów przecięcia na sekundę. Wszystkie do uniknięcia.
Wgląd geometryczny: przestrzeń ma strukturę. Obiekty skupiają się. Promień, który chybia lewą połowę sceny, chybia każdy obiekt w lewej połowie. Lista flat nie może tego wykorzystać — sprawdza każdy obiekt niezależnie od lokalizacji przestrzennej. Struktura danych przestrzennych może.
BVH: Wyszukiwanie binarne w 3D
Jak działa BVH
BVH (Bounding Volume Hierarchy) rozkłada przestrzeń 3D na drzewo zagnieżdżonych pudełek granicznych. Każdy węzeł wewnętrzny posiada pudełko graniczne, które zawiera całą geometrię swoich dzieci.
Zapytanie raycast:
1. Test pudełka granicznego pierwiastka. Jeśli promień chybia, wyjdź natychmiast — cała scena jest przycięta.
2. Jeśli promień trafia, rekurencja do dzieci. Test pudełka granicznego każdego dziecka.
3. Dla każdego dziecka, które chybia: przetnij to poddrzewo. Dla każdego dziecka, które trafia: rekurencja głębiej.
4. W węzłach liścia: test rzeczywistej geometrii.
Geometria przycinania: na każdym poziomie gałęzie niezachodzące się są eliminowane. Z zrównoważonym BVH o głębokości d: istnieje 2^d węzłów liścia, ale pojedynczy promień potrzebuje co najwyżej O(log N) porównań dla przycietej ścieżki.
To jest ta sama geometryczna logika jak wyszukiwanie binarne: każde porównanie zmniejsza o połowę pozostałą przestrzeń poszukiwań. Wyszukiwanie binarne zmniejsza o połowę posortowaną tablicę. BVH zmniejsza o połowę widoczną przestrzeń 3D. Struktura jest identyczna — zrównoważone drzewo binarne z przycięciem na każdym węźle.
Patch MOAD-0007: zamień listę flat na BVH. Przejdź z O(N) na zapytanie do O(log N) na zapytanie. Przy N=1 024 obiektów, O(log₂ 1 024) = 10 porównań zamiast 1 024.
Obliczanie przyspieszenia BVH
Scena gry ma 1 024 obiektów.
Bez BVH: raycast sprawdza wszystkie 1 024 obiekty.
Z zrównoważonym BVH o głębokości 10 (2^10 = 1 024 liście): raycast przebiega co najwyżej 10 poziomów, z 2 porównaniami dzieci na poziom.