采用正确的算法和数据结构

Use the Right Algorithm and Data Structure

一家用于众多分行的大型银行他们给出纳新采购的电脑实在太慢了。那个时候还没有电子银行,也不想现在到处都是ATM机。人们会经常去银行办理业务,由于电脑慢导致人们排起长队。因此,这家银行向供应商威胁要终止合同。

供应商急忙发送一份性能分析,为了查明延迟原因还派遣了一名专家过去。他立刻就发现跑在终端的一段特殊代码几乎耗尽了CPU资源。通过图表分析工具,他放大了这段程序,并看到了这个罪魁祸首的函数。源码大致为:

1
2
3
for (i=0; i<strlen(s); ++i) {
if (... s[i] ...) ...
}

而且字符串s平均都有上千个字符。这段代码(银行写的)很快变更正了。从此以后银行的出纳员过上了幸福快乐的生活。

相对于使用不必要的嵌套扩展代码,程序员不应该做得更好吗?

每次调用strlen传递的每个字符上千遍,知道字符串发现null结束符。然后这期间该字符串就从未变化过。为了进一步使用它的长度,程序员可以先吊用strlen并将其保存(并把它执行个几百万次):

1
2
3
4
n=strlen(s);
for (i=0; i<n; ++i) {
if (... s[i] ...) ...
}

每个人都知道这个格言:“先让它跑起来,再让他快起来”,才能避免微优化陷阱。但上边的例子似乎让你相信,程序员遵循的是Machiavellian格言:“先让它慢慢跑吧”。

你可能遇到过不止一次这种欠考虑的事情。这不仅仅是“不要重新发明轮子”的事情。有时候初级程序员只是再打字而非思考,当他们突然间“发明”了冒泡排序时。他们甚至会开始吹嘘它。

选择正确算法的另一面就是数据结构的选择。这会有很大的不同:采用链表来遍历一个用于百万个项的集合(相比较哈希数据结构或二叉树),用户对你程序的评价都会产生很大的影响。

程序员不应该重新发明轮子,应该尽可能使用现有库。但为避免像上面那家银行的问题,他们也该学习有关算法以及它们如果扩展。现代令人眼花缭乱的文本编辑器会让它们变得像1980年代的WordStar一样慢么?很多人说程序中的复用很重要。然而综上考虑,程序员应该要知道何时、何处、如何服用。为了完成这个,他们应该具备这些问题域喝算法及数据结构的相关知识。

一个好的程序员也应该知道什么时候该用一种平庸的算法。例如,如果问题域是永远不会有超过5个项的算法(例如快艇骰子游戏),你就知道你必须进行5个元素的排序。对于这种案例,冒泡排序实际上会比绝大多数其它排序方法都更高效。每条狗都会有自己的一天。

所以,阅读一些好书吧——要确保你理解它们。如果你真的看过Donald Knuth
的《计算机程序设计技术》,很好,祝你好运:发现作者的一个错误,你就能得到十六进制美元($2.56)支票。

0%