AI 如何打破排序算法的瓶颈？DeepMind 新系统发现提速 70％ 的新方法

排序算法是计算机科学中最基础也最重要的算法之一，它的应用场景无处不在，从在线搜索、社交媒体到云计算、供应链管理等。然而，这种算法经过几十年的发展，已经非常成熟和高效，人们很难再找到更好的改进方式。那么，是否还有可能让排序算法变得更快呢？

答案是肯定的。最近，Google 的子公司 DeepMind 发表了一篇论文，介绍了他们的一个新的 AI 系统——AlphaDev，它能够从最底层的汇编指令开始，自主探索和发现更快的排序算法。这些新算法已经被集成到了 LLVM 标准 C++ 库中，对于较短的序列，排序库的速度提高了 70%，对于超过 25 万个元素的序列，速度提高了约 1.7%。这是十年来对排序库的首次更改，也是通过强化学习设计的算法首次被添加到该库中。

AlphaDev 是基于 DeepMind 之前开发的 AlphaZero 打造的。AlphaZero 是一个强化学习模型，它能够在没有人类指导的情况下，在围棋、国际象棋和象棋等游戏中打败世界冠军。AlphaDev 则展示了这个模型如何从游戏转移到科学挑战，以及从模拟到现实世界的应用。

为了训练 AlphaDev 发现新的算法，DeepMind 的研究员给它设计了一种单人“组装”游戏：只要能够搜索并选择出合适的指令，正确且快速地排好数据，就能获得奖励。但这个游戏的挑战不仅在于搜索空间的大小（可组合指令数相当于宇宙中的粒子数），也在于奖励函数的性质，因为一条错误指令就可能会使整个算法失效。

AlphaDev 拥有两个核心组件：学习算法和表示函数。其中，学习算法主要是在强大的 AlphaZero 上扩展的，它可以结合深度强化学习和随机搜索优化算法来进行巨量的指令搜索；主要的表示函数则基于 Transformer，它能够抓住汇编程序的底层结构，并表示成特殊的序列。随着 AlphaDev 不断地打怪升级，研究员还会限制它能执行的步数，以及待排序列的长度。

最终，AlphaDev 发现了一种全新排序算法：如果序列较短（3-5 个元素），相比人类基准排序算法，它能将速度提高 70%；如果序列长度超过 25 万个元素，则提高 1.7%。具体而言，该算法的创新主要在于两种指令序列：AlphaDev Swap Move（交换移动）和 AlphaDev Copy Move（复制移动）。这些指令序列能够跳过一些不必要的步骤，以一种看似错误但实际上是捷径的方式达成目标。这种新颖的方法让人想起当年 AlphaGo 的“第 37 步”——一种违反直觉的下法却直接击败传奇围棋选手李世石，让观众全都震惊不已。

除了排序算法，AlphaDev 还能够发现更快的哈希算法，这是另一种计算机科学中的基本算法，用于将任意大小的数据映射到固定大小的值。AlphaDev 在 9-16 字节的长度范围内也实现了 30% 的速度提升，并且也已经被集成到了 Abseil 库中，供全球数百万开发人员使用。

DeepMind 的研究员表示，这两种新算法的实现显示 AlphaDev 具有强大的发现原始解决方案的能力，并且将使我们进一步思考计算机领域基础算法的改进方式。不过，由于本次研究中使用的汇编语言具有局限性，他们接下来还是打算尝试 AlphaDev 在高级语言（如 C++）中优化算法的能力。

AI 发现更快排序算法的消息引起了学术界和业界的广泛关注和讨论，有人表示非常兴奋和惊讶，也有人认为 DeepMind 有夸大标题的嫌疑，因为它计算的是算法延迟，而非传统意义上的时间复杂度。不过，无论如何，这项研究都展示了 AI 在提升代码效率方面的巨大潜力，也为未来计算机科学领域带来了新的启示和挑战。

参考

2: https://github.com/abseil/abseil-cpp/pull/1010

3: https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

4: https://www.nature.com/articles/nature24270