重现当年 AlphaGo 神来之笔，DeepMind 新 AI 发现提速 70% 排序算法，十年都没更的 C++ 库更新了

DeepMind 又双叒叕带着重磅成果登 Nature 了！

这一次，他们又一强化学习 AI，在计算机领域最最最基础的两个算法上做了新突破：

一个是排序算法，发现了速度最高可提升 70%的新实现；

另一个是哈希算法，也找到了速度提高 30%的新方法。

不仅如此，该 AI 所用方法被称为“重现当年 AlphaGo 的神来之笔”，也就是看似违反直觉，实则一举击败人类高手李世石的那次。

消息一出，立刻引爆学术圈，有网友就直呼：

没想到这么古老又基础的算法还能被进一步改进。

而正是因为这一最新成果，十年都没有更新的 LLVM 标准 C++ 库都更新了，并且数十亿人将会受益。

因为，无论是排序还是哈希，它们的应用场景从在线购物、云计算到供应链管理等各个场景都能用到，每天会被调用上亿次！

不过，如 DeepMind 所说：

大家千万不要太兴奋了，AI 的力量用于代码效率提升才刚刚开始。

Alpha 家族“新贵”发现更快排序算法

这个 AI 名叫AlphaDev，属于 Alpha 家族“新贵”，并且基于 AlphaZero 打造（就是 2017 年击败世界冠军的那个棋类 AI）。

它的发现并非基于现有算法，而是从最底层的汇编指令开始摸索的。

DeepMind 的研究员给它设计了一种单人“组装”游戏：

只要能够搜索并选择出合适的指令（下图 A 流程），正确且快速地排好数据（下图 B 流程），就能获得奖励。

但这个游戏的挑战不仅在于搜索空间的大小（可组合指令数相当于宇宙中的粒子数），也在于奖励函数的性质，因为一条错误指令就可能会使整个算法失效。

AlphaDev 拥有两个核心组件：学习算法和表示函数。

其中，学习算法主要是在强大的 AlphaZero 上扩展的，它可以结合 DRL 和随机搜索优化算法来进行巨量的指令搜索；主要的表示函数则基于 Transformer，它能够抓住汇编程序的底层结构，并表示成特殊的序列。

随着 AlphaDev 不断地打怪升级，研究员还会限制它能执行的步数，以及待排序列的长度。

最终，AlphaDev 发现了一种全新排序算法：

如果序列较短，相比人类基准排序算法，它能将速度提高 70%；如果序列长度超过 25000 个元素，则提高 1.7%。

（3-5 个元素的短序列排序其实使用非常广泛，因为它能够作为较大排序函数的一部分被多次调用。因此，只要改进了短序列，任意数量序列的整体排序速度都能得到提高。）

具体而言，该算法的创新主要在于两种指令序列：

（1）AlphaDev Swap Move（交换移动）

（2）AlphaDev Copy Move（复制移动）

如下图所示，左边是利用了 min (A,B,C) 的原始 sort3 实现，右边是通过“AlphaDev Swap Move”，只需要 min (A,B) 的实现。能够发现可以省掉一步指令，还只需要算出 A 和 B 的最小值即可。

作者表示，这种新颖的方法让人想起当年AlphaGo 的“第 37 步”—— 一种违反直觉的下法却直接击败传奇围棋选手李世石，让观众全都震惊不已。

同样，AlphaDev 则是通过交换和复制移动，跳过了一个步骤，以一种看似错误但实际上是捷径的方式达成目标。

如下图所示，在对 8 个元素进行排序的算法中，AlphaDev 也同样利用“AlphaDev Copy Move”，用 max (B, min (A, C)) 替换了原始实现中更为复杂的 max (B, min (A, C, D)) 指令，并且使整个算法的指令总数也减少了一步。

而在发现更快的排序算法后，作者也用 AlphaDev 试了试哈希算法，以此证明其通用性。

结果也没有让人失望，AlphaDev 在 9-16 字节的长度范围内也实现了 30% 的速度提升。

和排序算法一样，他们已将新方法集成到了 Abseil 库中，全球数百万开发人员现在都可以使用。

最后，作者表示，两种新算法的实现显示 AlphaDev 具有强大的发现原始解决方案的能力，并且将使我们进一步思考计算机领域基础算法的改进方式。

不过，由于本次研究中使用的汇编语言具有局限性，他们接下来还是打算尝试 AlphaDev 在高级语言（如 C++）中优化算法的能力。

网友：不算发现新的排序算法

对于这一成果，不少人表示非常兴奋。

如这位网友所说：

AlphaGo 惊艳全世界后，强化学习还能做什么？还能做任何有实际意义的事情吗？这就是答案。

不过这次，有不少人指出，DeepMind 似乎有夸大标题的嫌疑。

它计算的是算法延迟，而非传统意义上的时间复杂度。如果真算时间复杂度，数据可能不好看。

它改进的并不是排序本身，而是在现代 CPU 上做新的排序（特别是短序列）。这种操作其实不算罕见，比如 FFTW、ATLAS 这些库就是这么做的。

同意，他们只是为特定 CPU 找到了更快的机器优化，并不算发现新的排序算法，方法本身很酷，但还不算开创性研究。

大家怎么看？

论文地址：

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

官方博客：

https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms?utm_source=twitter&utm_medium=social&utm_campaign=OCS

参考链接：

• [1]https://twitter.com/demishassabis/status/1666545516941803520

• [2]https://news.ycombinator.com/item?id=36228125

• [3]https://twitter.com/DeepMind/status/1666462540367372291

本文来自微信公众号：量子位 （ID：QbitAI），作者：丰色

广告声明：文内含有的对外跳转链接（包括不限于超链接、二维码、口令等形式），用于传递更多信息，节省甄选时间，结果仅供参考，IT之家所有文章均包含本声明。