谷歌借AI打破十年排序算法封印，每天被执行数万亿次，网友却说是最不切实际的研究？

在科技周边实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《谷歌借AI打破十年排序算法封印，每天被执行数万亿次，网友却说是最不切实际的研究？》，聊聊，希望可以帮助到正在努力赚钱的你。

整理 | 核子可乐，褚杏娟

接触过基础计算机科学课程的朋友们，肯定都曾亲自动手设计排序算法——也就是借助代码将无序列表中的各个条目按升序或降序方式重新排列。这是个有趣的挑战，可行的操作方法也多种多样。人们曾投入大量时间探索如何更高效地完成排序任务。

作为一项基础操作，大多数编程语言的标准库中都内置有排序算法。世界各地的代码库中使用了许多不同的排序技术和算法来在线组织大量数据，但至少就与 LLVM 编译器配套使用的 C++ 库而言，排序代码已经有十多年没有任何变化了。

近日，谷歌 DeepMind AI 小组如今开发出一种强化学习工具 AlphaDev，能够在无需通过人类代码示例做预训练的情况下，开发出极限优化的算法。如今，这些算法已经集成到 LLVM 标准 C++ 排序库中，这是十多年来排序库部分第一次发生变化，也是第一次将通过强化学习设计的算法添加到该库中。

把编程过程视为“游戏”

DeepMind系统常常能够发现人类从未想到的攻关思路，而无需提前与任何人类游戏策略进行接触。DeepMind 可能在某些情况下存在会被人类利用的盲点，这是因为它完全依赖自我对抗学习经验。

这种方法跟编程其实非常相似。由于大语言模型曾接触了大量人类代码示例，所以它们能够编写出有效的代码。但也正因为如此，语言模型很难产出人类之前没做过的东西。如果我们希望对普遍存在的现有算法（例如排序函数）做进一步优化，那么继续依赖现有人类代码将很难突破固有思路的束缚。那么，如何才能让 AI 找到真正的新方向？

DeepMind 的研究人员通过将代码优化任务转化为单人的"组装游戏"，采用了类似国际象棋和围棋的方法。AlphaDev 系统开发出一种 x86 汇编算法，会将代码的运行延迟视为一个分数，在努力将该分数最小化的同时确保代码能够顺畅跑通。通过不断强化学习，AlphaDev逐渐掌握了书写简洁高效代码的技能。

AlphaDev 基于 AlphaZero。DeepMind以其开发能够自我学习游戏规则的AI软件而闻名。这种思路展现出了杰出的效果，已经成功解决了国际象棋、围棋和《星际争霸》等多个游戏难题。虽然具体细节因所玩游戏而异，但 DeepMind 软件确实能在重复游玩中不断学习，持续探索能令得分最大化的办法。

AlphaDev 的两个核心组件是学习算法和表示函数。

AlphaDev可以利用强化学习算法和随机搜索优化算法来探索组装游戏的学习过程。AlphaDev 中的主要学习算法是 AlphaZero 33 的扩展，AlphaZero 33 是一种著名的 DRL 算法，其中训练神经网络以指导搜索完成游戏。

这个函数承担了追踪代码开发过程中整体性能的任务，包括算法的一般结构以及对 x86 寄存器和内存的利用。系统将添加汇编指令并利用蒙特卡洛树搜索方法来做出选择。树状结构允许系统快速将搜索范围缩小至包含大量潜在指令的有限区域，而蒙特卡洛方法则以一定程度的随机性从这个分支区域内选择具体指令。请注意，所谓的"指令"是指选择特定寄存器和其他操作以创建有效且完整的程序集。）

随后，系统将对汇编代码的延迟和有效性状态进行评估，并对其进行打分，然后与之前的得分进行比较。通过强化学习，系统会在给定程序状态下保留树结构中不同分支的任务信息。系统会逐渐学习如何以最高分（表现为最低延迟）来获得游戏的胜利（成功完成排序）。AlphaDev的主要表达函数是基于Transformer的。

为了训练 AlphaDev 发现新算法，AlphaDev 在每轮中都会观察它生成的算法和中央处理器 (CPU) 中包含的信息，然后通过选择要添加到算法中的指令完成游戏。AlphaDev 必须有效地搜索大量可能的指令组合，以找到可以排序的算法，并且还要比当前最好的算法更快，同时代理模型可以根据算法的正确性和延迟获得奖励。

图 A：组装游戏，图 B：奖励计算

最终，AlphaDev 发现了新的排序算法，这些算法可以让 LLVM libc++ 排序库得到改进：对于较短的序列，排序库的速度提高了 70%；对于超过 250,000 个元素的序列，速度提高了约 1.7%。

具体而言，该算法的创新主要在于两种指令序列：AlphaDev Swap Move（交换移动）和 AlphaDev Copy Move（复制移动），通过这两个指令，AlphaDev 跳过了一个步骤，以一种看似错误但实际上是捷径的方式连接项目。

左图：带有 min(A,B,C) 的原始 sort3 实现。‍

右图：AlphaDev Swap Move - AlphaDev 发现你只需要 min(A,B)。

左：max (B, min (A, C)) 的原始实现用于对八个元素进行排序的更大排序算法。

‍右：AlphaDev 发现在使用其复制移动时只需要 max (B, min (A, C))。

这套系统的主要优势在于，其训练过程不借助任何代码示例。相反，系统会自主生成代码示例，然后对其做出评估。过程当中，它也就逐渐掌握了关于有效排序的指令组合信息。

从排序到散列

在发现更快的排序算法后，DeepMind 测试了 AlphaDev 是否可以概括和改进不同的计算机科学算法：散列。

哈希是计算中用于检索、存储和压缩数据的基本算法。就像使用分类系统来定位某本书的图书管理员一样，散列算法可以帮助用户知道他们正在寻找什么以及在哪里可以找到它。这些算法获取特定密钥的数据（例如用户名“Jane Doe”）并对其进行哈希处理——这是一个将原始数据转换为唯一字符串（例如 1234ghfty）的过程。计算机利用该散列算法可快速定位与密钥相关的数据，而无需遍历全部数据。

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

今年，AlphaDev 的新哈希算法被发布到开源 Abseil 库中，可供全球数百万开发人员使用，该库现在每天被数万亿次使用。

实际可用的代码

复杂程序中的排序机制能够处理大量任意条目的集合。但在标准库层面来看，这种能力源自一系列高度限定的具体函数。这些函数各自只能处理一种或几种情况。例如，某些单独算法只能对 3、4 或 5 个条目做排序。虽然我们可以同时使用一组函数对任意数量的条目进行排序，但原则上每次函数调用最多只能对4个条目进行排序。

DeepMind 在每个函数上都设置了 AlphaDev，其实际运行方式有着很大区别。可以编写不包含任何分支语句的代码，以处理特定数量的条目，即根据变量状态执行相应的代码。因此代码性能往往与所涉及的指令数量成反比。

AlphaDev 已经成功将 sort-3、sort-5 和 sort-8 的指令数量各减一，在 sort-6 和 sort-7 中的指令削减量甚至更多。只有 sort-4 上没能找到改进现有代码的方法。通过实际系统的重复运行测试证实，较少的指令确实能够提升性能。

要对可变数量的条目进行排序，代码必须包含条件分支，并且不同处理器专门处理不同数量的这些条件分支。

研究人员评估了代码性能，使用了 100 台不同的计算设备。AlphaDev 在这类场景下同样找到了进一步榨取性能的方法，下面我们以一次最多排序 4 个条目的函数为例，看看它到底是怎么操作的。

在 C++ 库的现有实现中，代码需要进行一系列测试来确认具体需要对多少个条目做排序，再根据条目数量调用相应的排序函数。

而 AlphaDev 修改后的代码则采取更加“神奇”的思路：它先测试是不是 2 个条目，如果是则调用相应函数立即做排序。如果数量大于 2 个，则代码会先对前 3 个条目做排序。这样如果确实只有 3 个条目，则返回排序结果。由于实际是有 4 个条目要做排序，所以 AlphaDev 会运行专门代码，以非常高效的方式将第 4 个条目插入到前 3 个已经排序完成的条目中的适当位置。

这种办法听起来有点怪异，但事实证明其性能确实始终优于现有代码。

由于 AlphaDev 确实生成了更高效的代码，所以研究团队打算把这些成果重新合并到 LLVM 标准 C++ 库中。但问题是这些代码为汇编格式，而非 C++。因此，他们需要使用逆向计算来找到能够生成相同程序集的 C++ 代码。

这句话的修改如下： 最新一次的更新将代码成果整合进了LLVM工具链中，这是过去10年以来的首次更新。据估计，每天有数万亿次执行AlphaDev生成的新代码。

结束语

"太厉害了！我们程序员终于成功将基本排序任务的速度提高了70%"。是振奋人心的，我们现在依赖的算法和库中使用了 AI，使得速度大幅提升。”有开发者对谷歌 DeepMind 的成果表示振奋。

但也有开发者并不买账：“相当令人失望……1.7% 的改善？5 个元素的序列 70%？可能是最不受欢迎、最不切实际的应用研究……”也有开发者表示：“说发现了新算法是不是有点误导人？似乎更像是算法优化。无论如何这仍然很酷。”

参考链接：

https://arstechnica.com/science/2023/06/googles-deepmind-develops-a-system-that-writes-efficient-algorithms/

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

深度：为什么中国数据库领域没有出现像Snowflake这样的巨头？

十七年来奇葩大崩溃！为不让OpenAI和谷歌白拿数据，Reddit 收取巨额API 费用还诽谤开发者，社区爆发大规模抗议

“偷”代码建起公司、学历造假、6天拿下1亿美元却拖欠工资，这位AI独角兽CEO屡遭质疑后亲自回应了

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于科技周边的相关知识，也可关注golang学习网公众号。