排序或散列等基本算法在一天内的使用量可达数万亿次，随着计算需求的增长，让这些算法尽可能高效变得至关重要。基础排序算法在过去取得了显著的进步，但如要进一步提高这些算法例程的效率，对人类科学家和已知的计算方法都具有挑战性。

而 DeepMind 通过将 “寻找更好的排序程序” 任务制定成一个名为 AssemblyGame 的单人游戏。在这个游戏中，玩家需要选择一系列低级 CPU 指令（汇编指令），然后将其组合起来产生一种新的高效排序算法。

然后 DeepMind 训练了一个新的深度强化学习代理 ”AlphaDev“来玩这个游戏，AlphaDev 的主要学习算法是 AlphaZero 代理的扩展，并使用深度神经网络指导蒙特卡洛树搜索 (MCTS) 规划过程。

（完整的训练过程和细节分析可以在 deepmind 的论文中细细阅读）

最终，AlphaDev 从零开始地发现了几项新的小型排序算法，分别可用于对大小为 3、4 和 5 的列表进行排序，且均优于已知的人类基准。

目前这些算法已经集成到 LLVM 标准 C++ 排序库  中，使用强化学习的新算法替换掉了原有的 LLVM libc++ 标准排序 3、排序 4 和排序 5 算法，这些基础算法是 C++ 排序库的基本组件，通常被较大的排序算法多次调用。

值得一提的是，DeepMind 的提交是十多年来对 LLVM libc+ 排序算法子程序的首次更改。

原文来自：https://www.oschina.net/news/244274/google-finds-faste-sorting-algorithm

本文地址：https://www.linuxprobe.com/google-cpup.html编辑：roc_guo，审核员：清蒸github

Linux命令大全：https://www.linuxcool.com/

Linux系统大全：https://www.linuxdown.com/

红帽认证RHCE考试心得：https://www.rhce.net/