科学家们展示了算法在广泛示例中的改进速度

算法有点像计算机的父母。它们告诉计算机如何理解信息，以便它们反过来可以从中获得有用的东西。算法效率越高，计算机要做的工作就越少。对于计算硬件的所有技术进步，以及备受争议的摩尔定律寿命，计算机性能只是问题的一方面。

在幕后，第二个趋势正在发生：算法正在改进，因此需要更少的计算能力。虽然算法效率可能不太受关注，但您肯定会注意到，您值得信赖的搜索引擎是否突然变得快了十分之一，或者在大型数据集中移动时感觉像是在泥泞中跋涉。

这让麻省理工学院计算机科学与人工智能实验室(CSAIL)的科学家提出疑问：算法改进的速度有多快?

关于这个问题的现有数据主要是轶事，由特定算法的案例研究组成，这些算法被假定为代表更广泛的范围。面对证据的缺乏，该团队着手处理来自57部教科书和1,110多篇研究论文的数据，以追溯算法何时变得更好的历史。一些研究论文直接报道了新算法有多好，而其他研究论文需要作者使用“伪代码”(描述基本细节的算法的速记版本)进行重构。

该团队总共研究了113个“算法家族”，即解决计算机科学教科书中最重要的同一问题的算法集。对于113个中的每一个，该团队都重建了它的历史，跟踪每次针对该问题提出的新算法，并特别注意那些更有效的算法。从1940年代到现在，从性能上看，相隔几十年，该团队发现每个系列平均有8个算法，其中有几个提高了效率。为了共享这个组装的知识数据库，该团队还创建了Algorithm-Wiki.org。

科学家们绘制了这些家族改进的速度，重点关注算法分析最多的特征——它们能保证解决问题的速度有多快(用计算机的话说：“最坏情况时间复杂度”)。出现的是巨大的可，但也有关于计算机科学变革性算法改进的重要见解。

对于大型计算问题，43%的算法系列的同比改进等于或大于备受吹捧的摩尔定律带来的收益。在14%的问题中，算法对性能的改进大大超过了硬件改进带来的改进。对于大数据问题，算法改进带来的收益特别大，因此这些改进的重要性在近几十年来不断增加。

当算法系列从指数复杂度过渡到多项式复杂度时，作者观察到了最大的变化。解决指数问题所需的工作量就像一个人试图猜测锁上的密码一样。如果您只有一个10位拨号，则任务很简单。像自行车锁一样有四个刻度盘，很难有人偷你的自行车，但仍然可以想象你可以尝试每一种组合。如果是50，那几乎是不可能的——这需要太多的步骤。具有指数复杂性的问题就像计算机一样：随着它们变得越来越大，它们很快就会超过计算机处理它们的能力。找到多项式算法通常可以解决这个问题，从而可以以硬件改进无法解决的方式解决问题。

随着摩尔定律即将结束的传言迅速渗透到全球对话中，研究人员表示，计算用户将越来越需要转向算法等领域来提高性能。该团队表示，研究结果证实，从历史上看，算法带来的收益是巨大的，因此潜力是存在的。但如果收益来自算法而不是硬件，它们看起来就会不同。摩尔定律的硬件改进会随着时间的推移顺利进行，并且对于算法而言，收益通常会很大但很少发生。

“这是第一篇展示算法在广泛示例中改进速度有多快的论文，”CSAIL和斯隆管理学院的麻省理工学院研究科学家、新论文的资深作者尼尔汤普森说。“通过我们的分析，我们能够说出在算法改进后使用相同数量的计算能力可以完成多少任务。随着问题增加到数十亿或数万亿个数据点，算法改进变得比硬件改进重要得多。在计算的环境足迹越来越令人担忧的时代，这是一种改善企业和其他组织而没有负面影响的方法。”

汤普森与麻省理工学院访问学生YashSherry一起撰写了这篇论文。该论文发表在IEEEProceedings上。这项工作由Tides基金会和麻省理工学院数字经济计划资助。

标签：