哈明的幾何直覺
哈明看到無處不在的幾何
哈明第9章開篇的警告：高維空間中的幾何直覺會崩潰。在3維中，球體占據其外層立方體體積的大部分。在10維中，球體只占立方體體積的不足0.2%。在100維中，這個比例會接近零。體積集中在表面附近。點聚集在角落，而非中心。
他的糾錯碼直接利用了這一點。哈明碼將碼字堆積到n維二進制空間中，使得每個碼字都被一個可糾正錯誤的球體包圍。幾何結構決定了你能糾正多少個錯誤。n維空間中的球堆積是一個有實際應用的數學問題：更緊密地堆積球體，就能糾正更多錯誤。
同樣的幾何失效模式也適用於演算法複雜度。在小的N值下，O(N²)和O(N)在圖表上看起來幾乎相同。它們之間的差距似乎是可以接受的。在大的N值下，差距會爆炸式增長——正如球體的體積分數在高維空間中崩潰一樣。在小規模時感覺可行的東西在規模擴大時變得不可能。
每個複雜度類的形狀
繪製複雜度
每個複雜度類都有一個幾何形狀：
- O(1)： 一條水平線。無論N是多少，成本都相同。沒有斜率。
- O(log N)： 一條向上的溫和曲線，逐漸變平。每當N平方時就翻倍。增長的比例與N中的位數成正比。
- O(N)： 通過原點的對角線。成本與N成正比增長。
- O(N log N)： 略陡的對角線。一條非常輕微向上彎曲的線。
- O(N²)： 一條拋物線。在N=100時：10,000次操作。在N=1,000時：1,000,000次操作。
關鍵的洞察：兩個複雜度類之間的比率本身是N的函數。 在N=10時，O(N²)的成本比O(N)多10倍。在N=1,000時，O(N²)的成本比O(N)多1,000倍。在N=1,000,000時，它的成本比O(N)多1,000,000倍。差距不僅在增長，它以N的速率增長。
這就是MOAD-0001補丁重要的幾何論證。將依賴關係解析器從O(N²)移動到O(N)不是一個恆定的加速。在N=50,000個包時，這是一個50,000倍的加速。在N=100,000時，這是一個100,000倍的加速。補丁的價值隨著問題大小而增長。
差距的擴大
O(N²)和O(N)都產生正確的結果。
在N=10時：O(N²)花費100次操作，O(N)花費10次操作。比率：10倍。
在N=1,000時：O(N²)花費1,000,000次操作，O(N)花費1,000次操作。
圖作為幾何
有向無環圖
DAG（有向無環圖）是一個幾何結構：由有向邊連接的節點，沒有迴圈。軟體依賴圖、構建管道和數據流架構都形成DAG。
每個節點都帶有通過邊計數測量的幾何性質：
- 入度： 到達節點的邊數。高入度意味著許多上游依賴項流向此節點。
- 出度： 離開節點的邊數。高出度意味著許多下游消費者依賴此節點。
- 中介性： 入度+出度。測量有多少條路徑通過此節點。高中介性節點位於圖中的十字路口。
- 激增評分： 加速比×入度。測量當此瓶頸清除時有多少工作會流向下游。
工廠模型給了這些幾何性質物理意義：
- 高中介性+高激增評分=工作狂節點。在沒有準備下游的情況下移除此瓶頸=崩潰。
- 高出度+低激增評分=貪心節點。消費而不生產。那個忘記停止的機器。
實踐中的激增和中介性
讀取DAG
考慮一個5節點的鏈：A → B → C → D → E，加上一條額外的邊B → D。
- A：入度0，出度1，中介性1。源節點。沒有東西流入它。一個消費者。
- B：入度1（來自A），出度2（到C和D），中介性3。流向兩個下游節點——一個分流點。
- C：入度1（來自B），出度1（到D），中介性2。一個通過節點。
- D：入度2（來自B和C），出度1（到E），中介性3。從兩條路徑接收。
- E：入度1（來自D），出度0，中介性1。匯聚節點。
B和D共享最高的中介性（3）。B是分流點：它流向兩個節點。D是匯聚點：它從兩條路徑接收。在C進行MOAD-0001補丁後，D同時從B→D路徑和C→D路徑接收激增。
計算節點指標
一個依賴圖：A → B → C → D → E（一條鏈），加上額外的邊B → D。
節點C在MOAD-0001補丁後測得的加速是50倍。
平面缺陷
MOAD-0007：作為扁平列表查詢的空間數據
MOAD-0007（平面缺陷）：作為扁平列表查詢的空間數據忽視了數據的幾何結構。每個查詢檢查所有N個對象。O(N)每個查詢。有M個查詢：O(M × N)。在規模上：災難性的。
實時光線投射機檢查場景中的每個對象對抗每條射線。在每秒60幀，每幀100條射線，場景中10,000個對象：每秒60,000,000次交集測試。全部都是可以避免的。
幾何洞察：空間有結構。對象聚集。一條射線如果錯過場景的左半部分就錯過了左半部分的每個對象。扁平列表無法利用這一點——無論空間位置如何，它都檢查每個對象。空間數據結構可以。
BVH：3D中的二分查找
BVH如何工作
BVH（邊界體積層級結構）將3D空間分解為嵌套邊界框的樹。每個內部節點持有一個邊界框，包含其所有子節點的幾何。
光線投射查詢：
1. 測試根邊界框。如果射線錯過，立即退出——整個場景被修剪。
2. 如果射線擊中，遞歸進入子節點。測試每個子節點的邊界框。
3. 對於每個錯過的子節點：修剪該子樹。對於每個擊中的子節點：遞歸更深。
4. 在葉節點：測試實際幾何。
修剪的幾何： 在每一級，不相交的分支被消除。使用深度為d的平衡BVH：存在2^d個葉節點，但單條射線最多需要O(log N)次比較以沿著修剪的路徑。
這與二分查找的幾何論證相同：每次比較將剩餘的搜索空間減半。二分查找減半一個排序數組。BVH減半可見的3D空間。結構相同——一個具有在每個節點修剪的平衡二叉樹。
MOAD-0007修復：用BVH替換扁平列表。從O(N)每個查詢移動到O(log N)每個查詢。在N=1,024個對象時，O(log₂ 1,024)=10次比較而非1,024次。
計算BVH加速
一個遊戲場景有1,024個對象。
沒有BVH：光線投射檢查所有1,024個對象。
使用深度為10的平衡BVH（2^10=1,024葉子）：光線投射最多遍歷10個級別，每個級別2次子節點比較。