表达式树缓存性能对比：五种方法优劣分析？

本文共计2142个文字，预计阅读时间需要9分钟。

开始还需欠，因为还有至少两个可写的重要主题依赖在这个系列上，不解决就难以前进。目前，我们已经涉及了五种不同的缓存实现，它们分别是：SimpleKeyCache：构造字符串作为Key，使用字符。

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

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

1. SimpleKeyCache：构造字符串作为Key，使用字典作为存储。
2. PrefixTreeCache：使用前缀树进行存储。
3. SortedListCache：使用排序列表或二叉搜索树进行存储。
4. HashedListCache：先对表达式树取散列值，再从字典中取出二叉搜索树。
5. DictionaryCache：实现了散列值和表达式树的比较方法，直接使用字典进行存储。

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

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

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