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 has open-sourced them and integrated them into the Libc++ standard library.。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通过交换移动和复制移动指令序列，AlphaDev跳过了一个步骤，以一种看起来像错误但实际上是捷径的方式完成目标。这意味着AlphaDev具备发现初始解决方案并尝试改进计算机科学算法的能力。

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

研究人员在发现更快的排序算法后，试图将其应用到另一种计算机科学算法——散列算法的推广和改进上。

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

这些算法能够获取特定密钥(例如，用户名“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

以上是DeepMind推惊世排序算法，C++库忙更新！的详细内容。更多信息请关注PHP中文网其他相关文章！