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

哈喽！大家好，很高兴又见面了，我是golang学习网的一名作者，今天由我给大家带来一篇《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 their code and incorporated it into the popular Libc++ 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、测试：推广和改进散列算法

研究者在发现更快的排序算法之后，开始测试是否可以将AlphaDev应用于改进和推广散列算法，这是另一种计算机科学算法。

散列算法是计算中的一种基本算法，用于检索、存储和压缩数据。就像图书管理员使用分类系统来定位书籍一样，散列算法帮助用户确定他们所需的内容及其位置。

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

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

为了寻找更快的算法，研究人员尝试将AlphaDev应用于最常用的散列算法之一——数据结构。AlphaDev的算法在应用于散列函数时，在处理9-16字节范围内的数据时，速度提高了30%。

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

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

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

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

尽管在低级汇编指令空间中优化算法的能力很强大，然而它也有其限制。目前，团队正在研究如何在高级语言(例如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++库忙更新！》的详细内容，更多关于算法,C++库的资料请关注golang学习网公众号！