江苏龙网

  1. 主页 > 生活百科 > >

详解 DeepMind 排序算法

排序算法

作者 | Justine Tunney译者 | 弯月
责编 | 夏萌
出品 | CSDN（ID：CSDNnews）
近日，DeepMind 在博客发表了一篇阐述排序算法内核的论文 。他们借鉴了构建 AlphaGo 积累的有关深度学习的经验，并将其应用于超优化 。这激起了我的兴趣，因为作为一名 C 语言库的作者，我一直在寻找机会来提供最好的工具 。从某些方面来说，这是 C 语言库的最终目的 。虽然有些功能程序员已经习以为常了，但实际上它们是数十年研究的结晶，反复提炼而成的简单且可移植的代码 。
DeepMind 的这一发现确实居功至伟，但不幸的是，他们未能解释清楚算法 。下面，我们来详细看看他们发布的一段汇编代码，这是一个包含三个元素的数组的排序，我们将伪汇编转换为汇编：
/ move37.S .equ P,%rax .equ Q,%rcx .equ R,%rdx .equ S,%rsi move37: mov (%rdi),P mov 8(%rdi),Q mov 16(%rdi),R mov R,S cmp P,R cmovg P,R cmovl P,S cmp S,Q cmovg Q,P cmovg S,Q mov R,(%rdi) mov Q, 8(%rdi) mov P, 16(%rdi) ret .type move37,@function .size move37,.-move37 .globl move37 // deepsort1.c #include void move37(long *); intmAIn { long A[ 3] = { 3, 1, 2}; move37(A); printf( "%d %d %dn", A[ 0], A[ 1], A[ 2]);我将此函数命名为 move37，因为 DeepMind 在文章中将其与 2016 年 AlphaGo 在与李世石的第二场比赛中的第 37 步进行了比较 。这一步让专家们感到震惊，他们都认为 AlphaGo 走错了，但实际上错的是专家们，因为 AlphaGo 最终战胜了对手 。下面，我们来运行 DeepMind 的代码：
# run this on the shell cc-o deepsort1 deepsort1.c move37.S ./deepsort1 21 3在我看来，这个运行结果有错 。我提供的数组是 {3, 1, 2}，但排序结果为 {2, 1, 3} 。一定是 DeepMind 在骗我们，因为 2 确实不应该出现在 1 之前 。我们来看看他们为开源库 LLVM libcxx （https://reviews.llvm.org/D118029）贡献的代码，看看能否澄清这个问题：
// Ensures that *__x, *__y and *__z are ordered according to the comparator __c, // under the assumption that *__y and *__z are already ordered. template inline_LIBCPP_HIDE_FROM_ABI void__partially_sorted_swap( _RandomaccessIterator __x, _RandomAccessIterator __y, _RandomAccessIterator __z, _Compare __c) { usingvalue_type = typenameiterator_traits<_RandomAccessIterator>::value_type; bool__r = __c(*__z, *__x); value_type __tmp = __r ? *__z : *__x; *__z = __r ? *__x : *__z; __r = __c(__tmp, *__y); *__x = __r ? *__x : *__y; *__y = __r ? *__y : __tmp; }原来如此 。这么说实际上 move37 并不是排序函数 。它是一个排序内核，是函数的 sort3 的一部分 。如果 DeepMind 的论文和博客文章能提到这一点就好了，因为初看之下确实很迷惑 。下面是改进版的代码，包括缺少的交换操作 。
sort3: mov (%rdi),%rcx mov 8(%rdi),%rdx mov 16(%rdi),%rsi mov %rdx,%rax cmp %rdx,%rsi cmovl %rsi,%rax cmovl %rdx,%rsi mov %rcx,%rdx cmp %rcx,%rsi cmovl %rsi,%rdx cmovl %rcx,%rsi cmp %rax,%rdx cmovge %rax,%rcx cmovl %rax,%rdx mov %rcx,(%rdi) mov %rdx, 8(%rdi) mov %rsi, 16(%rdi) ret .globl sort3 .size sort3,.-sort3为了解释这段代码的重要性，我们来考虑一下这个算法在高层面的应用 。在第一次尝试自己解决 sort3 问题时，我想到了下面这段简短的代码：
// sorts [a,b,c] if(a > b) SWAP(a, b); if(a > c) SWAP(a, c); if(b > c) SWAP(b, c);回头查看 libcxx，发现他们在做同样的事情 。上述代码的问题是编译器无法很好地优化 。如果尝试编译上面的代码，你会注意到编译器插入了很多分支指令 。这就是 DeepMind 试图改进的地方，他们有更聪明的方法来编写这类代码 。然而，这些技巧往往不太容易理解 。实际上，我喜欢比较直白的代码，因为比较一下就会发现，这些代码与 DeepMind 最先进的汇编代码的基本思路相同 。从根本上说，这个问题的基本思想可以归结为三个比较和交换操作：
mov %rdx,%rax // create temporary cmp %rdx,%rsi // compare cmovl %rsi,%rax // conditional move cmovl %rdx,%rsi // conditional move / repeat thrice上述代码是预先对网络进行排序的最新技术 。下面是 DeepMind 的新发现发挥作用的地方 。他们发现上面的 mov 指令有时是不必要的 。
sort3: mov (%rdi),%rcx mov 8(%rdi),%rdx mov 16(%rdi),%rsi mov %rdx,%rax cmp %rdx,%rsi cmovl %rsi,%rax cmovl %rdx,%rsi mov %rcx,%rdx cmp %rcx,%rsi cmovl %rsi,%rdx cmovl %rcx,%rsi mov %rdx,%rcx // <-- wrekt by AlphaDev cmp %rax,%rdx cmovge %rax,%rcx cmovl %rax,%rdx mov %rcx,(%rdi) mov %rdx, 8(%rdi) mov %rsi, 16(%rdi) ret尝试运行上面的代码，你会发现无论那行被删除的代码是否存在，运行结果都是 100% 正确的 。这行代码看似有用，但实际上什么也没做 。因此，几十年来计算机科学都没有注意到这个问题，我并不感到惊讶 。到这里，AlphaDev 的工作原理也应该变得更加清晰了 。从根本上说，DeepMind 构建了一个人工智能，用于检查汇编代码，并随机删除一些代码，看看代码是否会出问题 。我这么说并不是要否定 AlphaDev 的智慧，因为我也做了相同的尝试 。


推荐阅读


上一篇：小红书上如何开店铺

下一篇：在线刷空间人气