算法信仰的力量：改进算法能提升多少性能？
source link: https://www.jdon.com/57412
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
与硬件的摩尔定律相比：摩尔定律的硬件改进会随着时间的推移顺利进行，而对于算法而言，带来的收益虽然会很大但是发生的概率机会很小。
为了让人们坚信对算法的信仰，麻省理工学院计算机科学与人工智能实验室 (CSAIL) 的科学家开始研究：算法改进能提升多少性能？
该团队着手处理来自 57 部教科书和 1,110 多篇研究论文的数据，以追溯算法何时变得更好的历史。一些研究论文直接报告了新算法有多好，而其他研究论文需要作者使用“伪代码”（描述基本细节的算法的速记版本）进行重构。
该团队总共研究了 113 个“算法家族”，即解决计算机科学教科书中最重要的同一问题的算法集。对于 113 个中的每一个，该团队都重建了它的历史，跟踪每次针对该问题提出的新算法，并特别注意那些更有效的算法。从 1940 年代到现在，从性能上看，相隔几十年，该团队发现每个系列平均有 8 个算法，其中有几个提高了效率。为了共享这个组装的知识数据库，该团队还创建了 Algorithm-Wiki.org。
科学家们绘制了这些家族改进的速度，重点关注算法分析最多的特征——它们能保证解决问题的速度有多快（用计算机的话说：“最坏情况时间复杂度”）：
- 结果是：有很大的可变性（不确定性）。
但也有关于计算机科学变革性算法改进的重要见解：
- 对于大型计算问题，43% 的算法系列的同比改进等于或大于摩尔定律带来的收益；
- 在 14% 的问题中，算法对性能的改进大大 超过了硬件改进带来的改进。对于大数据问题，算法改进带来的收益特别大，因此这些改进的重要性在近几十年来不断增加。
研究人员表示：随着摩尔定律即将结束的传言（注意这是传言）迅速渗透到全球对话中，计算用户将越来越需要转向算法等领域来提高性能。该团队表示，研究结果证实，从历史上看，算法带来的收益是巨大的，因此潜力是存在的。（banq注：潜力总是存在的，当然更可能被量子计算这样硬件迅速超越）
研究人员表示：随着问题增加到数十亿或数万亿个数据点，算法改进变得比硬件改进重要得多。在计算的环境足迹越来越令人担忧的时代，这是一种改善企业和其他组织而没有负面影响的方法。
汤普森与麻省理工学院访问学生 Yash Sherry 一起撰写了这篇论文。该论文发表在IEEE Proceedings 上。这项工作由 Tides 基金会和麻省理工学院数字经济计划资助。
banq注：这也是搞人工智能机器学习的公司最终会设计芯片的原因。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK