排序，太难了！

什么是排序？

几十年来，计算机行业的发展一直依赖于硬件的改进。然而，随着微芯片日趋接近其物理极限，对软件进行优化越来越受到计算机科学家的重视。

对于改进算法来说，人类的直觉和专业知识至关重要。但是，许多算法都已经达到了人类科学家无法进一步优化它们的阶段，这导致了计算瓶颈的不断加剧，其中就包括排序。

排序是计算机科学中的一个基本算法，它涉及到将许多的项按特定的顺序排列起来，比如按字母顺序排列字母，又比如按从大到小的顺序排列数字。

排序算法能将一系列未排序的数字转变为已排序的数字。（图/DeepMind）

排序最早可以追溯到二世纪和三世纪，当时，学者们按照字母顺序，徒手为亚历山大图书馆书架上的数千本书排序。现如今，在世界各地的代码库中，有许多不同的排序技术和算法用于组织大量数据。它的应用无处不在，每一天都会被使用数万亿次。

在一项新发表于《自然》杂志的研究中，DeepMind团队介绍了一种新的人工智能（AI）系统——AlphaDev，它通过使用深度强化学习，发现了更快的排序算法。这些全新的算法超越了现有的、最优的、由人类科学家在数十年时间里磨炼出的算法。

什么是AlphaDev？

AlphaDev并没有对现有的算法进行改进，而是从零开始发现新的、更快的算法。它的工作原理与AlphaZero类似，我们知道，AlphaZero是一款用于下国际象棋、围棋和将棋的人工智能系统，它通过强化学习方法，在棋盘游戏中击败了世界冠军。

在AlphaZero的设计中，当它要走每一步时，都会考虑所有可能的走法，以及在每一步走法之后的可能走法，以此类推。它以一种分支的形式计算哪些走法最有可能以胜利结束。但是，考虑所有可能的分支所需的时间可能比宇宙的年龄还要长，所以它还会使用一些类似于直觉的东西来缩小搜索范围。

在对AlphaDev的开发中，研究人员利用类似的思路，将排序转换为一种单人的“汇编游戏”。这里，在介绍AlphaDev的运作原理之前，我们首先要介绍计算机中一个概念——汇编指令。

汇编指令用于创建二进制代码供计算机执行。当人们使用C++这样的高级编程语言编写代码时，一个被称为编译器的程序会将这些代码翻译成“低级”的汇编指令，这些汇编指令又会被转换成一组机器级代码，以供计算机理解。计算机科学家相信，这个过程应该存在改进的空间。

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

在每个进行决策的回合中，AlphaDev会观察它生成的算法和包含在中央处理器（CPU）中的信息，然后通过选择在算法中添加一条指令来完成一步决策。

这种汇编游戏非常困难，因为AlphaDev必须对大量的可能的指令组合进行有效搜索，以找到一种优于目前的最好算法的排序算法。而这种指令的可能组合的数量级非常大，可以与宇宙中的粒子数量相比拟。而一步走错，就会使整个算法失效。

在构建算法时，对于每一次指令的添加，AlphaDev都会对算法的输出与预期结果进行比较，以检查结果是否正确。以排序算法来说，这意味在每一次添加指令后，AlphaDev就对一组输入的无序数字进行排序，然后输出正确的数字排序。

在这个过程中，神经网络会根据排序的正确性和速度对AlphaDev进行奖励。当AlphaDev发现了一个正确的、更快的算法时，它就赢得了游戏。

更快的排序算法

最终，AlphaDev发现了新的、更快的排序算法。对于较短的序列，AlphaDev的算法可以将速度提高70%。但对于超过25万个项的序列，累积节省的时间只能提高1.7%。

研究人员专注于改进较短序列（3-5个项）的排序算法。这样的算法非常重要，它们的使用广泛，经常作为更大的排序函数的一部分而被多次使用。改进这些算法有助于加快对任意数量的序列进行排序的总体速度。

此外，AlphaDev不仅发现了更快的算法，还发现了新的方法。在仔细分析了AlphaDev的排序算法后，研究人员发现了两种新的方法，他们称之为“AlphaDev交换移动步骤和复制步骤”。这些新的方法让人想起了AlphaGo的“第37步”，这是当时在AlphaGo与围棋冠军李世石对阵时走出的反直觉的一步，但这一步却被证实是赢得比赛的击败对手的基础一步。

通过交换移动和复制步骤，AlphaDev跳过了一个步骤，以一种看起来像错误但实际上是捷径的方式连接那些要进行排序的项。这表明AlphaDev不仅有能力发现全新的解决方案，并且还能挑战我们思考如何改进计算机科学算法的方式。‍‍