谈表达式树的缓存（6）：五种缓存方式的性能比较

开始还债，因为还有至少两个可写的重要话题依赖在这个系列上，不解决就难以前进。

目前我们已经涉及了五种不同的缓存实现，它们分别是：

SimpleKeyCache：构造字符串作为Key，使用字典作为存储。

PrefixTreeCache：使用前缀树进行存储。

SortedListCache：使用排序列表或二叉搜索树进行存储。

HashedListCache：先对表达式树取散列值，再从字典中取出二叉搜索树。

DictionaryCache：实现了散列值和表达式树的比较方法，直接使用字典进行存储。

如果要从一个已经包含n个表达式树的存储中，查找一个有m个节点的表达式树，根据几篇文章的分析 ，从理论上说除了HashedListCache的时间复杂度是O(m * log(n))之外，其它几种实现的时间复杂度都是 O(m)。不过，理论上的结果和实际使用中的效果完全符合吗？如果完全符合的话，那么我们在构建第一个 SimpleKeyCache，获得了一种既简单直观又“高效”（达到了理论上最好的时间复杂度O(m)）的实现之后 为什么还要继续设计剩下的方案呢？如果您看完了文章还没有想到，这说明您的.NET编程“常识”还需要 加强。

那么我们就写一个程序，让数据说话。

这是一个控制台应用程序，接受用户参数，并由此生成试验数据，或进行性能比较。

生成试验数据

需要进行测试，自然要准备试验数据，而这里所需要的试验数据自然是大量的表达式树。

表达式树的种类非常纷繁，如果要构造各种类型的树，其代价也是非常昂贵的。因此在这里，我们只 构建所谓的“整数的四则运算”表达式进行试验。对于这样的表达式，每个运算符占用一个节点，每个数 字又会占用另一个节点，因此表达式数的节点个数m便是操作符的个数p，与数字的个数q之和。而由于每 个元算符都是二元运算符，因此p等于q - 1。于是我们就可以得出m与p之间的关系：

m　=　2p　+　1

知道了这个关系，我们便可以获得一定规模的试验数据。于是我们写一个简单的小程序来随机输出一 个表达式：

private　static　void　WriteSingleExpression(
　　 TextWriter　writer,　Random　random,　int　opCount)
{
　　 string　ops　=　"+-*/";

　　 writer.Write(random.Next(100));
　　 while　(opCount--　>　0)
　　 {
　　　　 writer.Write("　");
　　　　 writer.Write(ops[random.Next(4)]);
　　　　 writer.Write("　");
　　　　 writer.Write(random.Next(100));
　　 }
　　 writer.WriteLine();
}