AlphaDev发现更快的排序算法

发布日期：2023年6月7日
作者：Daniel J. Mankowitz 与 Andrea Michi

数字社会对计算能力和能源消耗的需求持续增长。过去五十年间，人们依靠硬件改进来满足需求，但随着微芯片逼近物理极限，改进运行其上的代码变得至关重要，尤其是那些每日运行数万亿次的基础算法。

在发表于《自然》期刊的最新研究中，某机构团队推出人工智能系统AlphaDev。该系统通过强化学习发现了更高效的计算机科学算法，其性能超越了科学家和工程师数十年打磨的成果。

AlphaDev发现了更快的排序算法（一种数据整理方法）。全球数十亿人日常使用这些算法却未察觉——从搜索引擎结果排序、社交媒体推文展示到手机数据处理都依赖于此。通过AI生成更优算法将彻底改变编程方式，并影响日益数字化的社会各个层面。

新排序算法已在主流C++库中开源，全球数百万开发者和企业将其应用于云计算、电子商务和供应链管理等领域的AI应用。这是该排序库十余年来首次更新，也是首次通过强化学习设计的算法被纳入。这被视为用AI优化全球代码的重要里程碑。

什么是排序？

排序是将项目按特定顺序组织的方法，例如将三个字母按字母表排列、将五个数字从大到小排序，或整理包含数百万条记录的数据库。排序方法历经演变：从公元前2-3世纪亚历山大图书馆学者手动整理书籍，到工业革命后用于处理1890年美国人口普查结果的打孔卡排序机，再到1950年代商用计算机兴起时最早出现的计算机排序算法。如今，全球代码库使用多种排序技术处理海量在线数据。

从零开始寻找新算法

AlphaDev通过从零构建而非优化现有算法来发现更快的算法，其探索领域多数人类不会涉足：计算机汇编指令。汇编指令用于生成计算机执行的二进制代码。开发者用C++等高级语言编写代码后，需将其翻译为低级汇编指令才能被计算机理解。

在低级层面存在许多难以通过高级编程语言发现的优化空间。计算机存储和操作在此层级更加灵活，意味着潜在改进更多，可能对速度和能效产生更大影响。

通过游戏寻找最优算法

AlphaDev基于曾击败围棋、国际象棋世界冠军的强化学习模型AlphaZero构建。研究表明，该模型可从游戏迁移至科学挑战，从模拟应用至现实场景。

为训练AlphaDev发现新算法，团队将排序转化为单人“汇编游戏”。每轮中，AlphaDev观察已生成的算法及中央处理器（CPU）中的信息，然后选择指令添加到算法中。汇编游戏难度极高，因为AlphaDev需高效搜索巨量指令组合（数量级相当于宇宙粒子数或棋类游戏可能步数），以找到正确且更快的算法。单步错误即可导致整个算法失效。

算法构建过程中，AlphaDev通过对比输出与预期结果来验证正确性。对于排序算法，即输入无序数字后输出正确排序结果。系统根据排序正确性、速度与效率给予奖励，AlphaDev通过发现正确且更快的程序赢得游戏。

发现更快的排序算法

AlphaDev发现的新排序算法使LLVM libc++排序库性能提升：短序列排序速度快70%，超过25万个元素的序列速度快1.7%。研究重点优化了3-5个元素的短序列排序算法，这些算法因常被大型排序函数频繁调用而广泛使用，其改进可提升任意数量项目的整体排序速度。

为使新算法更易使用，团队将算法反向工程并翻译为开发者最常用的C++语言。这些算法现已加入LLVM libc++标准排序库，供全球数百万开发者使用。

发现新颖方法

AlphaDev不仅找到更快算法，还发现了新颖方法。其排序算法包含新的指令序列，每次应用可节省一条指令。由于这些算法每日被调用数万亿次，微小改进即可产生巨大影响。

这种方法被称为“AlphaDev交换与复制操作”，其创新性令人联想到AlphaGo的“第37步”——一种反直觉的落子方式，曾击败传奇围棋选手。通过交换与复制操作，AlphaDev跳过步骤以看似错误实为捷径的方式连接项目，这展示了其发现原创解决方案的能力，并挑战了改进计算机科学算法的传统思路。

从排序到数据结构散列

发现更快排序算法后，团队测试AlphaDev能否推广至改进其他计算机科学算法：散列。散列是计算中用于检索、存储和压缩数据的基础算法，就像图书管理员使用分类系统定位书籍一样。散列算法将特定键（如用户名“Jane Doe”）转换为唯一字符串（如1234ghfty），计算机借此快速检索数据而非搜索全部数据。

团队将AlphaDev应用于数据结构中最常用的散列算法，尝试发现更快的算法。当应用于9-16字节范围的散列函数时，AlphaDev发现的算法速度快30%。今年，新散列算法已发布至开源Abseil库，预计每日被调用数万亿次。

一次优化一个算法，改变世界代码

通过优化并推广全球开发者使用的排序和散列算法，AlphaDev证明了其发现具有现实影响的新算法的泛化能力。这标志着向开发通用AI工具迈出重要一步，未来可能优化整个计算生态系统并解决其他社会性问题。

尽管在低级汇编指令层面的优化非常强大，但随着算法增长存在局限性。团队正在探索AlphaDev直接优化C++等高级语言算法的能力，这将为开发者提供更大价值。

AlphaDev的发现（如交换与复制操作）不仅表明其可改进算法，还能找到新解决方案。希望这些发现能激励研究者和开发者创建新技术与方法，进一步优化基础算法，构建更强大、可持续的计算生态系统。

致谢：（略）
相关工作：研究团队曾开发用于发现基础算法的人工智能系统AlphaTensor（2022年10月）以及解决竞争性编程问题的AlphaCode（2022年12月）。