Hammings geometriska intuition
Hamming såg geometri överallt
Hammings kap. 9 börjar med en varning: geometrisk intuition kollapsar i höga dimensioner. I 3D fyller en sfär det mesta av sin omslutande kub. I 10D upptar sfären mindre än 0,2% av kubens volym. I 100D rundas fraktionen till noll. Volymen koncentreras nära ytan. Punkter klustras nära hörn, inte i mitten.
Hans felkorrigeringskoder utnyttjade detta direkt. Hammingkoder packar kodord i n-dimensionell binär rymd så att varje kodord omges av en sfär med korrigerbara fel. Geometrin bestämmer hur många fel du kan korrigera. Sfärpackning i n-rum är ett matematikproblem med verkliga konsekvenser: packa sfärerna tätare, korrigera fler fel.
Samma geometriska felläge gäller för algoritmisk komplexitet. Vid små N ser O(N²) och O(N) nästan identiska ut på en graf. Gapet mellan dem verkar hanterbart. Vid stora N exploderar gapet — precis som sfärens volymfraktion kollapsar i höga dimensioner. Vad som känns genomförbart i liten skala blir omöjligt i stor skala.
Formen av varje komplexitetsklass
Rita komplexitet
Varje komplexitetsklass har en geometrisk form:
- O(1): en horisontell linje. Samma kostnad oavsett N. Ingen lutning.
- O(log N): en mjuk uppåtkurva som planar ut. Fördubblas varje gång N kvadreras. Växer proportionellt mot antalet siffror i N.
- O(N): en diagonal linje genom origo. Kostnaden växer proportionellt mot N.
- O(N log N): något brantare diagonal. En linje som kurvor mycket församt uppåt.
- O(N²): en parabel. Vid N=100: 10 000 operationer. Vid N=1 000: 1 000 000 operationer.
Den kritiska insikten: förhållandet mellan två komplexitetsklasser är själv en funktion av N. Vid N=10 kostar O(N²) 10× mer än O(N). Vid N=1 000 kostar O(N²) 1 000× mer. Vid N=1 000 000 kostar det 1 000 000× mer. Gapet växer inte bara — det växer i takt med N själv.
Detta är det geometriska argumentet för varför MOAD-0001-patchar spelar roll. Att flytta en beroendeupplösare från O(N²) till O(N) är inte en konstant acceleration. Vid N=50 000 paket är det en 50 000× acceleration. Vid N=100 000 är det en 100 000× acceleration. Patcharnas värde växer med problemstorleken.
Det växande gapet
O(N²) och O(N) producerar båda korrekta resultat.
Vid N=10: O(N²) kostar 100 operationer, O(N) kostar 10 operationer. Förhållande: 10×.
Vid N=1 000: O(N²) kostar 1 000 000 operationer, O(N) kostar 1 000 operationer.
Grafer som geometri
Den riktade acykliska grafen
En DAG (riktad acyklisk graf) är en geometrisk struktur: noder anslutna av riktade kanter utan cykler. Programvaruberoendegrafer, byggpipeliner och dataflödesarkitekturer bildar alla DAGs.
Varje nod bär geometriska egenskaper mätta genom att räkna dess kanter:
- In-grad: antal kanter som anländer till noden. Högt in-grad betyder många upstream-beroenden matar denna nod.
- Ut-grad: antal kanter som lämnar noden. Högt ut-grad betyder många downstream-konsumenter beror på denna nod.
- Betweenness: in-grad + ut-grad. Mäter hur många vägar som går genom denna nod. En nod med hög betweenness sitter vid en vägskäl i grafen.
- Surge-poäng: acceleration × in-grad. Mäter hur mycket arbete som strömmar downstream när denna flaskhals rensas.
Fabriksmodellen ger dessa geometriska egenskaper fysisk mening:
- Högt betweenness + högt surge-poäng = workaholic-nod. Ta bort denna flaskhals utan att fasadsätta downstream = kollaps.
- Högt ut-grad + lågt surge-poäng = gluttonnod. Konsumerar utan att producera. Maskinen som glömmer att stanna.
Surge & Betweenness i praktiken
Läsa en DAG
Betrakta en 5-nodskedja: A → B → C → D → E, plus en ytterligare kant B → D.
- A: in-grad 0, ut-grad 1, betweenness 1. Källnod. Ingenting matar den. En konsument.
- B: in-grad 1 (från A), ut-grad 2 (till C och till D), betweenness 3. Matar två downstream-noder — en fan-out-punkt.
- C: in-grad 1 (från B), ut-grad 1 (till D), betweenness 2. En genomgångsnod.
- D: in-grad 2 (från B och från C), ut-grad 1 (till E), betweenness 3. Tar emot från två vägar.
- E: in-grad 1 (från D), ut-grad 0, betweenness 1. Sinknod.
B och D delar det högsta betweenness (3). B är fan-out: den matar två noder. D är konverggenspunkten: den tar emot från två vägar. Efter en MOAD-0001-patch på C får D surge från både B→D-vägen och C→D-vägen samtidigt.
Beräkning av nodsmetriker
En beroendegraf: A → B → C → D → E (en kedja), plus en ytterligare kant B → D.
Nod C har en uppmätt acceleration på 50× efter en MOAD-0001-patch.
Flatland-defekten
MOAD-0007: Spatial data som frågats som en platt lista
MOAD-0007 (Flatland-defekten): spatial data som frågats som en platt lista ignorerar den geometriska strukturen för data. Varje fråga kontrollerar alla N objekt. O(N) per fråga. Med M frågor: O(M × N). I stor skala: katastrofalt.
En realtids-raycaster kontrollerar varje objekt i en scen mot varje stråle. Vid 60 bilder per sekund, med 100 strålar per bild och 10 000 scen-objekt: 60 000 000 skärningstestar per sekund. Alla undvikbara.
Den geometriska insikten: utrymme har struktur. Objekt klustras. En stråle som missar den vänstra halvan av scenen missar varje objekt i den vänstra halvan. En platt lista kan inte utnyttja detta — den kontrollerar varje objekt oavsett rumslig plats. En spatial datastruktur kan.
BVH: Binär sökning i 3D
Hur en BVH fungerar
En BVH (Bounding Volume Hierarchy) dekomponerar 3D-utrymme i ett träd av kapslade begränsningsvolymer. Varje internod innehåller en begränsningsvolym som innehåller all dess barns geometri.
En raycast-fråga:
1. Testa rotbegränsningsvolymen. Om strålen missar, avsluta omedelbar — hela scenen är beskuren.
2. Om strålen träffar, rekursera in i barn. Testa varje barns begränsningsvolym.
3. För varje barn som missar: beskär det delträdet. För varje barn som träffar: rekursera djupare.
4. Vid bladnoder: testa den faktiska geometrin.
Geometrin för beskärning: på varje nivå elimineras icke-korsande grenar. Med en balanserad BVH av djup d: 2^d bladnoder finns, men en enda stråle behöver högst O(log N) jämförelser för den beskurna vägen.
Detta är samma geometriska argument som binär sökning: varje jämförelse halverar det återstående sökutrymmet. Binär sökning halverar en sorterad array. En BVH halverar det synliga 3D-rummet. Strukturen är identisk — ett balanserat binärt träd med beskärning vid varje nod.
En MOAD-0007-fix: ersätt den platta listan med en BVH. Flytta från O(N) per fråga till O(log N) per fråga. Vid N=1 024 objekt, O(log₂ 1 024) = 10 jämförelser istället för 1 024.
Beräkning av BVH-acceleration
En spelscen har 1 024 objekt.
Utan en BVH: en raycast kontrollerar alla 1 024 objekt.
Med en balanserad BVH av djup 10 (2^10 = 1 024 blad): en raycast traverserar högst 10 nivåer, med 2 barnjämförelser per nivå.