DIY编程器网

标题: 追求算法已经不再重要？ [打印本页]

作者: admin 时间: 2014-10-12 16:26
标题: 追求算法已经不再重要？
追求算法（特别是普遍高效的）已经不再重要？因为现在计算机硬件的成本，比起以前已经很便宜，是否意味着算法和改进算法的技能已经不那么重要了？大部分时候，只要别写出一个死循环就行了。但当你拥有了强悍的硬件，是不是意味着烂代码也不是什么大问题？

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

我们来比较两种排序算法：“插入排序”和“归并排序”。他们的算法复杂度分别是O（n2）=c1n2和O（nlogn）=c2nlgn.一般情况下，归并排序算法有一个更大的常数因子，所以我们假设c1<c2。

为了回答你的问题，我们在一台时髦的高速电脑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内核和再高的主频都无法给你带来和算法改进一样的回报。

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

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

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

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

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

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

欢迎光临 DIY编程器网 (http://diybcq.com/)