SortedListCache

　SortedListCache使用排序列表进行存储，这样每次查询需要O(log(n))次比较，每次比较需要O(m)次操作，因此它也是五种存储中时间复杂度唯一不是理论最优值O(log(n) * m)的方案。

　我们为SortedListCache实现了ExpressionComparer，可以比较两个表达式树的“大小”。ExpressionComparer的实现非常高效，没有出现任何装箱拆箱操作，因此它可以说没有对GC造成任何压力，这也是为什么它没有造成任何回收操作的原因。虽然它在理论上的时间复杂度较高，为O(log(n) * m)，但是由于存储中的表达式树的数量不会不太多，其log(n)之后就变得非常小。因此从实际看来它的性能反而较SimpleKeyCache和PrefixTreeCache为好。性能较好的另一个原因在于ExpressionComparer不会形成一个完整遍历，一旦它发现两个表达式树的任意节点有所不同，那么就会立即返回。

　在上一篇文章的结尾，老赵提出了一个问题：“能否设计一种用例，让SortedListCache的耗时超过PrefixTreeCache或SimpleKeyCache”。这个问题其实可以转化为“能够设计一种用例，让ExpressionComparer耗时尽可能长”，也就是说，我们其实是要设计一种方案，设法让ExpressionComparer可以遍历到尽可能后的位置，例如每次都遍历到底。当然，表达式树长度的增加，也会导致SimpleKeyCache和PrefixTreeCache的耗时增加，是否确定能够满足要求，事实上老赵也并不确定。

　那么，我们又如何可以让ExpressionComparer比较次数尽可能少呢？这就要视情况而定了。例如，ExpressionComparer现在其实使用深度优先的方式进行比较，那么如果换成广度优先的方式是否能更快发现两个表达式树的差别呢？

　HashedListCache

　HashedListCache是性能较好的，它的关键便是在于使用了散列值将不同的表达式首先分布到不同的SortedList对象中，然后再使用类似SortedListCache的方式，使用O(log(k) * m)的时间复杂度进行查询。

　散列值的计算是HashedListCache性能的关键。计算散列值要求快，而且离散。“快”保证了可以在短时间内计算出一个表达式树。而“离散”保证了经过分布之后，每个SortedList对象中的表达式树数量k非常少。我们实现的ExpressionHasher基本上满足了这个条件。首先在计算散列值时只消耗了O(m)的时间复杂度，并且由于使用了和ExpressionComparer相同的遍历顺序，使得“前缀相同”的两颗表达式树的“散列值”很有可能不同。这样每个SortedList中，“前缀相同”的可能性就被降低了。自然ExpressionHasher便可更快地比较出两颗表达式树的区别来，节省了实现。

　此外，ExpressionHasher的设计也消除了任何装箱/拆箱，节省了时间消耗和GC压力。如果要进行优化的话，可能就需要设计一个更好的散列值计算方式。例如，我们可以对表达式树进行“采样”散列，而不是一个完整散列。但是“采样”散列很可能会降低离散程度，因此任何的改进还是要以性能评测为依据。

　DictionaryCache

　DictionaryCache为标准的字典存储方式。我们构造了一个CacheKey对象封装了表达式树，并且实现了Dictionary所需要的GetHashCode和Equals方法。

　由于每次查询需要构造一个CacheKey对象，因此对于GC会有“些许”影响，但是这个影响其实可以忽略不计。DictionaryCache也是继续散列值的存储方式，它与HashedListCache的区别在于由散列值获得某个“分区”之后，从分区中进行查找的时间复杂度是O(k * m)而不是HashedListCache的O(log(k) * m)。因此，DictionaryCache比HashedListCache更加依赖一个优秀的散列算法。如果一个散列算法的计算结果足够分布，那么HashedListCache和DictionaryCache的性能可谓不分伯仲。这也是为什么在上一篇文章试验中，DictionaryCache和HashedListCache的性能几乎相同。

　DictionaryCache的优势并非在于它的实现有什么精妙之处，反而在于“平实”。由于DictionaryCache的实现使用了.NET中标准的键/值存储方式，因此这种方法可以与其他组件轻易集成。例如我们的几种“缓存方式”其实都有点“名不副实”，因为缺少了“过期”及“自动清除”的机制。如果您要实现一个真正的“缓存”机制，可能就要借助现有的成熟的缓存容器了（实现一个成熟的，高效的，线程安全的缓存容器其实是一件非常困难的事情）。而有了DictionaryCache作为蓝本之后，我们就可以轻松地使用CacheKey对象封装表达式树，并作为Key放入缓存容器了。

　这就是“标准”的优势之一。

原文地址：http://www.cnblogs.com/jeffreyzhao/archive/2009/03/16/expression-cache-1.html