使用正确的算法和数据结构
本文翻译自”Use the Right Algorithm and Data Structure“，来自于《程序员应该知道的97件事》一书中的某个章节。
一家拥有多个分行的大银行抱怨说他们为出纳员新买的计算机运行得太慢了。这件事儿发生在电子银行以及ATM机使用普及程度远不及现在的那个年代。人们更多的是亲自到银行办理业务，这些运行超慢的计算机使得大家排起了长队。因此，这家银行威胁计算机供货商要结束他们之间的供货合同。
计算机供货商派出了一个性能分析和调优专家查找计算机运行缓慢的原因。这个专家很快就发现了一个运行在终端的特定程序几乎消耗掉了CPU的所有处理能力。他使用了一个程序分析工具将程序展开，并找到了那个导致计算机运行缓慢的罪魁祸首。其源码如下：
for (i = 0; i < strlen(s); ++i) {
if (… s[i] …) …
}
这里的字符串s的平均长度有上千个字符。这段代码（由这个银行编写的）很快被修正了，并且这家银行的出纳员自从那以后工作得很开心…
难道程序员不应该做得更好一些并且不去使用那些无用的二次阶复杂度算法吗？
每次strlen调用都会遍历字符串中上千个字符里的每个字符以找到字符串的结尾null字符。不过，这个字符串永远不会改变。如果事先得到该字符串的长度，这个程序员本可以节省数千次对strlen的调用（以及数百万次循环的执行）：
n = strlen(s);
for (i = 0; i < n; ++i) {
if (… s[i] …) …
}
每个人都知道这句格言：“首先使其能工作，然后再考虑让其更高效地工作”，这可以避免微小优化导致的缺陷。不过上面的例子几乎可以让你相信这个程序员遵循的是权谋家的节拍“首先使其缓慢地工作”。
这种草率的事情你可能不止遇到过一次。这不仅仅是一件“不要重新发明轮子”的事情。有些时候新手程序员在没有仔细考虑的前提下就开始写代码，然后突然意外地“发明”了冒泡排序。他们甚至可能为其自夸一番。
选择正确算法的另外一方面是数据结构的选择。这会导致很大的差异：用一个链表表示你要搜索的一个具有百万项元素的集合-与用一个哈希数据结构或一个二叉树相比-这会对用户对你的编程能力的评价产生较大影响。
程序员不应该重新发明轮子，并且应该尽可能地使用现有的库。但是为了能避免类似上面银行发生的问题，他们应该进行一些有关算法以及算法规模评估的培训。难道这只是现代文本编辑器中的华而不实才使得他们运行起来就像是上世纪80年代的老程序一样缓慢吗，比如WordStar？许多人说编程中的重用是最为重要的。不过，最重要的是，程序员应该知道何时重用、重用什么以及如何重用。为了做到这些，他们必须拥有问题域以及算法和数据结构的知识。
一个优秀的程序员也应该知道何时使用一个性能较差的算法。比如，如果问题域规定永远不会多于五个元素（就像是在掷骰子游戏中骰子的个数），你知道始终最多对5个元素进行排序。在这种情况下，冒泡排序实际上也许才是进行排序的最高效的方式。每个人都有得意的那天。
所以，阅读一些好书 – 并且确保你理解了书中所讲的内容。如果你真地读过Donald Knuth的“计算机编程艺术”，你也许甚至很幸运：找到一处作者犯下的错误都可以得到Donald Knuth的面额为2.56美元的支票。
© 2011, bigwhite. 版权所有.
Related posts:
评论