【IT168技术文档】
转载自Jeff Zhao的博客
开始还债，因为还有至少两个可写的重要话题依赖在这个系列上，不解决就难以前进。
目前我们已经涉及了五种不同的缓存实现，它们分别是：
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();
}
这个方法的目的是向TextWriter中随机输出一个拥有opCount个运算符的表达式（可以得知，这个表达式树有m = 2 * opCount + 1个节点）。例如，当opCount等于11的时候，它可能就会生成这样一个表达式：
然后我们获取用户参数输入，并输出一系列随机的表达式：
private static void GenerateExpressions(NameValueCollection args)
{
string output = args["out"] ?? "expressions.txt";
int min = Int32.Parse(args["min"] ?? "11");
int max = Int32.Parse(args["max"] ?? (min + 9).ToString());
int repeat = Int32.Parse(args["repeat"] ?? "100");
以上代码的目的是获取用户参数，用户输入的参数将被解析为NameValueCollection，参数含义如下：
output：输出文件
min：最短表达式中的运算符数量
max：最长表达式中的运算符数量
repeat：每种长度的表达式重复次数
向文件输出所有的随机表达式便不是难事了：
Random random = new Random(DateTime.Now.Millisecond);
using (var stream = File.Open(output, FileMode.Create))
{
StreamWriter writer = new StreamWriter(stream);
for (int opCount = min; opCount <= max; opCount++)
{
for (int i = 0; i < repeat; i++)
{
WriteSingleExpression(writer, random, opCount);
}
}
}
}
代码简单，就不多作分析了。
