麻省理工学院的科学家提出了第一个系统的、定量的证据，证明算法是计算改进的最重要来源之一。功劳:德贵Adil/ EyeEm算法有点像电脑的家长。他们告诉计算机如何理解信息，这样他们就可以反过来利用这些信息做出有用的东西。算法越高效，计算机需要做的工作就越少。尽管计算机硬件取得了技术进步，摩尔定律的寿命也备受争议，但计算机性能只是其中的一面。
在幕后，第二个趋势正在发生:算法正在改进，因此反过来需要更少的计算能力。虽然算法效率可能没有那么引人注目，但你肯定会注意到，如果你信任的搜索引擎突然变得十分之一快，或者如果在大数据集中移动感觉像在污泥中跋涉。
这让麻省理工学院计算机科学和人工智能实验室(CSAIL)的科学家们提出了一个问题:算法改进的速度有多快？
关于这个问题的现有数据大部分是轶事，包括假设代表更广泛范围的特定算法的案例研究。面对证据的缺乏，该团队着手处理来自57本教科书和1110多篇研究论文的数据，以追溯算法何时变得更好的历史。一些研究论文直接报道了新算法有多好，其他的需要由作者使用“伪代码”来重建，伪代码是描述基本细节的算法的简写版本。
该团队总共研究了113个“算法家族”，这些算法解决了计算机科学教科书中强调为最重要的同一问题。对于这113个问题中的每一个，研究小组都重建了它的历史，跟踪每一次针对这个问题提出的新算法，并特别注意那些效率更高的算法。从20世纪40年代到现在，该团队发现每个家庭平均有八种算法，其中一对夫妇提高了效率。为了共享这个集合的知识数据库，该团队还创建了Algorithm-Wiki.org。
科学家们绘制了这些家族进步的速度，重点是算法中分析最多的特征——他们能保证多快解决问题(用计算机的话说:“最坏情况下的时间复杂度”)。出现的是巨大的可变性，但也是关于算法改进对计算机科学的变革性的重要见解。
对于大型计算问题，43%的算法家族的同比改进等于或大于从摩尔定律中获得的备受吹捧的收益。在14%的问题中，算法对性能的改善远远超过了硬件的改善。算法改进带来的收益对于大数据问题来说尤其巨大，因此这些进步的重要性在最近几十年有所增长。
作者观察到的最大变化是算法族从指数复杂度过渡到多项式复杂度。解决指数问题所需的工作量就像一个人试图猜测一把锁的密码。如果你只有一个10位数的拨号盘，这个任务很简单。有了像自行车锁一样的四个表盘，很难没有人偷你的自行车，但仍然可以想象你可以尝试每一种组合。50岁，这几乎是不可能的——这将需要太多的步骤。具有指数复杂性的问题就像计算机的问题一样:随着它们变得越来越大，它们的速度远远超过了计算机处理它们的能力。找到一个多项式算法通常可以解决这个问题，使解决问题成为可能，这是任何硬件改进都无法做到的。
随着摩尔定律即将结束的传言迅速渗透到全球对话中，研究人员表示，计算用户将越来越需要转向算法等领域来提高性能。该团队表示，这些发现证实，从历史上看，算法的收益是巨大的，因此潜力是存在的。但是如果收益来自算法而不是硬件，它们看起来就会不同。随着时间的推移，摩尔定律带来的硬件改进会顺利进行，对于算法来说，这种改进通常是大幅度的，但并不频繁。
CSAIL和斯隆管理学院的麻省理工学院研究科学家、这篇新论文的资深作者尼尔·汤普森(Neil Thompson)说:“这是第一篇展示算法在广泛的例子中如何快速改进的论文。“通过我们的分析，我们能够说出在算法改进后，使用相同的计算能力可以完成多少更多的任务。随着问题增加到数十亿或数万亿个数据点，算法改进变得比硬件改进重要得多。在一个计算的环境足迹越来越令人担忧的时代，这是一种改善企业和其他组织而没有负面影响的方式。”
汤普森和麻省理工学院的访问学生雅什·雪莉一起写了这篇论文。这篇论文发表在《电气和电子工程师协会学报》上。这项工作由潮汐基金会和麻省理工学院数字经济倡议资助。
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
