达式树是否相同并不需要对它们进行完整编码如果我们“手动”进行比较往往只要一个节点一个节点进行对比只要找到某个节点不同便可以得到结论。不过仅仅比较两棵表达式是否相同无法进行查询和排序我们至少要得到两个表达式树之间的大小关系这样我们才能对它们进行排序才能够进行查找例如我们可以将它们放入线性表中并时刻保持排序状态这样便可以进行二分查找了。要得到两颗表达式树的大小关系与得到它们是否相等的时间复杂度是完全一样的事实上它们的实现方式也几乎完全相同只需在得到结果时返回1、0或-1而不是一个简单的布尔值便可。做一次这样的比较时间复杂度是O(m)m为遍历序列较短的表达式树的长度。不过就之前的分析可以得知对于两个“随机”的表达式树进行比较的性能是相当高的因为我们只要发现两者有一些不同便可以立即返回结果。可惜的是我们要实现一个这样的比较功能并不简单因为ExpressionVisitor只能用于遍历单个表达式树无法同时操作两个。不过我们只要模仿ExpressionVisitor的遍历方式“同时”遍历两个表达式树就可以了。因此我们现在就来实现算法的核心功能ExpressionComparer。如下public class ExpressionComparer : IComparerExpression { 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)); } } ... }ExpressionComparer实现了IComparerExpression接口可以进行两个表达式树的“大小”比较。从代码中可以看出它的Compare方法与ExpressionVisitor的Visit方法很接近起到了一个“中枢”的作用会将调用“转发”给具体的CompareXxx方法进行比较。不过这么做的前提是两个表达式树的类型相同——更确切地说是两个表达式树从“外观”上来看并没有区别所以才需要使用CompareXxx方法进行“深入”比较。从代码中可以看出Compare深得比较之道它会率先比较能够“立即”得到的信息如果已经能够看出差距便可快速地直接返回。为此老赵在ExpressionComparer中还实现了一些比较特定类型用的辅助方法摘录部分如下protected bool CompareNullT(T x, T y, out int result) where T : class { if (x null y null) { result 0; return true; } if (x null || y null) { result x null ? -1 : 1; return true; } result 0; return false; } protected virtual int CompareType(Type x, Type y) { if (x y) return 0; int result; if (this.CompareNull(x, y, out result)) return result; result x.GetHashCode() - y.GetHashCode(); if (result ! 0) return result; result x.Name.CompareTo(y.Name); if (result ! 0) return result; return x.AssemblyQualifiedName.CompareTo(y.AssemblyQualifiedName); }CompareNull方法比较两者是否为null并根据情况给出大小关系。而CompareType方法则是比较两个Type类型的对象从中也可以看出我们的比较策略从最迅速的比较入手“万不得已”才会比较相对低效的内容。因此在CompreType方法中在大部分情况下就已经能够通过两个对象的Hash Code中得到它们的大小关系只有在“万中无一”的情况下两个不同的Type对象才会有相同的HashCode那么我们再进行低效的字符串比较。这样的原则同样出现在各CompareXxx中如CompareUnaryprotected virtual int CompareUnary(UnaryExpression x, UnaryExpression y) { int result x.IsLifted.CompareTo(y.IsLifted); if (result ! 0) return result; result x.IsLiftedToNull.CompareTo(y.IsLiftedToNull); if (result ! 0) return result; result this.CompareMemberInfo(x.Method, y.Method); if (result ! 0) return result; return this.Compare(x.Operand, y.Operand); }而比较的“终点”则是ConstantExpression或ParameterExpression。其中CompareConstant方法实现如下protected virtual int CompareConstant(ConstantExpression x, ConstantExpression y) { return Comparer.Default.Compare(x.Value, y.Value); }在这里使用Comparer.Default这个框架自带的默认比较器进行object的比较其中会检查它们是否为字符串或者实现了IComparable接口——如果不实现则说明“无法进行比较”于是会抛出异常。不过如果需要进行比较那么这么做几乎是必须的所以这点对于我们的使用来说并不成为问题就不作处理了。需要补充的一点是我们的比较方式其实是基于表达式树的遍历序列的其比较方式其实与“字典序比较字符串”并没有多大差别所以这种大小关系同样具备传递性。也就是说如果Exp1 Exp2且Exp2 Exp3则Exp1 Exp3。现在我们可以轻松的得到两个表达式树的大小关系就可以像之前谈到的那样构造一个排序的线性表并且使用二分法进行查询这样查询性能便可以控制在O(log(n))了。不过我们在这里选择二叉搜索树Binary Search TreeBST这种数据结构进行存储如下上图来自Wikipedia它很好地展现了二叉搜索树这种数据结构的存储方式。二叉搜索树查询操作的时间复杂度是O(h)其中h是树的高度。所以在极端情况下二叉搜索树会发生“退化”使查询操作的时间复杂度变成或接近O(n)如下因此出现了AVL树又称“平衡二叉搜索树”它会在插入新节点时进行“旋转”保证每次插入后任意子树的左右高度差最多为1如下图。这样就控制了树的高度使查询操作的时间复杂度保持在O(log(n))。其实老赵选择二叉搜索树作为存储数据结构的原因有些可笑那只是因为.NET Framework的类库中已经提供了现成的实现那就是SortedList及对应的范型类。SortedList的实现便是一棵二叉搜索树是不是AVL树不清楚MSDN上提到了查询性能为O(log(n))并没有提到“退化”但也没有提到自动平衡因此有机会还是看看它的代码吧。SortedListTKey, TValue还能够接受一个IComparerTKey类型的对象用于自定义比较方式使用起来简直太容易了。因此我们就以此实现一个SortedListCachepublic class SortedListCacheT : IExpressionCacheT where T : class { private ReaderWriterLockSlim m_rwLock new ReaderWriterLockSlim(); private SortedListExpression, T m_storage new SortedListExpression, T( new ExpressionComparer()); public T Get(Expression key, FuncExpression, T creator) { T value; this.m_rwLock.EnterReadLock(); try { if (this.m_storage.TryGetValue(key, out value)) { return value; } } finally { this.m_rwLock.ExitReadLock(); } this.m_rwLock.EnterWriteLock(); try { if (this.m_storage.TryGetValue(key, out value)) { return value; } value creator(key); this.m_storage.Add(key, value); return value; } finally { this.m_rwLock.ExitWriteLock(); } } }由于一次表达式树的比较操作其时间复杂度为O(m)而二叉搜索树的查询操作其时间复杂度是O(log(n))即进行O(log(n))次比较。因此SortedListCache的查找操作最坏情况下其时间复杂度为O(m * log(n))——这可比前两次提到的SimpleKeyCache和PrefixTreeCache的O(m)时间复杂度要差啊。说得没错理论上的确是这样的。不过还是需要提一下理论和实际是有差别的就目前的问题来说ExpressionComparer非常高效在一般情况下很少会需要比较完整的遍历序列再由于它不需要任何的字符串拼接或新对象的创建因此其性能并不如想象中低。对于O(log(n))这个时间复杂度来说由于n为缓存容器中对象数目就算再大被以2为底取对数之后也变得不可怕了——要知道log(1020)也只是约等于55.22这是个什么规模呢