AlphaDev 发现更快的排序算法

新算法将改变计算的基础

数字社会对计算和能源的需求越来越大。在过去的五十年里，我们依靠硬件的改进来跟上需求。但是随着微芯片接近物理极限，改进运行在其上的代码变得至关重要，以使计算更加强大和可持续。对于每天运行数万亿次的代码中的算法来说，这尤为重要。

在我们今天发表在《自然》杂志上的论文中，我们介绍了AlphaDev，一种人工智能系统，它使用强化学习来发现改进的计算机科学算法，超越了科学家和工程师几十年来磨砺出的算法。

AlphaDev发现了一种更快的排序算法，即一种对数据进行排序的方法。数十亿人每天都在使用这些算法而毫不知情。它们支撑着从在线搜索结果和社交帖子的排名到计算机和手机上的数据处理的一切。利用人工智能生成更好的算法将改变我们编程计算机的方式，并影响我们日益数字化的社会的方方面面。

通过在主要的C++库中开源我们的新排序算法，全球数百万开发者和公司现在将其用于云计算、在线购物和供应链管理等各行各业的人工智能应用中。这是对排序库的首次更改，超过十年来首次通过强化学习设计的算法被添加到该库中。我们将其视为使用人工智能逐步优化世界代码的重要里程碑，一次一个算法。

排序是什么？

排序是一种按照特定顺序组织多个项目的方法。例如，将三个字母按字母顺序排列，将五个数字从大到小排列，或对数百万记录的数据库进行排序。

这种方法在历史上发展了很多。早在公元二、三世纪，学者们就在亚历山大图书馆的书架上手工按字母顺序排列了数千本书。工业革命后，出现了可以帮助排序的机器 – 制表机使用打孔卡存储信息，这些卡被用来收集美国1890年的人口普查结果。

随着商用计算机在20世纪50年代的兴起，我们看到了最早的计算机科学排序算法的发展。如今，有许多不同的排序技术和算法在全球范围内的代码库中用于在线组织大量数据。

排序算法的功能示意图。一系列未排序的数字作为输入进入算法，排序后的数字作为输出。

当代算法经过了计算机科学家和程序员数十年的研究才得以发展。它们非常高效，因此要进一步改进是一个巨大的挑战，就像试图找到节约电力的新方法或更高效的数学方法一样。这些算法也是计算机科学的基石，是大学介绍性计算机科学课程的教材。

寻找新算法

AlphaDev通过从零开始而不是改进现有算法来发现更快的算法，并开始寻找大多数人不会考虑的地方：计算机的汇编指令。

汇编指令用于为计算机创建二进制代码。开发人员使用C++等高级编程语言编写代码，然后必须将其转换为计算机能够理解的“低级”汇编指令。

我们相信许多改进存在于这个较低的层次上，而在更高级的编码语言中可能很难发现。在这个层次上，计算机的存储和操作更加灵活，这意味着可能有更多的潜在改进，可能对速度和能源使用有更大的影响。

代码通常是用高级编程语言（如C++）编写的。然后，使用编译器将其转换为称为汇编指令的低级CPU指令。然后，汇编程序将汇编指令转换为可执行的机器代码，供计算机运行。

图A：一个示例C++算法，用于排序最多两个元素。图B：代码的对应汇编表示。 — **图A：**一个示例C++算法，用于排序最多两个元素。图B：代码的对应汇编表示。

使用游戏找到最佳算法

AlphaDev基于AlphaZero开发，它是我们的强化学习模型，在围棋、国际象棋和将棋等游戏中击败了世界冠军。通过AlphaDev，我们展示了该模型如何从游戏转移到科学挑战，以及从模拟到现实世界的应用。

为了训练AlphaDev来发现新的算法，我们将排序转化为一个单人的“汇编游戏”。在每一轮中，AlphaDev观察到它生成的算法以及中央处理单元（CPU）中的信息。然后，它通过选择一条指令添加到算法中来进行一次移动。

汇编游戏非常困难，因为AlphaDev必须高效地搜索大量可能的指令组合，以找到一个能够排序的算法，并且比当前最佳算法更快。可能的指令组合数量类似于宇宙中的粒子数量或国际象棋（10^120局）和围棋（10^700局）中可能的移动组合数量。而且一次错误的移动可能会使整个算法失效。

图A：汇编游戏。玩家AlphaDev接收系统状态st作为输入，并通过选择一条汇编指令添加到到目前为止生成的算法中来进行一次移动。图B：奖励计算。每次移动后，生成的算法会被提供测试输入序列 - 对于sort3来说，这对应于所有三个元素序列的组合。然后，算法生成一个输出，与排序情况下排序序列的预期输出进行比较。代理根据算法的正确性和延迟获得奖励。 — **图A：**汇编游戏。玩家AlphaDev接收系统状态st作为输入，并通过选择一条汇编指令添加到到目前为止生成的算法中来进行一次移动。图B：奖励计算。每次移动后，生成的算法会被提供测试输入序列 – 对于sort3来说，这对应于所有三个元素序列的组合。然后，算法生成一个输出，与排序情况下排序序列的预期输出进行比较。代理根据算法的正确性和延迟获得奖励。

随着算法逐步构建，AlphaDev通过将算法的输出与预期结果进行比较来验证其正确性。对于排序算法来说，这意味着无序的数字作为输入，正确排序的数字作为输出。我们奖励AlphaDev根据其正确排序数字的速度和效率。AlphaDev通过发现一个正确且更快的程序来赢得游戏。

发现更快的排序算法

AlphaDev发现了新的排序算法，使LLVM libc++排序库在较短序列上提速高达70%，在超过250,000个元素的序列上提速约1.7%。

我们专注于改进三至五个元素的短序列的排序算法。这些算法是最广泛使用的，因为它们经常作为较大排序函数的一部分被多次调用。改进这些算法可以加快任意数量项目的排序速度。

为了使新的排序算法对人们更易用，我们对算法进行了逆向工程，并将其转换为C++语言，这是开发人员使用最广泛的编程语言之一。这些算法现在在LLVM libc++标准排序库中可用，被全球数百万开发人员和公司使用。

发现新方法

AlphaDev不仅发现了更快的算法，还揭示了新的方法。它的排序算法包含了一种新的指令序列，每次应用时可以节省一条指令。这对于每天被使用数万亿次的这些算法来说具有巨大的影响。

我们称之为“AlphaDev交换和复制移动”。这种新颖的方法让人想起了AlphaGo的“37号着法”——一种令旁观者震惊的反直觉下法，导致了一位传奇围棋选手的失败。通过交换和复制移动，AlphaDev跳过了一步，以一种看起来像错误但实际上是一种捷径的方式连接物品。这显示了AlphaDev发现原创解决方案的能力，并挑战了我们对于如何改进计算机科学算法的思考方式。

左：使用min(A,B,C)的原始实现。右：AlphaDev交换移动——AlphaDev发现只需要min(A,B)。 — 左：使用min(A,B,C)的原始实现。右：**AlphaDev交换移动——**AlphaDev发现只需要min(A,B)。

左：在一个更大的排序算法中使用max(B, min(A, C, D))的原始实现。右：AlphaDev发现只需要max(B, min(A, C))的复制移动。 — 左：在一个更大的排序算法中使用max(B, min(A, C, D))的原始实现。右：**AlphaDev发现只需要max(B, min(A, C))的复制移动。**

从排序到哈希在数据结构中

在发现更快的排序算法后，我们测试了AlphaDev是否可以普及并改进另一个计算机科学算法：哈希。

哈希是计算中的一种基本算法，用于检索、存储和压缩数据。就像图书管理员使用分类系统来定位特定的书籍一样，哈希算法帮助用户知道他们在寻找什么以及确切地在哪里找到它。这些算法接受特定键（例如用户名称“Jane Doe”）的数据，并将其哈希化，即将原始数据转换为一串唯一的字符（例如1234ghfty）。计算机使用这个哈希值来快速检索与该键相关的数据，而不是搜索所有数据。

我们将AlphaDev应用于数据结构中最常用的哈希算法之一，试图发现更快的算法。当我们将其应用于哈希函数的9-16字节范围时，AlphaDev发现的算法速度提高了30%。

今年，AlphaDev的新哈希算法发布到了开源的Abseil库中，可供全球数百万开发者使用，我们估计它现在每天被使用数万亿次。

优化全球代码，一次一个算法

通过优化和推出全球开发者使用的改进排序和哈希算法，AlphaDev展示了其能够推广和发现具有实际影响的新算法的能力。我们将AlphaDev视为发展通用型AI工具的一步，这些工具可以帮助优化整个计算生态系统并解决将造福社会的其他问题。

虽然在低级汇编指令空间进行优化非常强大，但随着算法的增长，存在一些限制，我们目前正在探索AlphaDev在高级语言（如C++）中直接优化算法的能力，这对于开发者来说更加有用。

AlphaDev的发现，如交换和复制移动，不仅表明它可以改进算法，还能找到新的解决方案。我们希望这些发现能激发研究人员和开发者创造出能进一步优化基本算法的技术和方法，从而创建一个更强大和可持续的计算生态系统。

了解更多关于优化计算生态系统的信息：

阅读我们的案例研究：https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools