AI重写排序算法能改写摩尔定律放缓的命运吗？

　　“重现当年AlphaGo神来之笔”，“没想到这么古老又基础的算法还能被进一步改进”……以上是网友对DeepMind公司AI系统AlphaDev发现的新排序算法的评价。这个名叫AlphaDev的人工智能是基于AlphaZero（2017年击败世界冠军的棋类AI）打造的，它正在重新“构想”排序算法，创新计算机领域核心算法。

　　DeepMind在科学杂志《自然》上发表的一篇论文中提到，与C﹢﹢库中的算法相比，AlphaDev的新算法在对短序列元素进行排序时效率提高了70%，对超过25万个元素的序列排序效率提高了约1.7%。目前，新算法已经开源并纳入常用的Libc ﹢﹢库中。DeepMind表示，这是十多年来C﹢﹢排序算法库部分的首次更新。

　　排序算法是计算机领域极为基础的“主力”算法之一，用于将一串数据按照特定的顺序进行排列。常见的歌单列表、图像处理等都离不开排序算法，其应用场景还包括直播间“买买买”、云计算集群任务处理等，不夸张地说，排序算法每天会被调用上亿次。

　　近些年来，诸如冒泡排序、插入排序、堆排序等许多不同的排序算法得到了高度优化，因而排序算法的创新空间十分有限。“我们真的没想到能取得如此好的成绩：这个程序非常简短，这类程序已经被研究了数十年”，DeepMind公司的丹尼尔·曼科维茨（Daniel Mankowitz）说。

　　AlphaDev不是对现有算法进行微调，而是从零开始“创造”，从汇编指令开始“摸索”。它使用汇编语言，这是一种介于程序代码与用0和1编码的二进制指令序列之间的基础语言，具有直接和简洁的特点，可以有效访问、控制计算机的各种硬件设备，占用内存少，执行速度快。DeepMind表示，使用汇编代码让AlphaDev有更多空间来创建更高效的算法。

　　AlphaDev“摸索”算法的过程类似“打怪升级”。该人工智能系统被要求每次构建一条指令，并将输出与已知的正解方案进行对比，从而确保正在创建一个有效的方法。此外，随着难度增加，还会限制执行的步数以及待排序列的长度。DeepMind表示，随着问题规模扩大，这项任务会变得越发困难，因为指令的可能组合数可能逼近宇宙中的粒子总数。

　　曼科维茨表示，元件尺寸正在触及物理极限，工艺研发难度与日俱增，摩尔定律（即单芯片计算能力每隔一段时间就会翻倍）即将走到尽头，但AlphaDev带来的计算效率提升或是应对之道。“这些算法正在被数以万亿次地调用（在软件中运行），我们估计每天都有数以百万计的开发人员和公司在世界各地使用它们。”曼科维茨说，“优化每天被调用数以万亿次的基础代码有望突破摩尔定律放缓的瓶颈。”

　　英国伯明翰大学的马克·李认为，AlphaDev非常有趣，即使只能带来1.7%的速度提升也是有用的。但他表示，即使在其他基础算法中也能做到类似的效率提升，他仍对这种方法能弥补摩尔定律的失效持怀疑态度，因为其在上层软件应用中的效果还有待验证。“相关优化会从排序算法拓展到其他常用算法上，但暂时还无法进一步应用到更复杂的代码上。”他认为，硬件层面的进步和革新仍是主流趋势。

　　（来源：《新科学家》作者：Matthew Sparkes 翻译：吴双）

　　划重点

　　排序算法应用场景

　　在大数据处理中，由于数据量太大，无法一次性加载到内存中进行排序，需要使用外部排序，即将数据分成多个小文件，对每个小文件进行内部排序，然后再将排序好的小文件合并成一个大文件。这种场景下，可以使用归并排序。

　　在机器学习中，有一种名叫KNN（K-Nearest Neighbor）的分类算法，它的思想是根据一个样本最近的K个邻居的类别来判断该样本的类别。这种场景下，可以使用快速排序找到第K小或第K大的元素。

　　在图像处理中，有一种叫作中值滤波的方法，其原理是用一个像素点周围K个像素值的中值来替换该像素点的值，从而去除噪声。这种场景下，可以使用堆排序，因为它可以高效地维护一个大小为K的最小堆或最大堆，从而快速地找到中值。关于深度强化学习（DRL）DRL是Deep Reinforce-ment Learning（深度强化学习）的缩写，是强化学习（Reinforcement Learning）和深度学习（Deep Learning）的结合。

　　DRL是一种端对端（endto-end）的感知与控制系统，具有很强的通用性。其学习过程可以描述为：

　　1.在每个时刻通过与环境交互得到一个高维度的观察，并利用深度学习方法来感知观察，以得到具体的状态特征表示；

　　2.基于预期回报来评价各动作的价值函数，并通过某种策略将当前状态映射为相应的动作；

　　3.环境对此动作做出反应，并得到下一个观察；

　　4.通过不断循环以上过程，最终可以得到实现目标的最优策略。

　　总的来说，深度强化学习通过不断试错和反馈学习的方式，逐步调整自身的策略，以获得更好的性能。