上一篇文章中谈到的前缀树实现方式，时间复杂度从理论上来讲已经达到了最优，而空间复杂度理论 上也可以做到较优。但是理论和实际是有差别的，而对于上文前缀树的实现来说，这两方面并不是非常理 想：
时间：前缀树时间复杂度为O(m)的前提是每次哈希表查找操作的时间复杂度为O(1)，不过这个O(1)与 一次数值比较相比，从性能上来说还是有比较明显的差距。
空间：前缀树空间复杂度较优的前提是“精细”地实现该数据结构，如果像上文般粗枝大叶，那么会 形成大量稀疏的哈希表，反而造成空间浪费。
因此，虽然事实上前缀树是老赵第一个真正实现的缓存方法，但是对此并不满意，也想着有什么办法 可以进行优化。
之前提到过，使用字符串进行完整编码的性能较低，其原因之一是因为只有完整编码才能获得最终结 果，继而与字典中其他元素进行比较。很明显的事实是，比较两棵表达式树是否相同并不需要对它们进行 完整编码，如果我们“手动”进行比较，往往只要一个节点一个节点进行对比，只要找到某个节点不同， 便可以得到结论。不过仅仅比较两棵表达式是否相同无法进行查询和排序，我们至少要得到两个表达式树 之间的大小关系，这样我们才能对它们进行排序，才能够进行查找，例如我们可以将它们放入线性表中并 时刻保持排序状态，这样便可以进行二分查找了。
要得到两颗表达式树的大小关系，与得到它们是否相等的时间复杂度是完全一样的，事实上它们的实 现方式也几乎完全相同，只需在得到结果时返回1、0或-1，而不是一个简单的布尔值便可。做一次这样的 比较时间复杂度是O(m)，m为遍历序列较短的表达式树的长度。不过就之前的分析可以得知，对于两个“ 随机”的表达式树进行比较的性能是相当高的，因为我们只要发现两者有一些不同，便可以立即返回结果 。
可惜的是，我们要实现一个这样的比较功能并不简单，因为ExpressionVisitor只能用于遍历单个表达 式树，无法同时操作两个。不过我们只要模仿ExpressionVisitor的遍历方式，“同时”遍历两个表达式 树就可以了。因此我们现在就来实现算法的核心功能：ExpressionComparer。如下：
public class ExpressionComparer : IComparer<Expression>
{
public virtual int Compare(Expression x, Expression y)
{
int result;
if (this.CompareNull(x, y, out result)) return result;
result = this.CompareType(x.GetType(), y.GetType());
if (result != 0) return result;
result = x.NodeType - y.NodeType;
if (result != 0) return result;
result = this.CompareType(x.Type, y.Type);
if (result != 0) return result;
switch (x.NodeType)
{
case ExpressionType.Negate:
case ExpressionType.NegateChecked:
...
return this.CompareUnary((UnaryExpression)x, (UnaryExpression)y);
case ExpressionType.Add:
case ExpressionType.AddChecked:
...
return this.CompareBinary((BinaryExpression)x, (BinaryExpression) y);
case ExpressionType.TypeIs:
return this.CompareTypeIs((TypeBinaryExpression)x, (TypeBinaryExpression)y);
case ExpressionType.Conditional:
return this.CompareConditional((ConditionalExpression)x, (ConditionalExpression)y);
case ExpressionType.Constant:
return this.CompareConstant((ConstantExpression)x, (ConstantExpression)y);
...
default:
throw new Exception(string.Format("Unhandled expression type: '{0}'", x.NodeType));
}
}
...
}