ハミングの幾何学的直感
ハミングはあらゆる場所に幾何学を見出した
ハミングの第9章は警告で始まります：幾何学的直感は高次元で崩壊します。3Dでは、球体は外側の立方体のほとんどを満たします。10Dでは、球体は立方体の体積の0.2%未満を占めます。100Dでは、その割合はゼロに丸められます。体積は表面付近に集中します。点はコーナー付近に集まり、中心ではありません。
彼の誤り訂正コードは、これを直接利用しました。ハミング符号は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操作。
重要な洞察：2つの複雑性クラス間の比率は、それ自体Nの関数です。 N=10では、O(N²)はO(N)より10倍コストがかかります。N=1,000では、O(N²)は1,000倍コストがかかります。N=1,000,000では、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を形成します。
各ノードは、そのエッジをカウントすることで測定される幾何学的性質を持ちます：
- In-degree（入度）： ノードに到達するエッジの数。高いIn-degreeは、多くの上流の依存関係がこのノードをフィードすることを意味します。
- Out-degree（出度）： ノードを離れるエッジの数。高いOut-degreeは、多くの下流のコンシューマーがこのノードに依存することを意味します。
- Betweenness（媒介中心性）： In-degree + Out-degree。このノードを通過する経路の数を測定します。高いBetweennessノードはグラフの交差点に位置しています。
- Surge score（サージスコア）： speedup × In-degree。このボトルネックが解消されたときに下流にどの程度の作業が流入するかを測定します。
工場モデルはこれらの幾何学的性質に物理的な意味を与えます：
- 高いBetweenness +高いSurge score =ワーカホリックノード。このボトルネックを下流をステージングせずに削除する=崩壊。
- 高いOut-degree +低いSurge score =グルトンノード。生産なしに消費します。停止を忘れた機械。
実践におけるサージと媒介中心性
DAGの読み方
5ノードチェーンを考えてください：A → B → C → D → E、さらに追加エッジB → D。
- A：In-degree 0、Out-degree 1、Betweenness 1。ソースノード。何もフィードしません。1つのコンシューマー。
- B：In-degree 1（A から）、Out-degree 2（C と D へ）、Betweenness 3。2つの下流ノードをフィード—ファンアウトポイント。
- C：In-degree 1（B から）、Out-degree 1（D へ）、Betweenness 2。パススルーノード。
- D：In-degree 2（B と C から）、Out-degree 1（E へ）、Betweenness 3。2つのパスから受け取ります。
- E：In-degree 1（D から）、Out-degree 0、Betweenness 1。シンクノード。
BとDは最も高いBetweennessを共有しています（3）。Bはファンアウトです：2つのノードをフィードします。Dは収束ポイントです：2つのパスから受け取ります。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）。規模で：壊滅的。
リアルタイムレイキャスターはシーン内のすべてのオブジェクトをすべてのレイに対してチェックします。1秒あたり60フレーム、フレームあたり100本のレイ、10,000個のシーンオブジェクト：1秒あたり60,000,000個の交差テスト。すべて避けられます。
幾何学的な洞察：空間は構造を持っています。オブジェクトは集まります。シーンの左半分を逃すレイは、左半分のすべてのオブジェクトを逃します。フラットリストはこれを利用できません—空間位置に関係なくすべてのオブジェクトをチェックします。空間データ構造はできます。
BVH：3Dにおける二分探索
BVHの仕組み
BVH（Bounding Volume Hierarchy）は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）= 1,024の代わりに10の比較です。
BVHスピードアップの計算
ゲームシーンには1,024個のオブジェクトがあります。
BVHなし：レイキャストはすべての1,024オブジェクトをチェックします。
深さ10の均衡したBVHを使用：（2^10 = 1,024葉）：レイキャストは最大10レベルを通過します、レベルあたり2つの子比較です。