大道至简--简单与复杂数据结构之间的性能PK

事情源起阿里巴巴的一道笔题.题目大概是要求统计<圣经>中的各个单词出现的次数,按单词首次出现的顺序输出结果.本来没什么技术含量的题,随便用个kv容器都很容易统计单词次数,然后用链表把单词按出现顺序链起来.

结果prince-W同学有点较真,回来还真的写代码.意外地发现了一些很惊讶的东西,他发现这个题用平衡二叉树(bst)实现,效率竟然没有二叉排序树(avl)高,便找我讨论,于是引出了本文.

在我机器上跑的结果:

bst avl 1080000 1280000

bst的代码在这里,还有avl的代码

他是用c++写的代码,递归版本的.我开始怀疑是不是这个案例中bst树没有退化,所以avl体现不出优势来.但是他看了一下树的高度,avl是18层,而bst大概有30多层.

这不科学啊!有点被惊讶到,于是做了些更有趣的研究:我让他去用c++自带的map容器实现一下,而我去写了一个非递归版本avl.因为我看stl源代码时记得c++的map容器是红黑树实现的,而且是非递归版本,我想把递归实现的影响,以及红黑树,都看一下.

我的代码在这里.得到的实验结果更令人惊讶了.我写的非递归的avl速度快了一点点,是1050000.非递归的avl居然只比递归的bst快那么一点点!

而最慢的就是c++的map实现的.c++库中那么精妙的红黑树在这里居然比所有的都慢!

中间我帮他优化了一下代码,他上面有一段大概是:

if(在map中) {
    map[key] ++;
} else {
    map[key] = 0;
}
`****

没有保存 iterator 的查找结果,造成每次插入都有两次的查找过程.修改以后,这个实现的速度仍然是最慢的,耗时大概是我那边 c 语言非递归 avl 的 3 倍!

于是我得出了结论:简单的东西往往比复杂的来得有用.c++那一套精妙的库可能倒不如自己写出来的很脏的c代码.从这个事情,又让我想起了 rob pike 说的大道至简,以及 unix 的那些 KISS 哲学,真是让人不由得感叹.

把那段经典的语录复制过来吧:

你无法断定程序会在什么地方耗费运行时间。瓶颈经常出现在想不到的地方，所以别急于胡乱找个地方改代码，除非你已经证实那儿就是瓶颈所在。2. 估量。在你没对代码进行估量，特别是没找到最耗时的那部分之前，别去优化速度。
3. **花哨的算法在 n 很小时通常很慢，而 n 通常很小。花哨算法的常数复杂度很大。** 除非你确定 n 总是很大，否则不要用花哨算法（即使 n 很大，也优先考虑原则 2 ）。比如，解决常见问题时，最简单的树——二叉树（binary tree）,总是比那些复杂的树（AVL树，伸展树（splay tree）和红黑树、B-树（B-tree）,多叉树（trie））来的高效。
花哨的算法比简单算法更容易出 bug 、更难实现。尽量使用简单的算法配合简单的数据结构。只要掌握了数据结构中的四大法宝，就可以包打天下，他们是：array 、linked list 、hash table、binary tree 。这四大法宝可不是各自为战的，灵活结合才能游刃有余。比如，一个用hash table组织的symbol table，其中是一个个由字符型array构成的linked list。
4. 以数据为中心。如果已经选择了正确的数据结构并且把一切都组织得井井有条，正确的算法也就不言自明。编程的核心是数据结构，而不是算法。
5. 没有原则 6 。

本文发生时间大致在 2012-09-13,找工作那段.写作时间为 2013-03-01.快要离校了整理以前的东西时写了此文.