AlphaDev将排序算法提速70%！C语言库作者一文详解DeepMind最新AI

原文：新智元

图片来源：由无界 AI‌ 生成

几天前，DeepMind推出了AlphaDev，直接把排序算法提速70%。

这一全新AI系统，便是基于下棋高手AlphaGo打造。

而这项研究恰恰激起了前谷歌研究人员Justine Tunney的兴趣。

她表示，作为一名C语言库的作者，我一直在寻找机会来策划最好的东西。

一起看看Justine如何详解DeepMind排序算法。

DeepMind排序算法

DeepMind的这一发现赢得了当之无愧的关注，但不幸的是，他们本可以更好地解释AlphaDev。

接下来，从DeepMind发布的汇编代码开始，该代码将一个有三个项目的数组进行排序，从伪汇编翻译成汇编：

我将这个函数命名为 move37() ，是因为DeepMind的博客文章，将其与AlphaGo下的令人震惊的「第37步」进行了比较。

在2016那场人机大战中，AlphaGo下了一颗违反人类直觉的棋，一个简单的肩冲，击败了传奇围棋选手李世石。

所以如果运行DeepMind代码：

但是，在我看来这是一个错误。

我们给它的数组是{3,1,2}，但 move37() 将其排序为{2,1,3}。

DeepMind一定在欺骗我们，因为我不相信2在1之前。再来看看他们对LLVM libcxx所做的开源贡献，这有望澄清一些事情：

所以 move37() 实际上不是一个排序函数，而是一个排序内核，旨在用作 sort3() 函数的构建块。

如果论文和博客文章能提到这一点就好了，因为它让我在最短的时间内感到非常困惑。下面是更好的代码版本，其中包括缺失的交换（swap）操作。

为了解释为什么他们的代码很重要，让我们考虑一下这个算法在高层次上是如何工作的。当我第一次尝试自己解决 sort3() 问题时，我想到了这个：

然后我查看了libcxx，发现它们也在做同样的事情。上述代码的问题是，编译器并不善于优化它。

如果你尝试编译上面的代码，就会注意到你的编译器插入了大量的分支指令。这就是DeepMind试图通过LLVM贡献来改进的地方。

然而，这些技术往往不太容易理解。

我实际上喜欢天真无邪的代码，因为如果我们眯起眼睛，可以看到一种模式，与DeepMind最先进的汇编代码有相同的基本想法。

这个想法是这个问题本质上归结为3个比较和交换操作：

上面的代码是之前排序网络的最先进技术。现在，这就是DeepMind的新发现发挥作用的地方。他们发现有时上面的 mov 指令是不必要的。

如果你试着运行上面的代码，你会发现不管有没有被删除的行，它都是100%正确的。

这行代码看起来像是在做什么，但实际上什么也没做。所以我并不惊讶这样的事情会被计算机科学忽视几十年。

现在也应该更清楚AlphaDev是如何工作的。

DeepMind基本上构建了一个人工智能，它可以摆弄汇编代码，随机删除一些东西，看看它是否损坏。