硬件强悍 算法就不再重要了吗?

jopen 10年前

硬件强悍 算法就不再重要了吗?

        英文原文:Are algorithms (and efficiency in general) getting less important?

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

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

        Pavel Zaichenkov 11 票:我特别喜欢《算法导论》一书中的一个例子,以摧枯拉朽地方法说明了算法性能的重要性。

        我们来比较两种排序算法:“插入排序”和 “归并排序”。他们的算法复杂度分别是 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 秒

        给爪机用户:

硬件强悍 算法就不再重要了吗?

        土鳖电脑 B :

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

        给爪机用户:

硬件强悍 算法就不再重要了吗?

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

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

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

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

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

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

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

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

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

        备注:以上外文原文来自程序员的问答社区 stackexchange.com 上的一个问题。

来自: jandan.net