谈表达式树的缓存（4）：使用二叉搜索树（AVL树）
2009-03-19 09:05 by 老赵, 10530 visits上一篇文章中谈到的前缀树实现方式，时间复杂度从理论上来讲已经达到了最优，而空间复杂度理论上也可以做到较优。但是理论和实际是有差别的，而对于上文前缀树的实现来说，这两方面并不是非常理想：
- 时间：前缀树时间复杂度为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)); } } ... }
ExpressionComparer实现了IComparer<Expression>接口，可以进行两个表达式树的“大小”比较。从代码中可以看出，它的Compare方法与ExpressionVisitor的Visit方法很接近，起到了一个“中枢”的作用，会将调用“转发”给具体的CompareXxx方法进行比较。不过这么做的前提是两个表达式树的类型相同——更确切地说是两个表达式树从“外观”上来看并没有区别，所以才需要使用CompareXxx方法进行“深入”比较。从代码中可以看出，Compare深得比较之道，它会率先比较能够“立即”得到的信息，如果已经能够看出差距，便可快速地直接返回。为此，老赵在ExpressionComparer中还实现了一些比较特定类型用的辅助方法，摘录部分如下：
protected bool CompareNull<T>(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中，如CompareUnary：
protected 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 Tree，BST）这种数据结构进行存储，如下：
上图来自Wikipedia，它很好地展现了二叉搜索树这种数据结构的存储方式。二叉搜索树查询操作的时间复杂度是O(h)，其中h是树的高度。所以在极端情况下，二叉搜索树会发生“退化”，使查询操作的时间复杂度变成（或接近）O(n)，如下：
因此出现了AVL树，又称“平衡二叉搜索树”，它会在插入新节点时进行“旋转”，保证每次插入后任意子树的左右高度差最多为1（如下图）。这样就控制了树的高度，使查询操作的时间复杂度保持在O(log(n))。
其实老赵选择二叉搜索树作为存储数据结构的原因有些可笑，那只是因为.NET Framework的类库中已经提供了现成的实现，那就是SortedList（及对应的范型类）。SortedList的实现便是一棵二叉搜索树（是不是AVL树不清楚，MSDN上提到了查询性能为O(log(n))，并没有提到“退化”，但也没有提到自动平衡，因此有机会还是看看它的代码吧）。SortedList<TKey, TValue>还能够接受一个IComparer<TKey>类型的对象用于自定义比较方式，使用起来简直太容易了。因此，我们就以此实现一个SortedListCache：
public class SortedListCache<T> : IExpressionCache<T> where T : class { private ReaderWriterLockSlim m_rwLock = new ReaderWriterLockSlim(); private SortedList<Expression, T> m_storage = new SortedList<Expression, T>( new ExpressionComparer()); public T Get(Expression key, Func<Expression, 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，这是个什么规模呢？
但是从理论上来说，O(m * log(n))的时间复杂度还是比O(m)要高，因此性能究竟如何，还要由测试数据说了算——在老赵进行详细比较之前，不如您自己先试试看？
更正：据源码分析，SortedList是文章中所写的排序后的线性表，加上二分查找这样的数据结构（插入删除O(n)，查找O(log(n))），而不是一颗二叉搜索树。事实上，SortedDictionary是使用红黑树（也是一种平衡的二叉搜索树）实现的（插入删除查找都是O(log(n)），兄弟们可以根据情况自行进行选择。犯此错误的原因在于老赵亲信了MSDN的错误描述（见26楼）；更主要的原因也是没有更进一步的思考，虽然发现了MSDN的矛盾之处，但还是简单的写了出来。立此为证，以观后效。
完整代码下载：http://code.msdn.microsoft.com/ExpressionCache
相关文章：
趁机占一次沙发，明早细细品味，老赵同志早点睡:-)