MIT新研究:43%算法改进速度超摩尔定律,解决超大规模问题,算法比硬件更有用

软件算法对计算速度的提升有多大?MIT最新研究说:超过4成算法对性能的改进,已经超过了硬件的摩尔定律。对于中等规模的问题,30%-43%的算法的改进比硬件进步更能提升性能。当问题数据增加到数亿规模时,算法改进变得比硬件改进/摩尔定律更重要。这就是MIT的两位科学家对来自57本

NetSmell 出品

  软件算法对计算速度的提升有多大?

  MIT 最新研究说:超过 4 成算法对性能的改进,已经超过了硬件的摩尔定律。

  对于中等规模的问题,30%-43% 的算法的改进比硬件进步更能提升性能。

  当问题数据增加到数亿规模时,算法改进变得比硬件改进/摩尔定律更重要。

  这就是 MIT 的两位科学家对来自 57 本教科书,超过 1137 篇研究论文的数据进行分析后得到的结论。

  不仅如此,他们还全面叙述了现有以及历史上的算法何时被发现、如何改进、以及改进的规模。

  14% 的算法改进率超过 1000%

  研究者通过分析 QS 排名中前 20 的计算机名校所用的课件,总结出 11 个算法子领域:

  组合学、统计学/机器学习、密码学、数值分析、数据库、操作系统、计算机网络、机器人学、信号处理、计算机图形/图像处理、生物信息学。

  通过分析子领域中的算法教材、学术期刊、已发表论文等信息,研究者划分出了 113 个算法家族,平均每个家族 8 个算法。

  他们首先统计了从 1940 年到现在,各种算法的最初提出时间:

  并且根据这些算法最初被提出时的时间复杂度进行了归纳。可以看到,其中 31% 的算法属于指数复杂度类别:

  在时间复杂度的改进上,对于n=100 万的问题规模,一些算法比硬件或摩尔定律的改进率更高:

  △算法改进对四个算法家族的影响

  将这一分析拓展到 110 个算法家族上时,可以看到,对于中等规模(n=1000)的问题来说,只有 18% 的算法改进率快于硬件。

  但当问题规模来到了百万、亿、甚至万亿级别时,算法的改进速度就超过了硬件性能。

  甚至有 14% 的算法家族的改进率超过 1000%,远超硬件改进所带来的性能提升。

  △a:n=一千 b:n=一百万 c:n=一亿

  作者介绍

  论文一作 Yash Sherry 本科毕业于印度德里大学计算机科学专业,现在是 MIT 斯隆商学院的一位研究员,工作重点是跟踪算法的改进及其对 IT 公司经济的影响。

  另一位 Neil Thompson 是麻省理工大学 CSAIL(计算机科学和人工智能实验室)的科学家,也是哈佛大学创新科学实验室的客座教授。

  论文:

  https://ieeexplore.ieee.org/document/9540991

  参考链接:

  https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920

显示余下内容
相关文章:
  1. 苹果面向所有平台发布紧急更新 修复“零点击”高危漏洞
  2. 狗子随地拉屎 人类用DNA技术追踪 狗:你礼貌吗?
  3. OpenBSD 7.0 释出
  4. Linux Kernel 5.14 rc4发布:开发工作顺利 有望如期发布
  5. 超85%人类面临气候危机!他用BERT读10万篇论文:越穷的地方极端天气越多
  6. 曾与华为齐名的国产手机“复活”了 放言三年内重返第一梯队!
  7. Google将推Pixel Pass:在Pixel 6上提供比Apple One更完善的服务
  8. 联想发布启天K系列商用平板家族 并公布了“启明星”计划
  9. 谁在看付费直播?
  10. 英伟达:真正做到虚拟和真实世界交互需5-10年
 

发表评论

您的电子邮箱地址不会被公开。