DeepMind推惊世排序算法，C++库忙更新！

点击参加51CTO网站内容调查问卷

编译 | 王瑞平、言征

AlphaGo又有“小弟”加入了!

谷歌DeepMind把Alpha系列“卷”到了排序算法上，重磅推出AlphaDev。

它好比一种“开发秘法”，通过使用强化学习AI发现排序算法和散列算法，强行把人类程序员设计的算法分别提速约70%和30%。

研究成果一经推出，瞬间点燃软件圈！一下子，全球数以百万计的软件运行速度飙升，直接超越了科学家和工程师几十年来的成果，十年未更新的LLVM标准C++库都更新了。

（来源：Nature）

这也是继谷歌两AI部门合体后推出的颠覆性技术。论文以《使用深度强化学习模型发现更快排序算法》（Faster sorting algorithms discovered using deep reinforcement learning）为题发表于Nature。DeepMind计算机科学家Daniel Mankowitz为论文的第一作者。

1、演进：排序算法的由来

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

排序法最早可追溯至二到三世纪，仍在不断演进。最初，学者们徒手将亚历山大图书馆书架上的数千本书按字母顺序进行排序。

工业革命之后，人们发明了可自行分类的机器，即，将信息存储在穿孔卡片上的制表机器中，用于收集1890年美国人口普查的结果。

20世纪50年代，商用计算机开始兴起，也随即产生了排序算法。将一系列未排序的数字输入到排序算法中，它就能输出排好顺序的数字。

如今，在世界各地的代码库中，仍有许多不同的排序技术和算法被用于在线整理大量数据。      

这些排序算法经过计算机科学家和程序员几十年的研究开发，变得越来越高效。但是，对其进一步改进仍具有重大挑战。

2、重头戏：如何用AlphaDev生成新排序算法？

研究人员最初用AlphaDev生成新算法的目的是高效率完成给定任务。

在这个实验中，AlphaDev是从零开始构建新算法的，并不是根据以往算法构建，属于原创。在此过程中，它应用了汇编代码的中间语言。该语言更接近计算机二进制指令，也更容易让AlphaDev创造出高效算法。

具体来讲，AlphaDev每次生成一个指令，然后测试其输出正确与否，同时还在模型中设定要求生成最短算法。

当被要求重新设计排序算法时，AlphaDev随机生成比现有算法快70%的新排序算法，可同时将五个数据排序。在对25万个数据进行排序时，它也比最好的算法快1.7%。

由于排序算法被广泛用于各种常用软件中，这项创新会对全球算法产生重大影响。DeepMind已将它们进行开源，并加入Libc++常用代码库。

据DeepMind的研究者描述：“由于指令组合数量庞大，看似简单的研究过程难度极大。”

3、缘起：在玩游戏中找到最佳算法  

进一步来讲，AlphaDev是基于AlphaZero产生的更先进模型。而AlphaZero此前是DeepMind的强化学习模型，曾在围棋、国际象棋和其它棋类游戏中击败了世界冠军。

通过此项实验，新模型AlphaDev发挥出从玩游戏转移到解决科学问题以及从实验模拟转移到现实世界应用的独特优势。

为训练AlphaDev发现新算法，研究者将排序模拟为单人“组装游戏”。在每个游戏回合中，AlphaDev都能观察到生成的算法和包含在CPU中的信息，然后选择一条指令添加到算法中走出每一步棋。

论文中提到，汇编游戏非常困难，因为AlphaDev必须能够有效地搜索到大量可能的指令组合以获取可以排序的算法。

指令组合数量类似于宇宙中粒子数量或国际象棋(10120局)和围棋(10700局)中可能走法的组合数量，每个错误的举动将会使整个算法失效。

然后，该模型输出一个算法并将其与预期输出比较，根据算法的正确性和延迟时间奖励代理。

在构建算法时，每次输入一个指令，AlphaDev通过比较输出算法与预期结果检查正确性（对于排序算法，这意味着输入无序的数字后能够输出正确排序的数字）。

模型会奖励AlphaDev对数字的正确排序以及它的高效。最终AlphaDev通过发现更准确的、更快的程序赢得了比赛。

4、算法创新：交换移动和复制移动指令序列

AlphaDev不仅生成了更快算法，还创新出两种指令序列。

具体来讲，它生成的排序算法包括交换移动和复制移动两种新的指令序列，每次使用时都会保存一条指令。研究者称之为“AlphaDev的交换移动和复制移动”。

这种新颖的方法让人想起AlphaGo的“第37步”——“反直觉”下棋法，震惊了旁观者并造成一位传奇棋手的失败。

通过交换移动和复制移动指令序列，AlphaDev跳过了一个步骤，以一种看起来像错误但实际上是捷径的方式完成目标。这表明，AlphaDev有能力发现原始解决方案，并挑战如何改进计算机科学算法。

5、测试：推广和改进散列算法

在发现更快的排序算法后，研究者测试了AlphaDev是否可以推广和改进另一种计算机科学算法：散列算法。

散列算法是计算中的一种基本算法，用于检索、存储和压缩数据。就像图书管理员使用分类系统定位某本书一样，散列算法帮助用户知道他们要找的是什么以及在哪里可以找到它。

这些算法能够获取特定密钥(例如，用户名“Jane Doe”)的数据并对其进行散列排序——将原始数据转换为唯一字符串(例如，1234ghty)。

计算机使用该散列快速检索与密钥相关的数据，而不是搜索所有数据。

研究人员将AlphaDev应用于数据结构中最常用的散列算法之一以尝试发现更快的算法。当将其应用于散列函数的9-16字节范围时，AlphaDev生成的算法速度快了30%。

今年早些时候，AlphaDev生成的新散列算法曾被发布到开源的Abseil库中，全世界数以百万计的开发人员都可以使用，估计它现在每天被使用数万亿次。

6、蓄势：迈出开发AGI的第一步  

通过优化“排序和散列算法”，AlphaDev展示出生成不同实用新算法的能力。

这也是AlphaDev朝着开发通用人工智能（AGI）工具迈出的第一步，通过类似的AI工具还可以帮助优化整个计算生态系统并解决其它有益于社会的问题。

虽然在低级汇编指令空间中优化算法的功能非常强大，但它也存在局限性。目前，团队也正在探索AlphaDev直接在高级语言(如，C++)中优化算法的能力，这对开发人员更有用。

总之，希望这些新发现能够激励开发人员创造新技术和方法、进一步优化基本算法，创造更强大、更可持续的计算生态系统。

7、开源：AI优化代码的里程碑突破

此前，排序算法每天都会被使用数万亿次。随着计算需求的增长，人们对算法的性能要求越来越高。虽然人类工程师已发现不同的排序算法，但经过几十年的优化，很难再有突破，也满足不了日益增长的需求。

如今，AlphaDev发现了一种更快的排序算法，可对数据进行排序。

新排序算法无所不能，既可应用于对在线搜索结果和社交帖子进行排名，也可在电脑和手机上处理数据。

值得庆贺的是，新排序算法已在主C++库中开源。世界各地数以百万的开发人员和公司目前可将其用于云计算、在线购物、供应链管理等。

总之，使用人工智能工具优化算法将彻底改变传统编程方式。这是十几年来第一次对排序库进行更改，第一次将强化学习模型设计出的算法添加到排序库中，因此成为了使用人工智能优化代码的里程碑式突破。

8、用户：可能只是噱头 

对于该项研究成果用户褒贬不一，Twitter上赞美的声音居多：

“这太棒了！在程序员早期就学会的基本排序任务基础上，速度提高了70%。看到利用AI在我们都依赖的算法和库中进行重大加速，真是令人兴奋”。

“很快，普通人就可以成为高级程序员”。

“有趣的方法，从装配级别开始优化”！

但是，也有的程序员认为这只是个噱头，DeepMind夸大了该算法的功能。

首先就是从效率的角度，它只统计了算法的延迟，而非真正改变了时间复杂度。

而且，它并没有真正改变排序，这种操作常见于各种其它代码库。

参考资料：

1.https://www.nature.com/articles/s41586-023-06004-9

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

3.https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools

4.https://twitter.com/demishassabis