一个周六替换掉七个 O(N²) 算法

你的 AI 能写出能跑的代码。让它变成能扩展的代码,才是一个空间运行时真正的胜负手——而这正是 RakuAI 所围绕构建的那份纪律。

智能体擅长写能跑的代码。它们有时不太擅长写能扩展的代码。这是一个我逐渐认出来、也开始为之预留预算的模式:当工单的框架要求一个做 X 的函数时,智能体会写出一个在小输入上正确、但在真实规模的输入上崩溃的函数。

这个周六我特意去找这些函数。找回来了七个。到周六结束时,这七个全都在运行它们真正的生产级算法,而不是智能体最初落地的那些暴力占位实现。

这篇文章讲的是每一个具体是什么,为什么它重要,以及智能体在每一个上面都错在了哪里。

这个模式

这个模式是这样出现的。一个工单被提交。”实现对象 A 和 B 之间的碰撞检测。应该能检测到对象何时重叠。验收标准:一个布尔函数在它们重叠时返回 true,否则返回 false。”

智能体写出了这个函数。这个函数能工作。这个函数是 O(N²) 的暴力实现。对两个对象来说,没问题。对两百个对象来说,也没问题。对两千个对象来说,帧率就没了。

智能体收到的提示没有指明渐进复杂度。智能体满足了这个提示。这个提示没有满足这个引擎。

这是我这边的纪律问题,不是智能体的问题。修复方法是在提示里明确说明复杂度目标,在重要的地方明确指定算法类别,并按固定节奏对这种暴力兜底做审计。这个周六就是这次审计的节奏。

七个具体的替换

我想具体讲讲每一个,因为模式是相同的,而这些教训是层层叠加的。

第一,2D 物理宽相碰撞检测。 原始实现是对每一对对象做双重嵌套循环。每帧 O(N²)。替换成了扫描剪除法(Baraff,1992):按轴对齐包围盒的最小 X 坐标排序,然后扫描一遍。只有当一个盒子的最大 X 大于另一个盒子的最小 X 时,这两个盒子才可能在 X 轴上重叠。排序是 O(N log N);扫描是 O(N + K),其中 K 是实际重叠的对数。对典型场景来说,K 远小于 N²,这正是整个方法的意义所在。

第二,智能体群体子系统的空间碰撞检测。 同样的模式,不同的表面。原始实现是对每个智能体和其他每个智能体做双重嵌套循环检查。替换成了一个空间哈希网格。每个智能体按其所在单元格的坐标进行哈希;碰撞只在同一个或相邻单元格里的智能体之间检查。单元格大小选取为智能体平均半径的大约两倍。期望复杂度 O(N),最坏情况(所有人都在同一个单元格里,正常游玩不会发生)是 O(N²)。哈希函数是 FNV 风格的 3D 坐标哈希。对的去重是通过一个 (min(a,b), max(a,b)) 对的有序 uint64_t 集合实现的。

第三,模型加载器的顶点缓存优化。 原始实现按资产作者指定的顺序把顶点和三角形加载进渲染器。大多数创作工具不会针对 GPU 的顶点缓存做优化,这意味着渲染器要浪费大量周期重新获取它已经拿到过的顶点。替换成了 Tom Forsyth 2006 年的顶点缓存优化:一个大小为 32 的 LRU 缓存模型,通过一个缓存内位置衰减函数加上一个价数加成来给每个候选三角形打分(与许多其他未处理三角形共享顶点的三角形得分更高)。结果是对典型网格拓扑而言接近最优的摊销缓存未命中率。实现的运行时间是 O(T),其中 T 是三角形数量。

第四,视觉特征描述符匹配。 运行时的计算机视觉管线在每一帧都做特征检测,并在连续帧之间匹配特征以实现追踪。原始实现有一个占位实现,直接把固定比例的输入描述符标记为”已匹配”。这个占位实现甚至都算不上暴力实现。它是一个刻意为之的桩。替换是带有 Lowe 比率测试(2004)的真正的暴力描述符匹配。对于 ORB 描述符(二进制),距离度量是通过异或再加上 Kernighan 位计数实现的汉明距离。对于 SIFT 和浮点描述符,距离是 L²。比率测试会拒绝那些最佳候选和次佳候选距离太接近的模糊匹配。比率测试的阈值是 0.75,这是文献中的默认值。复杂度是 O(N₁ × N₂ × D),其中 D 是描述符维度,对 ORB 来说是 32 字节。这在字面意义上确实是暴力实现,但在我们所处理的描述符长度和特征数量上,它足够快,也正是文献中用来做比较的基准。更聪明的近似算法(FLANN、层次化 k-means)已经排进了以后某个周末的队列。

第五,布料物理约束求解器。 原始实现以固定顺序、低迭代次数迭代约束,产生了不收敛的、摇摇晃晃的布料。替换成了一个基于位置的动力学求解器,在迭代之间正确地打乱约束顺序。这种打乱很重要,因为总是以相同顺序处理约束的求解器会产生偏差:布料最终会朝一个方向可预测地拉伸。每次迭代都打乱顺序就消除了这种偏差。为了达到生产质量,迭代次数从 4 提高到了 12,同时为低端设备提供了一个 4 次迭代的快速路径。

第六,人群子系统的 AI 智能体路径规划。 原始实现是一个占位实现,每一步都随机挑选一个有效的邻居。智能体朝随机方向游荡,偶尔靠运气到达目的地。替换成了在导航网格上正确的 A* 路径规划,启发式函数是欧几里得距离,代价函数由地形坡度和地面类型加权。这个实现对开放集使用二叉堆,对关闭集使用哈希集,这使得每一步在堆上的代价是 O(log N),在哈希集上是 O(1)。

第七,跨多个片段的动画混合。 原始实现是一个占位实现,只播放最近请求的那个片段,忽略其他的。替换成了一个正确的加权混合树:每一个输出帧都是各个参与片段每根骨骼变换的加权和,权重由动画作者指定的混合树拓扑驱动。这个混合计算尊重骨骼层级顺序,使得子骨骼能正确继承混合后的父骨骼变换。

我学到了什么

三件事,回头看都不算意外。

在工单里指明算法。 对任何处理非平凡输入规模的函数,工单的框架都必须指明期望的复杂度。”检测 N 个对象之间的碰撞”是不够的。”使用扫描剪除法(Baraff 1992)或等价方法,在最坏情况下以 O(N log N) 检测 N 个对象之间的碰撞”才够。引用文献就是那份纪律。没有它,智能体会写出最容易实现的正确方案,而那往往就是暴力法。

审计是必不可少的。 光靠在 PR 落地时读它们,我是不会抓到这些的。每一个单独的 PR 都是一个能工作的函数,带有能通过的测试。真正让它们浮现出来的,是那种问”找出运行时中每一个 O(N²) 或更差的函数,并评估它是否应该是这样”的审计。把审计加入固定节奏里。

文献就是作弊码。 这些替换里的每一个,都是一个背后有着几十年历史论文支撑的已发表算法。Baraff 1992。Forsyth 2006。Lowe 2004。基于位置的动力学。A*。这些都不是什么新东西。只要你告诉智能体该读哪篇论文,它就会写出与文献等价的版本。

合作伙伴和开发者应该从中获得什么

如果你正在为合作评估一个引擎,而这个团队还没有对他们的代码库做过算法审计,让他们做一次。审计会揭露出一些东西。这个团队对揭露出来的东西的反应,比任何功能列表都更能说明问题。

如果你在一个对性能敏感的代码库上运行智能体驱动的工作流,审计不是可选项。智能体会落地能工作的代码。这些能工作的代码有时会是暴力版本。审计就是你发现是哪一种的方式。

如果你是一个正在为性能敏感工作构建编码智能体的 AI 实验室,我会去优化的指标是”当智能体在实现一个名字暗示了扩展性关注的函数时,它是否会去问渐进复杂度”。大多数智能体不会。会这么做的那些,产出的是更好的代码。

周六下午。七个暴力算法被替换成了它们真正的生产级版本。引擎变快了。代码库变得更诚实了。

回去继续构建。