@ 2013.10.13 , 13:59
64

硬件强悍,算法是否已经不再重要

本文翻译自程序员的问答社区 stackexchange.com 上的一个问题。

[-]

提问:追求算法(特别是普遍高效的)已经不再重要。

因为现在计算机硬件的成本,比起以前已经很便宜,是否意味着算法和改进算法的技能已经不那么重要了?大部分时候,只要别写出一个死循环就行了。但当你拥有了强悍的硬件,是不是意味着烂代码也不是什么大问题?

Pavel Zaichenkov 11 票

我特别喜欢《算法导论(Introduction to Algorithms)》一书中的一个例子,以摧枯拉朽地方法说明了算法性能的重要性:

我们来比较两种排序算法:「插入排序」「归并排序」。他们的算法复杂度分别是 O(n2)=c1n2 和 O(nlogn)=c2n lg n。一般情况下,归并排序算法有一个更大的常数因子,所以我们假设 c1 < c 2。

为了回答你的问题,我们在一台时髦的高速电脑 A 上跑「插入排序」算法,和一台跑「归并排序」算法的老土电脑 B 做对比。

我们假设:

- 输入的问题数据量为 1,000万个数字:n=107;
- 电脑 A 一秒钟可以执行 1010 次运算指令 ( ~ 10GHz );
- 电脑 B 一秒钟只能执行 107 次运算指令 ( ~ 10MHz );
- 常数系数 C1 = 2 (有点夸张),C2 = 50 (比现实中稍微小了一点)

于是在以上假设下,我们得到如下结果:

牛X电脑A:

2·(107)2 次运算1010 次运算/=2·104 秒

IE爪机用户:
[-]

土鳖电脑 B :

50·107lg107 次运算107 次运算/1163 秒

IE爪机蛋友:

[-]

因为有人反映字太小……

所以你看,那部慢了1000倍的电脑,干活速度是快的那台的17倍。而且在现实中,归并算法有更高的效率,特别是随计算量增加的而更加明显。我希望这个答案能回答你的问题。

然而,这还不光是算法复杂程度的问题。在今天,单单想通过提高CPU主频来获得很明显的性能提升是不可能的。我们需要改良算法在多核CPU架构下的表现。而且这是个不太好对付的问题,因为随着内核数量的增加,其他方面的开销正在成为性能的障碍(比如内存访问调度控制)。所以,堆硬件很难获得线性的性能增长。

总而言之,当下对于算法的改进和以前一样重要,因为再多的CPU内核和再高的主频都无法给你带来和算法改进一样的回报。

Yuval Filmus 11票

正相反,随着硬件越来越便宜,新的运算需求正在增加。

首先,我们现在所需要面对和处理的数据正海量增加。这就要谈到「准线性算法(quasilinear time algorithms)」和大数据研究的话题。比如想想搜索引擎的算法设计 —— 它们必须要处理巨量的请求,在茫茫数据中,快速地找到,返回结果,算法的效率比以前更加重要。

其次,「机器学习(machine learning)」的势头正猛,这就是一个算法的世界(可能和你大学本科学的不太一样)。这个领域充满荆棘,但也正是新的算法诞生的地方。

再者,「分布式计算」已经变得非常重要,现在我们在CPU主频提升上已经遇到了瓶颈。如今计算机性能只能通过并行计算来获得提升,这也是算法发挥力量的地方。

最后,为了平衡 CPU/GPU 性能的突飞猛进,大量虚拟机技术被用来抵御安全漏洞的威胁,操作系统花费更多的时间和精力来处理安全威胁和警报,余下的CPU时间才能真正用来做正经事,这让你的程序性能表现有所下降。特别是还有很耗费CPU资源的视频压缩/解压缩计算,虽然计算机硬件性能与日俱增,但使用效率并没有同样提高。

总结一下,对于大数据处理、人工智能领域、分布式计算来说,算法的改进是不可或缺的;CPU 的运算能力在脱缰野马一般增长的需求面前,因为各种原因没有得到有效的利用,算法的重要性离死还远着呢。

本文译自 stackexchange,由译者 Junius 基于创作共用协议(BY-NC)发布。


给这篇稿打赏,让译者更有动力
支付宝打赏 [x]
您的大名: 打赏金额:

2.6
赞一个 (6)

TOTAL COMMENTS: 64+1

[2] 1 »
  1. perfect9000
    @4 years ago
    2218240

    为啥我看成“硬汉强奸,方法已经不重要了”……

  2. 2218233

    @harvie: 是存储资源解决空间复杂度,计算资源就是解决时间复杂度的
    在我学的算法里面,没有说数据越多效率越高的,除非复杂度的阶小于1,当然相对烂算法时间差距会越来越大,但是效率应该不变,我把效率理解为(操作数/数据量)

  3. 肥颓
    @4 years ago
    2218011

    @harvie: 说得对

  4. harvie
    @4 years ago
    2218007

    就好比你是网吧老板,你的机器越多,需要的网管也越多。

  5. harvie
    @4 years ago
    2218006

    “只要计算资源还是有限的,算法就还是重要的。

    只是重要程度的不同吧。”

    不认同,计算资源越是无限,算法越是重要。资源不代表效率。效率高的算法,在资源和数据都逐渐增加时,处理任务的效率会以指数倍数增长。

    计算资源只解决了空间复杂度,在这个“一秒钟几十万上下”的时代,算法更注重时间复杂度。毕竟,资源再怎么无限,电信号的速度是有限的。

    像拥有大型分布式系统的公司如谷歌亚马逊之类,在处理任务时需要更效率,更安全和稳定的“流水线”。

  6. 2217898

    要开程序猿专栏么?

  7. 日理万鸡
    @4 years ago
    2217873

    我喜欢这类型的文章,煎蛋应该开个栏目

  8. 2217842

    做MMORPG的程序都清楚算法的重要性

  9. 2217832

    你们造IE多努力吗

  10. rezilla
    @4 years ago
    2217806

    @cesium14: 手滑敲错了。。。

  11. blueauris
    @4 years ago
    2217709

    这就像下面这个情况:
    我收入大幅增加了,已经算得上是小型土豪了,是不是可以肆无忌惮想买啥就买啥了呢
    答案是NO。
    收入够买脚踏车的时候,大众在前方。够买大众时,玛莎拉蒂在前方,够买玛莎拉蒂时,庞巴迪在前方。够买庞巴迪,挑战者号在前面等着。你连挑战者都买得起?试试土星五如何,总有超出你当前收入水平的消费品存在。
    硬件越提升,数据规模增长越快,目光总是能到达指尖够不到的地方,看得更快更远。

  12. 撸一哥
    @4 years ago
    2217702

    悲剧的安迪比尔定律。当年电脑硬件没这么牛b时,软件也好小,用难度高却运算效率高的语言。现在硬件上去了,还是会狗卡狗卡的,软件动辄几十M上百M,程序员短时间就能写出一堆代码。多核心的问题在于能否充分利用,算法不好就是白费,并行算法要分核,越多核对编程猿也是更高难度,不然一堆数据只能堆到一两个核,其他核心只是在长毛。英特尔的多线程也可能由于不能兼容好同时被多核处理等问题而出错。还有即使说硬件上去,软件要求也一样上去,就像GTA5,要求也会越来越高,硬件根本不会越来越过剩,“三个顶级程序员顶得上上千个程序员” 如乔布斯提出的软硬结合才是王道

  13. 2217689

    摩尔定律到头,材料学甚至量子理论都无法给出进一步提升运算能力的时候,就会对能改进算法的家伙当耶稣一样膜拜

[2] 1 »

发表评论


24H最赞