3.8 性能

我们对上面的几个实现做了些比较。对程序做计时用的是《圣经·雅各书》中的《诗篇》，其中共有42 685个词(5 238个不同的词，22 482个前缀)。这个文本里有足够多的重复出现的短语(如“Blessed is the ...”)，其中有一个后缀包含多于400个元素，另外还有几百个链包含几十个后缀。所以这是个很好的测试数据集。

下面的表格列出的是生成10 000个输出词所用的秒数。这里用的机器一台是250 MHz的MIPS R10000，运行Irix 6.4系统，另一台是400 MHz的Pentium II，带有128 M内存，运行Windows NT 系统。运行时间几乎完全由输入数据的规模决定，相对而言，输出生成是非常快的。在表格里，还以源程序行数的方式给出了程序的大致规模。

C和C++ 程序都用带优化的编译器完成编译，Java程序运行时打开了即时编译功能。Irix的C和C++编译是从三个不同编译器里选出的最快的一个，由Sun SPARC 和DEC Alpha机器得到的数据也差不多。C版本的程序是最快的，比别的程序都快得多。Perl程序的速度次之。表格里的时间是我们试验的一个剪影，用的是特定的编译器和库。在你自己的环境里做，得到的结果也可能与此有很大差别。

Windows 上的STL deque版本肯定存在什么问题。试验说明表示前缀的deque用掉了大部分的运行时间，虽然在它里面从来都不超过两个元素。按说作为中心数据结构的映射所消耗的时间应该是最多的。把deque改成链表(在STL里是双链表)能使程序性质大大改善。另一方面，在Irix环境中把映射改为(非标准的)hash容器则并没有产生多大影响。在我们的Windows 机器上没有散列可以用。要完成上面说的这些修改，需要做的只是把deque换成list，或者把map 换成hash，然后重新做一下编译，这也是对STL基本设计思想的有效性的一个认证。我们也认为，STL作为C++ 的一个新部分，仍然受到不成熟实现的损害。在使用STL的不同实现或使用不同数据结构时，导致的性能变化是不可预测的。Java也存在这个问题，那里的实现也变得很快。

对于测试一个有意产生大量随机输出的程序，实际上存在着一些具有挑战性的问题。我们怎么能知道它确实是能工作的？怎样知道它在所有情况下都能工作？在第6章讨论测试时将提出一些建议，并描述如何测试马尔可夫程序。