谷歌 Alpha 家族再添“猛将”：AlphaDev 重磅亮相，打破多年计算瓶颈，新排序算法提速 70%！
上周四，DeepMind 在著名学术刊物 Nature 上，发表了其最新研究成果：一个名为 AlphaDev 的 AI 系统。
从名字上便可以看出，AlphaDev 与 AlphaGo、AlphaFold 一样，同属 DeepMind 旗下的 Alpha 系列，而 AlphaDev 的发布也同样在业界引起了广泛关注。
具体来说，AlphaDev 是一种通过强化学习来发现增强的计算机科学算法的 AI 系统，它发现了一种更快的排序算法，直接超越了科学家和工程师们几十年来的研究，将排序算法的速度提高了 70%！
DeepMind 计算机科学家 Daniel Mankowitz 更是表示：“我们估计，AlphaDev 发现的排序算法和哈希算法每天都会被调用数万亿次。”
不断扩大的计算瓶颈
既然 AlphaDev 发现的是一种全新的排序算法，那我们便先从“排序”说起。
不论是将 3 个字母按字母顺序排列、将 5 个数字从大到小排列，亦或是将一个有上百万条记录的数据库进行排列，这都是排序，是一种几乎所有关键软件的基础算法。在 20 世纪 50 年代之前，排序工作多数都依赖人工，直至后来商业计算机兴起，最早用于排序的计算机科学算法才开始出现并发展。
如今，开发者们所用的排序技术和算法，都是过去几十年计算机科学家和程序员们积累下来的研究成果。相较于几十年前的手动排序，现在的算法确实已经很高效，但也正因如此，想要将其进一步改进无疑是一项重大挑战，难度不亚于“找到一种新的节电方式”或“发现一种更有效的数学方法”。
因此，DeepMind 在论文中提到：“人类的直觉和专业知识对于改进算法至关重要。然而，许多算法已经到了人类专家无法进一步优化它们的阶段，导致计算瓶颈不断扩大。”
打破传统，从汇编指令入手
为了帮助打破这一计算瓶颈，DeepMind 引入了 AlphaDev ：“AlphaDev 不是改进现有算法，而是从头开始发现更快的算法，并从大多数人没想到的地方切入：计算机的汇编指令。”
现在，虽然开发者多用 C++ 等高级编程语言写代码，但为了让计算机理解，还是必须用编译器将其转换为“低级”汇编指令，再由汇编程序将汇编指令转换为计算机可以运行的可执行机器代码。
以此作为灵感，DeepMind 认为相较于在高层次的编码语言中，在汇编指令这个较低的层次上，应该还存在许多改进空间，因为计算机的存储和操作会更灵活，对速度和能源使用也将产生更大影响。
通过玩“游戏”来发现新算法
有了以上基本构思后，DeepMind 让 AlphaDev 开始了一个单人“汇编游戏（Assembly Game）”。
根据论文介绍，在这个游戏中，玩家需要选择一系列低级汇编指令，以此产生一种新的高效排序算法：“这个游戏很有挑战性，因为玩家需要考虑汇编指令的组合空间，以产生一种既可证明正确又快速的算法。难度不仅来自搜索空间的大小，可能的组合数量类似于国际象棋和围棋，而且其中一条不正确的指令都可能会使整个算法无效。”
由于这个特性，AlphaDev 基于 AlphaZero 研发——其强化学习模型在围棋、国际象棋和象棋等游戏中都曾打败世界冠军。
在游戏过程中，AlphaDev 每玩一次 AssemblyGame，都会从头开始构建一个汇编程序，从一组初始无序的指令开始构建，从而定义一种新的高效算法。
随着游戏的进行，算法不断建立，而 AlphaDev 会通过比较算法的输出和预期的结果来检查它是否正确。对于排序算法，AlphaDev 的检验方式是：输入无序的数字后，可否输出正确排序的数字。
DeepMind 将游戏的输赢作为 AlphaDev 的激励方式，而该游戏的输赢也很好判定：
▶ 使用汇编指令，生成正确的低延迟算法，AlphaDev 即赢得游戏。
▶ 生成不正确的算法或正确但低效的算法，AlphaDev 即输掉游戏。
新排序算法，速度提升 70%！
于是，在这样的“游戏”过程中，AlphaDev 发现了更快的排序算法，主要是围绕 3-5 个元素的较短序列的排序算法。
DeepMind 解释道：“因为这些算法是使用最广泛的算法之一，它们经常作为较大排序函数的一部分被多次调用，改进这些算法可以加快对任意数量项目进行排序的整体速度。”
因而，AlphaDev 发现的这个新排序算法，对于较短的序列来说，速度可提升 70%，对于超过 25 万个元素的序列来说，速度也能提高约 1.7%。
为了让更多人用到这个新排序算法，DeepMind 对算法进行了逆向工程，并以此改进了 LLVM libc++ 标准排序库，可供全球数百万开发者和公司使用。DeepMind 计算机科学家 Daniel Mankowitz 激动表示：“这些算法目前位于 C++ 标准排序库中，这是十多年来对这些子例程的首次更改！”
新哈希函数，速度提升 30%！
除了新排序算法，通过研究 AlphaDev 的发现过程，它实际上还创造了一种新方法：其排序算法包含新的指令序列，每次应用时都会跳过一条指令——对于每天都会被使用上万亿次的排序算法来说，这无疑将产生巨大影响。
DeepMind 研究人员将此称作 “AlphaDev 交换和复制动作（AlphaDev swap and copy moves）：通过交换和复制移动，AlphaDev 跳过了一个步骤，以一种看似错误实际上很快捷的方式连接项目。“这显示了 AlphaDev 发现原始解决方案的能力，并挑战了人类改进计算机科学算法的思考方式。”
不仅如此，在发现了新排序算法后，DeepMind 还测试了 AlphaDev 是否可以改进数据结构中常用的哈希算法，结果 AlphaDev 不负众望，确实也发现了一种新的哈希算法，将其应用于 9-16 字节范围内的哈希函数时，速度可提高 30%。而这个新哈希算法，也会在今年被发布到开源的 Abseil 库中，供全球数百万开发者使用。
用 AI 来优化代码的未来
通过以上新发现的排序算法和哈希算法，AlphaDev 已展示出了其概括和发现新算法的能力，即用 AI 来优化世界上的代码，并朝着开发通用 AI 工具迈出了重要一步。
因此对于 AlphaDev 的影响，DeepMind 表达了其最终展望：“我们希望这些发现，能激励研究人员和开发人员创造技术和方法，进一步优化基本算法，以创建一个更强大和可持续的计算生态系统。”
参考链接：
https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms
https://www.nature.com/articles/s41586-023-06004-9
推荐阅读：