算法信仰的力量:改进算法能提升多少性能?

21-10-18 banq

与硬件的摩尔定律相比:摩尔定律的硬件改进会随着时间的推移顺利进行,而对于算法而言,带来的收益虽然会很大但是发生的概率机会很小。

为了让人们坚信对算法的信仰,麻省理工学院计算机科学与人工智能实验室 (CSAIL) 的科学家开始研究:算法改进能提升多少性能?

该团队着手处理来自 57 部教科书和 1,110 多篇研究论文的数据,以追溯算法何时变得更好的历史。一些研究论文直接报告了新算法有多好,而其他研究论文需要作者使用“伪代码”(描述基本细节的算法的速记版本)进行重构。

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

科学家们绘制了这些家族改进的速度,重点关注算法分析最多的特征——它们能保证解决问题的速度有多快(用计算机的话说:“最坏情况时间复杂度”):

  • 结果是:有很大的可变性(不确定性)。

但也有关于计算机科学变革性算法改进的重要见解:

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

研究人员表示:随着摩尔定律即将结束的传言(注意这是传言)迅速渗透到全球对话中,计算用户将越来越需要转向算法等领域来提高性能。该团队表示,研究结果证实,从历史上看,算法带来的收益是巨大的,因此潜力是存在的。(banq注:潜力总是存在的,当然更可能被量子计算这样硬件迅速超越)

研究人员表示:随着问题增加到数十亿或数万亿个数据点,算法改进变得比硬件改进重要得多。在计算的环境足迹越来越令人担忧的时代,这是一种改善企业和其他组织而没有负面影响的方法。

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

 

banq注:这也是搞人工智能机器学习的公司最终会设计芯片的原因。

特斯拉人工智能Dojo概述

3
猜你喜欢