算法改进可以击败摩尔定律

麻省理工学院新闻说,算法有点像计算机的父母。他们告诉计算机如何理解信息,以便他们可以从中获得有用的东西。

麻省理工学院新闻说,算法有点像计算机的父母。他们告诉计算机如何理解信息,以便他们可以从中获得有用的东西。

算法效率越高,计算机的工作就越少。对于计算硬件的所有技术进步以及摩尔定律的争议寿命,计算机性能只是图片的一侧。

在幕后,第二种趋势正在发生:算法正在改善,因此需要更少的计算能力。虽然算法效率可能会降低焦点,但您肯定会注意到您可信赖的搜索引擎是否突然成为十分之一,或者通过大数据集移动,感觉就像在污泥中涉水。

这导致了麻省理工学院计算机科学和人工智能实验室(CSAIL)的科学家问:算法的改善速度如何?

关于这个问题的现有数据在很大程度上是轶事,包括对特定算法的案例研究,这些算法被认为是代表更广泛范围的特定算法。面对这一证据,该团队开始从57本教科书和1,110多个研究论文中进行处理,以追踪算法何时变得更好的历史。一些研究论文直接报道了新算法的良好程度,而另一些研究论文则需要使用“伪代码”(描述基本细节的算法的速记版本)对作者重建。

总的来说,该团队研究了113个“算法家庭”,这些算法解决了相同的问题,该问题被计算机科学教科书最重要。对于113个中的每一个,团队都重建了其历史,每次提出了新算法的问题,并特别注意那些更有效的算法。从1940年代到目前,该团队的性能范围为数十年,平均每个家庭发现了八种算法,其中一对夫妇提高了其效率。为了分享这个集会的知识数据库,团队还创建了算法 – wiki.org。科学家们绘制了这些家庭的进步速度,重点是算法的最分析功能 – 他们可以保证解决问题的速度(在计算机说:“最差的时间复杂性”)。出现的是巨大的可变性,但同时也对计算机科学的变革算法改进如何改进的重要见解。

对于大型计算问题,有43%的算法家庭的同比改善等于或大于摩尔法律的较高的收益。在14%的问题中,算法对性能的改善大大增加了来自硬件改进的算法。对于大数据问题,算法改进的收益特别大,因此这些进步的重要性在近几十年来增长。

作者观察到的最大变化是当算法家族从指数转变为多项式复杂性时。解决指数问题所需的努力就像一个试图在锁上猜测组合的人一样。如果您只有一个10位数字表盘,那么任务很容易。有四个表盘之类的自行车锁,很难偷您的自行车,但是仍然可以想象您可以尝试每种组合。有了50个,这几乎是不可能的 – 这将需要太多步骤。对于计算机而言,具有指数复杂性的问题就是这样:随着它们变大,它们很快就超过了计算机处理它们的能力。找到多项式算法通常可以解决这一问题,从而可以以无法改进的硬件改进的方式解决问题。随着摩尔定律的隆隆声迅速弥漫在全球对话中,研究人员表示,计算用户将越来越需要转向转向到诸如算法之类的领域,以提高性能。该团队说,调查结果证实,从历史上看,算法的收益是巨大的,因此潜力存在。但是,如果收益来自算法而不是硬件,它们看起来会有所不同。随着时间的流逝,摩尔定律的硬件改进会顺利进行,对于算法,收益以通常很大但很少经常出现的步骤出现。

“这是第一篇展示算法在广泛示例中进步的速度的论文,” CSAIL和斯隆管理学院的麻省理工学院研究科学家尼尔·汤普森(Neil Thompson)说,新论文的高级作者。“通过我们的分析,我们可以说在改进算法后,使用相同数量的计算能力可以完成多少任务。随着问题增加到数十亿或数万亿个数据点,算法改进比硬件改进更为重要。在一个越来越令人担忧的计算环境足迹的时代,这是一种改善企业和其他没有弊端的组织的方式。该论文发表在IEEE会议记录中。这项工作是由潮汐基金会和MIT倡议资助的。

在麻省理工学院新闻的允许下重新发布。阅读原始文章。

原创文章,作者:大天,如若转载,请注明出处:http://www.dsonekey.com/3062.html

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息