汉明的几何直觉
汉明在任何地方都能看到几何
汉明的第9章开头警告：在高维空间，几何直觉会崩溃。3D时，一个球体几乎占据了它所包含的立方体的全部空间。在10D时，球体所占的体积小于0.2%。在100D时，体积约为零。体积集中在表面附近。点聚集在角落，而不是中心。
他误差校正的代码直接利用了这一点。汉明码将码字放入n维二进制空间中，使得每个码字都被正确的错误包围在一个球体中。几何决定了可以纠正的错误数量。n空间中的球packing是一个实际问题：密度更高的球packing，纠正更多的错误。
同样的几何失败模式也适用于算法复杂性。在小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操作。
![/static/diagrams/unhamming_complexity_curves.svg]
关键见解：两个复杂性类别之间的比率本身就是一个函数N。 N=10时，O(N²)的成本比O(N)多10倍。N=1,000时，O(N²)的成本比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。
每个节点都具有几何属性，通过计算其边数来衡量：
- 入度：到达节点的边数。高入度意味着许多上游依赖项为此节点提供输入。
- 出度：离开节点的边数。高出度意味着许多下游消费者依赖于此节点。
- 介于…之间：入度 + 出度。衡量通过此节点的路径数量。介于…之间的节点在图中位于十字路口。
- 峰值分数：速度提升 × 入度。衡量当这个瓶颈消失时，下游工作量的增长。
工厂模型为这些几何属性赋予了物理意义:
- 高的之间度 + 高的冲刺分数 = 工作狂节点。没有在下游进行预先部署的情况下，移除这个瓶颈 = 崩溃。
- 高的出度 + 低的冲刺分数 = 狼烟点。消耗而不生产。忘记停止的机器。
冲刺与之间度实践
阅读有向图
考虑一个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) per 查询。有 M 个查询：O(M × N)。在大规模情况下：灾难性。
一个实时光线_caster_会将每个对象与每条光线进行检查。在每秒 60 帧的情况下，具有每帧 100 条光线和 10,000 个场景对象：每秒 60,000,000 次交叉测试。所有这些都可以避免。
几何见解：空间具有结构。对象会聚集。光线在场景的左半部分 misses_，则在左半部分的所有对象都 misses_。一个平面列表无法利用这一点——它会无论空间位置如何检查每个对象。一个空间数据结构可以。
BVH：3D 的二分搜索
BVH 是如何工作的
BVH（Bounding Volume Hierarchy）将 3D 空间分解为一个包含嵌套的 bounding boxes_的树。每个内部节点都包含其子节点的所有几何体的 bounding box_。
光线_cast_查询：
1. 测试根 bounding box_。如果光线 misses_，立即退出——整个场景都被修剪了。
2. 如果光线 hits_，递归进入子节点。测试每个子节点的 bounding box_。
3. 对于每个 misses_的子节点：修剪子树。对于每个 hits_的子节点：递归更深。
4. 在叶节点：测试实际几何体。
修剪的几何：在每个级别上，non-intersecting_分支将被消除。具有平衡 BVH 的深度 d：2^d 个叶节点存在，但一个单独的光线需要最多 O(log N) 的比较以获取修剪路径。
这与二分搜索的几何原理相同：每个比较都会将剩余搜索空间减半。二分搜索会将已排序的数组减半。一个 BVH 会将 3D 空间减半。结构本质上相同——一个平衡的二叉树，具有在每个节点进行修剪的特性。
一个 MOAD-0007 修复：将平面列表替换为 BVH。从 O(N) per 查询转换为 O(log N) per 查询。在 N = 1,024 个对象的情况下，O(log₂ 1,024) = 10 个比较，而不是 1,024。
计算 BVH 加速比
一个游戏场景有 1024 个对象。
没有 BVH：光线检测需要检查所有 1024 个对象。
有一个平衡的 BVH 深度为 10（2^10 = 1024 叶子）：光线检测最多遍历 10 个级别，每个级别最多 2 个子比较。