Hammings geometrische Intuition
Hamming sah Geometrie überall
In Hammings Kapitel 9 beginnt mit einer Warnung: geometrische Intuition bricht in hohen Dimensionen zusammen. In 3D füllt eine Kugel den Großteil des umschließenden Würfels aus. In 10D nimmt die Kugel weniger als 0,2 % des Würfelvolumens ein. In 100D rundet der Bruch gegen Null. Das Volumen konzentriert sich an der Oberfläche. Punkte häufen sich in den Ecken, nicht im Zentrum.
Seine Fehlerkorrekturcodes nutzten dies direkt aus. Hamming-Codes packen Codewörter in n-dimensionalen binären Raum, so dass jedes Codewort von einer Sphäre korrigierbarer Fehler umgeben ist. Die Geometrie bestimmt, wie viele Fehler Sie korrigieren können. Kugelpackung in n-dimensionalen Raum ist ein Mathe-Problem mit echten Konsequenzen: Packen Sie die Kugeln dichter, korrigieren Sie mehr Fehler.
Der gleiche geometrische Fehlermodus gilt für algorithmische Komplexität. Bei kleinen N sehen O(N²) und O(N) auf einem Graphen nahezu identisch aus. Die Lücke zwischen ihnen scheint bewältigbar zu sein. Bei großen N explodiert die Lücke – genau wie der Volumenanteil der Kugel in hohen Dimensionen zusammenbricht. Was sich in kleinem Maßstab beherrschbar anfühlt, wird im großen Maßstab unmöglich.
Die Form jeder Komplexitätsklasse
Komplexität zeichnen
Jede Komplexitätsklasse hat eine geometrische Form:
- O(1): eine horizontale Linie. Gleiche Kosten unabhängig von N. Keine Steigung.
- O(log N): eine sanfte nach oben gehende Kurve, die sich abflacht. Verdoppelt sich jedes Mal, wenn N quadriert wird. Wächst proportional zur Anzahl der Ziffern in N.
- O(N): eine Diagonallinie durch den Ursprung. Die Kosten wachsen proportional zu N.
- O(N log N): etwas steilere Diagonale. Eine Linie, die sich sehr sanft nach oben krümmt.
- O(N²): eine Parabel. Bei N=100: 10.000 Operationen. Bei N=1.000: 1.000.000 Operationen.
Die kritische Erkenntnis: das Verhältnis zwischen zwei Komplexitätsklassen ist selbst eine Funktion von N. Bei N=10 kostet O(N²) das 10-fache von O(N). Bei N=1.000 kostet O(N²) das 1.000-fache. Bei N=1.000.000 kostet es das 1.000.000-fache. Die Lücke wächst nicht nur – sie wächst mit der Rate von N selbst.
Dies ist das geometrische Argument dafür, warum MOAD-0001-Patches wichtig sind. Das Verschieben eines Abhängigkeitslösers von O(N²) zu O(N) ist keine konstante Beschleunigung. Bei N=50.000 Paketen ist es eine 50.000×-Beschleunigung. Bei N=100.000 ist es eine 100.000×-Beschleunigung. Der Wert des Patches wächst mit der Problemgröße.
Die wachsende Lücke
O(N²) und O(N) produzieren beide korrekte Ergebnisse.
Bei N=10: O(N²) kostet 100 Operationen, O(N) kostet 10 Operationen. Verhältnis: 10×.
Bei N=1.000: O(N²) kostet 1.000.000 Operationen, O(N) kostet 1.000 Operationen.
Graphen als Geometrie
Der gerichtete azyklische Graph
Ein DAG (gerichteter azyklischer Graph) ist eine geometrische Struktur: Knoten, die durch gerichtete Kanten ohne Zyklen verbunden sind. Softwareabhängigkeitsgraphen, Build-Pipelines und Datenflussarchitekturen bilden alle DAGs.
Jeder Knoten trägt geometrische Eigenschaften, die durch das Zählen seiner Kanten gemessen werden:
- In-Grad: Anzahl der Kanten, die beim Knoten ankommen. Ein hoher In-Grad bedeutet, dass viele vorgelagerte Abhängigkeiten diesen Knoten speisen.
- Out-Grad: Anzahl der Kanten, die vom Knoten ausgehen. Ein hoher Out-Grad bedeutet, dass viele nachgelagerte Verbraucher von diesem Knoten abhängen.
- Betweenness: In-Grad + Out-Grad. Misst, wie viele Pfade durch diesen Knoten verlaufen. Ein Knoten mit hohem Betweenness sitzt an einer Kreuzung im Graphen.
- Surge-Score: Beschleunigung × In-Grad. Misst, wie viel Arbeit sich ansammelt, wenn dieser Engpass behoben wird.
Das Fabrikmodell verleiht diesen geometrischen Eigenschaften physikalische Bedeutung:
- Hoher Betweenness + hoher Surge-Score = Workaholic-Knoten. Entfernen Sie diesen Engpass ohne nachgelagerte Pufferung = Zusammenbruch.
- Hoher Out-Grad + niedriger Surge-Score = Glutton-Knoten. Verbraucht ohne zu produzieren. Die Maschine, die vergisst zu stoppen.
Surge & Betweenness in der Praxis
Ein DAG lesen
Betrachten Sie eine Kette mit 5 Knoten: A → B → C → D → E, plus eine zusätzliche Kante B → D.
- A: In-Grad 0, Out-Grad 1, Betweenness 1. Quellknoten. Nichts speist ihn. Ein Verbraucher.
- B: In-Grad 1 (von A), Out-Grad 2 (zu C und zu D), Betweenness 3. Speist zwei nachgelagerte Knoten – ein Fan-out-Punkt.
- C: In-Grad 1 (von B), Out-Grad 1 (zu D), Betweenness 2. Ein Durchgangsknoten.
- D: In-Grad 2 (von B und von C), Out-Grad 1 (zu E), Betweenness 3. Empfängt von zwei Pfaden.
- E: In-Grad 1 (von D), Out-Grad 0, Betweenness 1. Senkenknoten.
B und D teilen sich den höchsten Betweenness (3). B ist der Fan-out: er speist zwei Knoten. D ist der Konvergenzpunkt: er empfängt von zwei Pfaden. Nach einem MOAD-0001-Patch bei C empfängt D einen Surge von sowohl dem B→D-Pfad als auch dem C→D-Pfad gleichzeitig.
Berechnung von Knotenmetriken
Ein Abhängigkeitsgraph: A → B → C → D → E (eine Kette), plus eine zusätzliche Kante B → D.
Knoten C hat nach einem MOAD-0001-Patch eine gemessene Beschleunigung von 50×.
Der Flatland-Defekt
MOAD-0007: Räumliche Daten als flache Liste abgefragt
MOAD-0007 (der Flatland-Defekt): Räumliche Daten, die als flache Liste abgefragt werden, ignorieren die geometrische Struktur der Daten. Jede Abfrage prüft alle N Objekte. O(N) pro Abfrage. Mit M Abfragen: O(M × N). Im großen Maßstab: katastrophal.
Ein Echtzeit-Raycaster überprüft jedes Objekt in einer Szene gegen jeden Strahl. Bei 60 Bildern pro Sekunde mit 100 Strahlen pro Bild und 10.000 Szenenobjekten: 60.000.000 Schnittest pro Sekunde. Alle sind vermeidbar.
Die geometrische Erkenntnis: Der Raum hat Struktur. Objekte bilden Cluster. Ein Strahl, der die linke Hälfte der Szene verfehlt, verfehlt jedes Objekt in der linken Hälfte. Eine flache Liste kann dies nicht nutzen – sie prüft jedes Objekt, unabhängig vom räumlichen Ort. Eine Raumondatenstruktur kann.
Die BVH: Binärsuche in 3D
So funktioniert eine BVH
Eine BVH (Bounding Volume Hierarchy) zerlegt den 3D-Raum in einen Baum verschachtelter Begrenzungskästen. Jeder interne Knoten hält einen Begrenzungskasten, der die gesamte Geometrie seiner Kinder enthält.
Eine Raycast-Abfrage:
1. Testen Sie den Wurzelbegrenzungskasten. Wenn der Strahl verfehlt wird, beenden Sie sofort – die gesamte Szene wird beschnitten.
2. Wenn der Strahl trifft, rekursieren Sie in die Kinder. Testen Sie jeden Kinderbegrenzungskasten.
3. Für jedes Kind, das verfehlt wird: Beschneiden Sie diesen Teilbaum. Für jedes Kind, das trifft: Rekursieren Sie tiefer.
4. Bei Blattknoten: Testen Sie die tatsächliche Geometrie.
Geometrie des Beschneidens: Auf jeder Ebene werden sich nicht schneidende Äste entfernt. Mit einer balancierten BVH der Tiefe d: Es gibt 2^d Blattknoten, aber ein einzelner Strahl benötigt höchstens O(log N) Vergleiche für den beschnittenen Pfad.
Dies ist das gleiche geometrische Argument wie die Binärsuche: Jeder Vergleich halbiert den verbleibenden Suchraum. Eine Binärsuche halbiert ein sortiertes Array. Eine BVH halbiert den sichtbaren 3D-Raum. Die Struktur ist identisch – ein ausbalancierter binärer Baum mit Beschneiden auf jedem Knoten.
Eine MOAD-0007-Behebung: Ersetzen Sie die flache Liste durch eine BVH. Wechseln Sie von O(N) pro Abfrage zu O(log N) pro Abfrage. Bei N=1.024 Objekten O(log₂ 1.024) = 10 Vergleiche statt 1.024.
Berechnung der BVH-Beschleunigung
Eine Spielszene hat 1.024 Objekte.
Ohne eine BVH: ein Raycast prüft alle 1.024 Objekte.
Mit einer balancierten BVH der Tiefe 10 (2^10 = 1.024 Blätter): Ein Raycast durchläuft höchstens 10 Ebenen, mit 2 Kindvergleichen pro Ebene.