当前位置:首 页 > IT客 > 查看文章

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

IT客 你是第2714个围观者 9条评论 供稿者: 标签:

本文翻译自程序员的问答社区 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 的运算能力在脱缰野马一般增长的需求面前,因为各种原因没有得到有效的利用,算法的重要性离死还远着呢。

这家伙很懒,什么都没写!

—— zhaorong

zhaorong
你可能也喜欢Related Posts
众说纷纭Comments
大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头
小提示:直接粘贴图片到输入框试试
努力发送中...
  1. 1 楼 易小艺

    第一次来访,表示支持
    yv2bv2
    癸巳年(蛇)九月十四 2013-10-18

    2013年10月18日 12:26:31 回复 取消回复
    • zhaorong
      1楼 - 楼中楼 zhaorong

      表示欢迎和感谢!

      2013年10月18日 12:53:53 回复 取消回复
  2. 2 楼

    以前我们学校进行军训。 教官对学生A喊道:第一排,报数!A莫名其妙的看了教官一眼,没动。教官再次对A喊:第一排报数!A不知所措的看着教官,还是没动。教官火了,指着A大喊一声:第一排,报数!!!当然这不是GC,GC是那丫的竟然慢吞吞的走过去神色无奈的把树抱的死死的。你想长毛吗?

    2014年01月17日 01:37:53 回复 取消回复
  3. 3 楼

    梦,总不够漫长,可是我们需要梦想;情,总让人受伤,可是我们还念念不忘;雨,下的再漂亮,但我们还是喜欢阳光!你,虽然不在我身旁,但从未将你遗忘……

    2014年01月19日 08:03:48 回复 取消回复
  4. 4 楼

    昨天逛超市,看到一对小情侣,不知为什么吵了起来。男的就骂女的:sao逼。结果女的说:那你还舔!当时所有人都愣了!用这根比较灵活!

    2014年01月20日 01:09:06 回复 取消回复
  5. 5 楼 访客

    岂在朝朝暮暮

    2014年01月21日 04:38:44 回复 取消回复
  6. 6 楼 访客

    心在飞扬,情在高昂。平安夜让我们一起,去聆听圣诞的钟声好吗?、世人都崇尚母亲的爱,再也没有什么比母亲更伟大。

    2014年01月23日 01:59:14 回复 取消回复
  7. 7 楼 访客

    1、英语老师:杀鸡给猴看,猴看多了,也就不怕了。 2、老师:煤为什么做成蜂窝状的呀? 学生 :因为它是蜂窝煤 3、有个人被狗咬伤,赶忙到医生那里上药。医生正收拾东西,准备下班。 “看看几点了,我要下班了、怎么这时候才来?”医生满脸不快。 “我是知道的医生,”那人说,“可是,狗不懂下不下班啊!”4、说个真的,有一年夏天我们开会没空调,大家建议比赛说凉快话,看谁能让人凉快。我说:咱们这儿怎么跟太平间似的? 5、女主人从外面回来,问新来的女佣:“你有没有照我的吩咐,把冰箱清理干净?”“清理过了,太太。”女佣回答,“每样东西都很好吃!”6、领导批人了,被罚将报纸的字一个一个用剪刀剪下来,剪到500多的时候已经头昏眼花了。这时领导发话,将这些字拼回去……7、少先队大队会,高年级的姐姐问我的同桌:你的职务(植物)是什么?同桌很认真的答:我就养了棵仙人掌,本来还想养个含羞草的。8、一哥们去书摊,张狂地问老板:“有刘备吗?” 另人纳闷,只见老板从角落翻出两本黄…书递了过来。回去的路上另人问:“黄书为什么叫 ‘刘备’ 呀?” 他悄声说:”皇叔”。9、负责ICU的一个护士和另一个护士说:床位太紧了,外面的都安排不过来了。另一个说:不用急,你看这个、那个、和那边那个,都差不多了,过不了今晚的……很快就有地方了……10、(天上人间被查) 最失望:人生一下子失去了奋斗目标!最理智:免费打广告呢!最纳闷:这些p.o.l.i.c.e们经常来光顾,怎么今天都装不认识了?最义愤:天上人间都查,还有王法吗?最无厘头:一直以为它是事业单位。最忧国忧民:又下岗这么多人… 最令人信服:世博会缺人了,北女南调。11、那阵子有点心悸,去做心电图,结果出来没什么问题。一个老医生先是用深不可测眼光看着我,然后叹气,摘下眼镜,用手指摁着太阳穴,说:你是不是想逃学啊…… 12、病人:医生,我看不清(我这儿是眼科) 医生:看那么清楚干嘛搞笑夫妻

    2014年02月10日 10:52:46 回复 取消回复
  8. 8 楼 访客

    LZ突然发现哥原来是一屌丝,军训这两天哥认识一妹子,长得那气质是没有话说。昨天看到她一天唔着肚子,有气无力。我就说:“肚子痛”?她回答说:“嗯,今天肚子有点痛”。哥以为她大姨妈来了,就想关心一下,就说了一句。你回去炖点骨头汤喝,多喝点红糖水。她听后,结果她就追着我打,还边跑边说:“吃东西吃坏肚子了,你居然这么想我,我要杀了你”。我在奇怪前面有气无力的,后面哪来的力气追我,女人真是琢磨不透。本人兼职光谷国际匡威卖鞋子

    2014年03月17日 08:51:07 回复 取消回复
  • 评论最多
  • 最新评论
  • 随机文章
footer logo
未经许可请勿自行使用、转载、修改、复制、发行、出售、发表或以其它方式利用本网站之内容
Copyright © zhaorong All Rights Reserved. 滇ICP备15006105号-1