哈明的几何直觉
哈明在各处看到几何
哈明的第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时，它的成本是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个子节点比较。