重现当年AlphaGo神来之笔！DeepMind新AI发现提速70%排序算法，十年都没更的C++库更新了
关注前沿科技约 5 分钟
丰色 发自 凹非寺
量子位 | 公众号 QbitAI
DeepMind又双叒叕带着重磅成果登Nature了！
这一次，他们又一 强化学习AI ，在 计算机领域最最最基础的两个算法 上做了新突破： 一个是 排序算法 ，发现了 速度最高可提升70% 的新实现； 另一个是 哈希算法 ，也找到了 速度提高30% 的新方法。
不仅如此，该AI所用方法被称为“重现当年AlphaGo的神来之笔”，也就是看似违法直觉，实则一举击败人类高手李世石的那次。
消息一出，立刻引爆学术圈，有网友就直呼：
没想到这么古老又基础的算法还能被进一步改进。
因为，无论是排序还是哈希，它们的应用场景从在线购物、云计算到供应链管理等各个场景都能用到，每天会被调用上亿次！
不过，如DeepMind所说：
大家千万不要太兴奋了，AI的力量用于代码效率提升才刚刚开始。
Alpha家族“新贵”发现更快排序算法
这个AI名叫 AlphaDev ，属于Alpha家族“新贵”，并且基于AlphaZero打造 （就是2017年击败世界冠军的那个棋类AI） 。 它的发现并非基于现有算法，而是从最底层的 汇编指令 开始摸索的。DeepMind的研究员给它设计了一种单人“组装”游戏：
只要能够搜索并选择出合适的指令 （下图A流程） ，正确且快速地排好数据 （下图B流程） ，就能获得奖励。
AlphaDev拥有两个核心组件：学习算法和表示函数。
其中，学习算法主要是在强大的AlphaZero上扩展的，它可以结合DRL和随机搜索优化算法来进行巨量的指令搜索；主要的表示函数则基于Transformer，它能够抓住汇编程序的底层结构，并表示成特殊的序列。
随着AlphaDev不断地打怪升级，研究员还会限制它能执行的步数，以及待排序列的长度。
最终，AlphaDev发现了一种全新排序算法：
（3-5个元素的短序列排序其实使用非常广泛，因为它能够作为较大排序函数的一部分被多次调用。因此，只要改进了短序列，任意数量序列的整体排序速度都能得到提高。）如果序列较短，相比人类基准排序算法，它能将速度提高70%；如果序列长度超过25000个元素，则提高1.7%。
具体而言，该算法的创新主要在于两种指令序列：
（1） AlphaDev Swap Move （交换移动）（2） AlphaDev Copy Move （复制移动）
如下图所示，左边是利用了min(A,B,C)的原始sort3实现，右边是通过“AlphaDev Swap Move”，只需要min(A,B)的实现。能够发现可以省掉一步指令，还只需要算出A和B的最小值即可。
如下图所示，在对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惊艳全世界后，强化学习还能做什么？还能做任何有实际意义的事情吗？这就是答案。
它计算的是算法延迟，而非传统意义上的时间复杂度。如果真算时间复杂度，数据可能不好看。
它改进的并不是排序本身，而是在现代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 — 完 — 「AIGC+垂直领域社群」 招募中！
欢迎关注AIGC的伙伴们加入AIGC+垂直领域社群，一起学习、探索、创新AIGC！
请备注您想加入的垂直领域「教育」或「电商零售」，加入AIGC人才社群请备注「人才」&「姓名-公司-职位」。