网站建设费用包括,怎么让关键词快速上首页,微信公众号怎么创建文章,wordpress 手机pc来源#xff1a;MIT#xff0c;新智元编辑#xff1a;David【导读】随着摩尔定律走向终结#xff0c;靠提升计算机硬件性能可能越发难以满足海量计算的需要#xff0c;未来的解决之道在于提升算法的效率。MIT的这篇新论文总结了过去80年来#xff0c;算法效率的提升究竟有… 来源MIT新智元编辑David【导读】随着摩尔定律走向终结靠提升计算机硬件性能可能越发难以满足海量计算的需要未来的解决之道在于提升算法的效率。MIT的这篇新论文总结了过去80年来算法效率的提升究竟有多快。提起算法它有点像计算机的父母它会告诉计算机如何理解信息而计算机反过来可以从算法中获得有用的东西。算法的效率越高计算机要做的工作就越少。对于计算机硬件的所有技术进步以及备受争议的摩尔定律的寿命问题来说计算机硬件的性能只是问题的一方面。而问题另一方面则在硬件之外算法的效率问题。如果算法的效率提升了对同一计算任务需要的算力就会降低。虽然算法效率问题可能不太受关注但你是否注意到经常使用的搜索引擎是否突然变快了十分之一而在大型数据集中活动就感觉就像在泥泞中跋涉一样艰难缓慢。这些都与算法效率有关。近日麻省理工学院计算机科学与人工智能实验室 (CSAIL) 的科学家提出疑问算法效率的提升速度到底有多快关于这个问题现有数据大部分是叙事性的其中很大一部分是面向特定算法的案例研究再把这些研究结果加以推广。面对实证研究数据的不足研究团队主要利用了来自 57 部教科书和 1110 多篇研究论文的数据以追溯算法效率提升的历史。其中有些论文的结论中直接给出了新的算法有多高效有的论文则需要作者使用“伪代码”对算法基本细节的简单描述进行重构。研究人员总共研究了 113 个“算法系”即解决计算机科学教科书中最重要的同一问题的算法集。他们对每个算法族的历史进行了回顾跟踪每次针对某一问题提出的新算法并特别注意更高效的算法。图1 算法发现和改进。(a) 每十年发现的新算法系的数量。(b) 已知算法系的比例每十年都有所提高。(c) 首次发现时算法系的渐近时间复杂度分类。(d) 同一时间复杂度的算法转换到另一个时间复杂度的每年平均概率反应算法系复杂度提升的平均水平。在c和d中“n3”的时间复杂度表示超过多项式级但不到指数级。最早的算法系可追溯到上世纪40年代每个算法系平均有 8 个算法按时间顺序效率逐步提升。为了共享这一发现团队还创建了“算法维基”页面Algorithm-Wiki.org。研究人员绘制了图表标识这些算法族效率提升的速度重点关注算法分析最多的特征——这些特征往往决定了解决问题的速度有多快用计算机术语说就是“最坏情况下的时间复杂度”。图 2 算法系的相对效率提升使用渐近时间复杂度的变化计算。参考线是SPECInt 基准性能。(a) 与该系列中的第一个算法n 100 万相比四个算法系的历史改进。(b) 算法改进对“最近邻搜索”算法系列的输入大小 (n)的敏感度。为了便于比较算法改进效果随时间的变化在图(b) 中将算法系和硬件基准的起始时间段对齐。结果显示变数很大但也发现了关于计算机科学变革性算法效率提升的重要信息。即对于大型计算问题43% 的算法系的效率提升带来的收益不低于摩尔定律带来的收益。在 14% 的问题中算法效率提升的收益远超硬件性能提升的收益。 对于大数据问题算法效率提升收益特别大因此近年来这一效果与摩尔定律相比越来越明显。当算法系从指数复杂度过渡到多项式复杂度时情况出现了最大的变化。所谓指数复杂度算法就像一个人猜密码锁的密码一样。如果密码盘上只有一位数那么任务很简单。如果像自行车锁一样表盘是4位数估计你的自行车很难有人偷得走但仍然可以一个个试。如果是表盘是50位的就几乎不可能破解了需要的步骤太多了。图3 基于渐近时间复杂度计算的110个算法系效率提升的年平均速度分布其中问题规模为(a) n 1000(b) n 100万(c) n 10亿。硬件性能提升线表示从 1978 年到 2017 年SPECInt 基准性能的平均年增长率这类问题也是计算机面对的难题随着问题的规模越来越大很快就会超过计算机的处理能力这个问题光靠摩尔定律是解决不了的。解决之道在于找到多项式复杂度的算法。研究人员表示随着摩尔定律终结这个话题越来越多地被提及我们需要将未来的解决方案的重点放在算法的效率提升上。图4 前导常数在算法性能提升中的重要性评价研究结果表明从历史上看算法效率的提升带来的收益是巨大的。不过二者之间存在着频度的差异摩尔定律带来的提升是平滑而缓慢的而算法效率的提升是阶梯式的跃进但出现没那么频繁。本文通讯作者尼尔·汤普森说这是业界第一篇说明算法效率提升速度的论文。通过我们的分析可以得出算法改进后使用同样的算力可以完成多少任务。随着问题的规模不断增大比如达到数十亿或数万亿个数据点算法效率的提升带来的收益比硬件性能的提升更重要而且重要得多。在我们开始逐步为算力不足发愁的时代在摩尔定律越来越显出疲态的今天这一发现可能为未来解决超大型计算问题开辟一条新的思路。参考链接https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920https://ieeexplore.ieee.org/stamp/stamp.jsp?tparnumber9540991未来智能实验室的主要工作包括建立AI智能系统智商评测体系开展世界人工智能智商评测开展互联网城市大脑研究计划构建互联网城市大脑技术和企业图谱为提升企业行业与城市的智能水平服务。每日推荐范围未来科技发展趋势的学习型文章。目前线上平台已收藏上千篇精华前沿科技文章和报告。 如果您对实验室的研究感兴趣欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”
