机器之心原创

2023/06/08 14:20

AI重写排序算法，速度快70%：DeepMind AlphaDev革新计算基础，每天调用万亿次的库更新了

计算的基础就此改变了。

「通过交换和复制移动，AlphaDev 跳过了一个步骤，以一种看似错误，但实际上是捷径的方式连接项目。」这种前所未见、违反直觉的思想不禁让人回忆起 2016 年那个春天。

七年前，AlphaGo 在围棋上击败人类世界冠军，如今 AI 又在编程上给我们上了一课。

今天凌晨，Google DeepMind CEO 哈萨比斯的两句话引爆了计算机领域：「AlphaDev 发现了一种全新且更快的排序算法，我们已将其开源到主要 C++ 库中供开发人员使用。这只是 AI 提升代码效率进步的开始。」

这一次，Google DeepMind 的全新强化学习系统 AlphaDev 发现了一种比以往更快的哈希算法，这是计算机科学领域中的一种基本算法，AI 的成果现已被纳入 LLVM 标准 C++ 库 Abseil 并开源。

这个成果有多重要？AlphaDev 的主要作者之一，Google DeepMind 研究科学家 Daniel J. Mankowitz 表示：「我们估计它发现的排序和哈希算法每天会在全世界被调用数万亿次。」

AI 似乎从算法层面加速了世界的运转。

这些算法改进了 LLVM libc++ 排序库，对于较短的序列，排序库的速度提高了 70%，对于超过 25 万个元素的序列，速度也能提高约 1.7%。Google DeepMind 表示，这是十多年来排序库这部分的第一次变化。看起来，现在 AI 不仅可以帮人写代码，而且可以帮我们写出更好的代码。

在最新的博客中，新系统的作者们对 AlphaDev 进行了详细介绍。

新的算法将改变计算基础

数字社会推动了对计算和能源日益增长的需求。过去五十年里，数字时代依靠硬件的改进来跟上需求。但是随着微芯片接近其物理极限，改进在其上运行的代码变得至关重要。对于每天运行数万亿次的代码所包含的算法来说，这尤其重要。

Google DeepMind 的这项研究就是因此产生的，相关论文已发表在《Nature》上，AlphaDev 是一个 AI 系统，它使用强化学习来发现算法，甚至超越了科学家和工程师们几十年来打磨出来的成果。

论文地址：https://www.nature.com/articles/s41586-023-06004-9

总体来说，AlphaDev 发现了一种更快的排序算法。虽然数十亿人每天都在使用这些算法，但却没有人意识到这一算法还存在优化空间。排序算法应用范围广泛，从在线搜索结果、社交帖子排序，到计算机以及手机上的各种数据处理，都离不开排序算法。利用 AI 生成更好的算法将改变人类编程计算机的方式，对日益数字化的社会将产生重大影响。

通过在主要的 C++ 库中开源新排序算法，全球数百万开发人员和公司现在可以在云计算、在线购物和供应链管理等各行各业的人工智能应用中使用它。这是十多年来对排序库的首次更改，也是通过强化学习设计的算法首次被添加到该库中。这将这视为使用人工智能逐步优化世界代码的重要里程碑。

关于排序

排序算法是一种按照特定顺序对某些任务进行排列的方法。例如，按字母先后顺序排列三个字母，从大到小排列五个数字，或者对数百万条记录的数据库进行排序。

这种算法由来已久，并得到了很好的演进。其中关于排序的最早一个示例可追溯到公元 2 世纪和 3 世纪，当时学者们在亚历山大图书馆的书架上手工按字母顺序排列了数千本书。随着工业革命的到来，出现了可以帮助人们进行排序的机器，其中制表机使用打孔卡片存储信息，这些卡片被用于收集美国 1890 年的人口普查结果。

随着上世纪 50 年代商用计算机的兴起，最早用于排序算法的计算机科学算法开始发展。如今，在全球的代码库中有许多不同的排序技术和算法被用于处理海量的在线数据。

将一系列未排序的数字输入到算法中，输出已排序的数字。

经过计算机科学家和程序员们几十年的研究，目前的排序算法已经非常高效，以至于很难再实现进一步的改进，这有点类似于试图找到一种新的节省电力或更高效的数学方法，而这些算法也是计算机科学的基石。

探索新算法：汇编指令

AlphaDev 从头开始探索更快的算法，而不是基于现有算法之上，除此以外，AlphaDev 还能用于寻找大多数人所不涉足的领域：计算机汇编指令。

汇编指令可用于创建计算机执行的二进制代码。开发人员使用诸如 C++ 之类的高级语言编写代码，但必须将其转换为计算机能够理解的「低级」汇编指令。

Google DeepMind 认为这个层次存在许多改进的空间，而这些改进在更高级的编程语言中可能很难被发现。在这个层次上，计算机的存储和操作更加灵活，这意味着存在更多潜在的改进可能性，这些改进可能对速度和能源使用产生更大的影响。

代码通常是用高级编程语言（如 C++）编写的。然后，编译器将其转换为低级 CPU 指令，称为汇编指令。汇编器将汇编指令转换为可执行的机器码，以便计算机可以运行。

图 A：C++ 算法示例，该算法可对最多两个元素进行排序；图 B：相应的汇编表示形式。

用 AlphaGo 的方法寻找最佳算法

AlphaDev 基于 Google DeepMind 此前的一项成果：在围棋、国际象棋和象棋等游戏中打败世界冠军的强化学习模型 AlphaZero。而 AlphaDev 展示了这个模型如何从游戏转移到科学挑战，以及从模拟到现实世界的应用。

为了训练 AlphaDev 发现新的算法，团队将排序变成了一个单人的「组装游戏」。在每个回合中，AlphaDev 观察它所产生的算法和 CPU 中包含的信息，然后通过选择一条指令添加到算法中来下一步棋。

汇编游戏是非常困难的，因为 AlphaDev 必须在大量可能的指令组合中进行高效搜索，以找到一个可以排序的算法，并且比当前的最佳算法更快。指令的可能组合数量类似于宇宙中的粒子数量，或者国际象棋（10^120 局）和围棋（10^700 局）中可能的动作组合的数量，而一个错误的动作就可以使整个算法失效。

图 A：组装游戏。玩家 AlphaDev 接收系统 st 的状态作为输入，并通过选择一条汇编指令添加到目前已生成的算法中来下棋。图 B：奖励计算。每次移动后，生成的算法都会输入测试输入序列 —— 对于 sort3，这对应于三个元素序列的所有组合。该算法然后生成一个输出，将其与排序情况下排序序列的预期输出进行比较。智能体根据算法的正确性和延迟获得奖励。

在构建算法时，对于每次的一条指令，AlphaDev 通过将算法的输出与预期结果进行比较来检查它是否正确。对于排序算法，这意味着无序数字进入，正确排序的数字出来。团队会奖励 AlphaDev 对数字的正确排序以及排序的速度和效率，然后 AlphaDev 通过发现正确、更快的程序来赢得比赛。

它发现了更快的排序算法

AlphaDev 发现了新的排序算法，这些算法导致 LLVM libc++ 排序库得到改进：对于较短的序列，排序库的速度提高了 70%，对于超过 25 万个元素的序列，速度提高了约 1.7%。

其中，Google DeepMind 团队更专注于改进三到五个元素的短序列排序算法。这些算法是使用最广泛的算法之一，因为它们通常作为更大排序函数的一部分被多次调用，改进这些算法可以提高对任意数量项目进行排序的整体速度。

为了让新的排序算法对人们更有用，团队对算法进行了逆向工程并将它们翻译成 C++，这是开发人员使用的最流行的编程语言之一。

目前，这些算法已在 LLVM libc++ 标准排序库（https://reviews.llvm.org/D118029）中提供，被全球数百万开发人员和公司使用。

「交换和复制动作」，神之一手重现？

事实上，AlphaDev 不仅发现了更快的算法，而且还发现了新的方法。它的排序算法包含新的指令序列，每次应用时都会节省一条指令 —— 这显然会产生巨大的影响，因为这些算法每天都要使用数万亿次。他们把这些称为「AlphaDev 交换和复制动作」。

这种新颖的方法让人联想到 AlphaGo 的「第 37 步」—— 当时这这种反直觉的下法让围观者目瞪口呆，并导致李世石这位传奇围棋选手被打败。通过交换和复制动作，AlphaDev 跳过了一个步骤，以一种看起来像错误但实际上是捷径的方式连接项目。这表明 AlphaDev 有能力发掘出原创性的解决方案，并挑战人类对如何改进计算机科学算法的思考方式。

左图：min (A,B,C) 原始的 sort3 实现；右图：AlphaDev 交换移动 ——AlphaDev 发现你只需要 min (A,B)。

左图：在一个更大的排序算法中使用 max（B，min（A，C，D））的原始实现，用于排序八个元素；右图：AlphaDev 发现，使用其复制动作时，只需要 max（B，min（A，C））。

扩展能力测验：从「排序」到「哈希」

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

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

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

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

开源地址：https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

结语

Google DeepMind 通过优化和推出改进的排序和哈希算法，供世界各地的开发人员使用，AlphaDev 展示了其概括和发现具有现实影响的新算法的能力。AlphaDev 可被视为开发通用 AI 工具的一步，它可以帮助优化整个计算生态系统并解决其他造福社会的问题。

虽然在低级汇编指令空间中进行优化非常强大，但随着算法的增长， AlphaDev 仍存在局限性，团队目前正在探索其直接在高级语言（如 C++）中优化算法的能力，这对开发人员来说更加有用。

AlphaDev 的发现，例如交换和复制动作，不仅表明它可以改进算法，还可以找到新的解决方案。这些发现或许能够激励研究人员和开发人员创建可以进一步优化基础算法的技术和方法，以创建更强大和可持续的计算生态系统。

参考内容：

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

https://news.ycombinator.com/item?id=36228125

https://twitter.com/DJ_Mankowitz/status/1666468646863130631

理论DeepMind排序算法

相关数据

DeepMind机构

DeepMind是一家英国的人工智能公司。公司创建于2010年，最初名称是DeepMind科技（DeepMind Technologies Limited），在2014年被谷歌收购。在2010年由杰米斯·哈萨比斯，谢恩·列格和穆斯塔法·苏莱曼成立创业公司。继AlphaGo之后，Google DeepMind首席执行官杰米斯·哈萨比斯表示将研究用人工智能与人类玩其他游戏，例如即时战略游戏《星际争霸II》（StarCraft II）。深度AI如果能直接使用在其他各种不同领域，除了未来能玩不同的游戏外，例如自动驾驶、投资顾问、音乐评论、甚至司法判决等等目前需要人脑才能处理的工作，基本上也可以直接使用相同的神经网上去学而习得与人类相同的思考力。

https://deepmind.com/

排序算法技术

排序算法是将一串数据依照特定排序方式进行排列的算法，最常用到的排序方式是数值顺序以及字典顺序。基本上，排序算法的输出必须遵守下列两个原则：输出结果为递增序列（递增是针对所需的排序顺序而言）；输出结果是原输入的一种排列、或是重组。

来源：维基百科

AlphaZero技术

DeepMind 提出的 AlphaZero 不仅征服了围棋，也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。DeepMind 推出的 AlphaGo 曾在围棋项目中取得了超越人类的表现，其研究曾经两次登上 Nature。2018 年 12 月，AlphaGo 的「完全自我博弈加强版」AlphaZero 的论文又登上另一大顶级期刊 Science 的封面。在论文中，AlphaZero 不仅征服了围棋，也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。

来源：机器之心

人工智能技术

在学术研究领域，人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体（intelligent agent）

来源：Russell, S., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach.

线搜索技术

最优化问题中，线搜索是一种寻找目标函数的局部最小值的近似方法。它是最基础的迭代近似方法之一，另一种是置信域方法。线搜索近似首先找到一个使目标函数下降的方向，然后计算应该沿着这个方向移动的步长。下降方向可以通过多种方法计算，比如梯度下降法，牛顿法和拟牛顿法。

来源：维基百科

逆向工程技术

逆向工程，又称反向工程，是一种技术过程，即对一项目标产品进行逆向分析及研究，从而演绎并得出该产品的处理流程、组织结构、功能性能规格等设计要素，以制作出功能相近，但又不完全一样的产品。逆向工程源于商业及军事领域中的硬件分析。

来源：维基百科

数据库技术

数据库，简而言之可视为电子化的文件柜——存储电子文件的处所，用户可以对文件中的数据运行新增、截取、更新、删除等操作。所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

来源：维基百科

云计算技术

云计算（英语：cloud computing），是一种基于互联网的计算方式，通过这种方式，共享的软硬件资源和信息可以按需求提供给计算机各种终端和其他设备。

来源：Cloud Computing

哈希函数技术

散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。

强化学习技术

强化学习是一种试错方法，其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划（Dynamic Programming）。流行的强化学习方法包括自适应动态规划（ADP）、时间差分（TD）学习、状态-动作-回报-状态-动作（SARSA）算法、Q 学习、深度强化学习（DQN）；其应用包括下棋类游戏、机器人控制和工作调度等。

来源：机器之心

围棋技术

围棋是一种策略性棋类，使用格状棋盘及黑白二色棋子进行对弈。起源于中国，中国古时有“弈”、“碁”、“手谈”等多种称谓，属琴棋书画四艺之一。西方称之为“Go”，是源自日语“碁”的发音。

来源：维基百科