谈表达式树的缓存(3):使用前缀树
2009-03-18 01:24 by 老赵, 10287 visits在上一篇文章里我们设法将前缀树构造为一个唯一的字符串,然后使用字符串作为key缓存在字典中。这个想法非常直接,做法也不困难(在遍历时记录详细信息便可)。不过事实上,老赵在思考表达式树的缓存问题时,这种字符串拼接的方式只存在于脑海当中,而上文的实现是为了这一系列文章的完整性而特地编写的。这是因为它的缺点较为明显,正如上文所述,字符串拼接操作较为耗时耗资源,且很容易生成一个长度可观的字符串(并非不能优化,不过实现就复杂了)。于是我们现在设法选择另一个解决方案来处理这个问题。
不过现在,我们先来考虑另一个问题:比较两个字符串是否相同(例如实现一个String.Equals方法)。此时,我们往往会分几步进行:
- 判断字符串长度是否相等,如果不等,则两个字符串肯定不同。
- 从头遍历两个字符串,如果找到某一位不相同,则两个字符串不相同。
- 如果完整遍历完整个字符串,则两者相同。
以上算法基本上是我们可以写出的最高效的比较算法。为什么这么说呢?原因主要有以下两点:
- 我们在比较时,首先使用最容易获得的信息(长度)进行判断,并且在合适的时候(发现某一位不同)及时返回,节省了时间。
- 比较时不需要保存完整信息(比较字符串的第n位时,从0到n-1位字符无需保留),这样在空间上也节省了下来。
那么我们来思考一下,为什么前一篇文章中谈到的字符串会性能差呢?其实他正是由于违反了上面的“特点”:
- 需要对整个树进行完整编码,这样无法通过部分编码上排除各种状况,时间上耗费较大。
- 必须保留完整路径,造成字符串很长,导致空间上耗费也大。
与字符串比较略有不同,既然我们最终是要匹配完全相同的表达式树,那么一次完整的树遍历是不可避免的,因此第一点可能很难有所改变。那么第二点呢?我们是否可以在进行匹配时,不用保存之前已经遍历的节点,遍历到某个“冲突”则表明匹配失败,而经过一个完整遍历,则表明匹配成功。为了进一步看清需求,我们再说的清楚一点:
- 对一颗表达式树进行完整遍历,可以看作是构造一个由各节点(或节点的“特性”)构成的序列。
- 在遍历序列时,无需保存之前遍历的结果。遍历结束时,则表示匹配成功。
“序列”、“遍历”、“匹配”……在心中反复默念几遍,您是否想到了些什么?没错,上述需求似乎符合我们常用的数据结构:前缀树。
前缀树可用于查询一个集合中是否包含某个特定序列。上图(引自Wikipedia)表明了前缀树的查询方式。例如我们要查询序列“ted”,则会从根节点开始,顺着“t”、“e”、“d”依次遍历到叶结点。如果序列没有遍历完就已经到了叶结点,则说明集合中没有该序列。前缀树至少有以下两个好处:
- 查询性能与集合中元素的数量n无关,对于查找一个长度为m的序列,其时间复杂度总是O(m),而对于二叉搜索树(Binary Search Tree)来说,其时间复杂度可能退化至O(m * log(n))。
- 只需对序列遍历一遍即可得到结果,且其中无需保存之前遍历的结果
有了思路之后,实现并不是什么大问题。如果要简单地构造一颗前缀树,最常用的方式便是让前缀树的每个节点包含一个哈希表,而每一次查找(Lookup)其实就是一次哈希表的查询操作。以下是PrefixTreeVisitor(也是另一个ExpressionVisitor的子类)中构造的预备代码:
public class PrefixTreeVisitor : ExpressionVisitor { private Hashtable m_storage; public Hashtable CurrentStorage { get; private set; } public bool StopLookingUpWhenMissed { get; private set; } public PrefixTreeVisitor(Hashtable storage, bool stopLookingUpWhenMissed) { this.m_storage = storage; this.StopLookingUpWhenMissed = stopLookingUpWhenMissed; } public Hashtable Accept(Expression exp) { this.CurrentStorage = this.m_storage; this.Visit(exp); return this.CurrentStorage; } }
PrefixTreeVisitor的构造函数会接受两个参数:一个作为前缀树根节点的Hashtable,以及一个标识“是否在命中失败的时候停止”。如果第二个参数为true,则对于前缀树的构造将在某次查找命中失败时中止,显然它可用于对前缀树的“查询”;如果第二个参数为false,那么在查找命失败后扩展前缀树,也就是创建新的节点(Hashtable),并建立与“父节点”的关系。这段逻辑可以从关键性的LookUp方法中得到体现:
private static readonly object s_nullKey = new object(); /// <summary> /// /// </summary> /// <param name="key"></param> /// <returns>Stop or not</returns> protected virtual bool LookUp(object key) { if (this.CurrentStorage == null) return true; key = key ?? s_nullKey; Hashtable next = this.CurrentStorage[key] as Hashtable; if (next == null && !this.StopLookingUpWhenMissed) { next = new Hashtable(); this.CurrentStorage[key] = next; } this.CurrentStorage = next; return next == null; }
LookUp方法的返回值表示该次查询是否跳出。从代码中可以看出,只有当StopLookingUpWhenMissed为true时LookUp方法才会可能返回false,因为在StopLookingUpWhenMissed为false时,LookUp方法会不断地“拓展”前缀树,永远不会中止。至于在PrefixTreeVisitor的Visit等重载方法中,便是构造合适的的节点(在这里一般使用匿名类型),作为正在遍历的序列中的某个元素,并交给LookUp方法进行“深入”。如果LookUp方法返回false,则立即返回,因为前缀树已经“探底”,可以“反弹”了:
protected override Expression Visit(Expression exp) { if (exp == null) return exp; var key = new { NodeType = exp.NodeType, Type = exp.Type }; if (this.LookUp(key)) return exp; return base.Visit(exp); } protected override Expression VisitBinary(BinaryExpression b) { var key = new { IsLifted = b.IsLifted, IsLiftedToNull = b.IsLiftedToNull, Method = b.Method }; if (this.LookUp(key)) return b; return base.VisitBinary(b); } protected override Expression VisitConstant(ConstantExpression c) { if (this.LookUp(c.Value)) return c; return base.VisitConstant(c); } protected override Expression VisitMemberAccess(MemberExpression m) { if (this.LookUp(m.Member)) return m; return base.VisitMemberAccess(m); } protected override Expression VisitMethodCall(MethodCallExpression m) { if (this.LookUp(m.Method)) return m; return base.VisitMethodCall(m); } ...
再编写PrefixTreeCache之前,我们可能还需要准备它的读取与写入功能。这两个操作其实都是对PrefixTreeVisitor的简单封装:
public class PrefixTreeCache<T> : IExpressionCache<T> where T : class { private Hashtable m_storage = new Hashtable(); private T Get(Expression key) { var visitor = new PrefixTreeVisitor(this.m_storage, true); var storage = visitor.Accept(key); return storage == null ? null : (T)storage[typeof(T)]; } private void Set(Expression key, T value) { var visitor = new PrefixTreeVisitor(this.m_storage, false); var storage = visitor.Accept(key); storage[typeof(T)] = value; } }
现在编写IExpressionCache.Get方法已如探囊取物:
private ReaderWriterLockSlim m_rwLock = new ReaderWriterLockSlim(); public T Get(Expression key, Func<Expression, T> creator) { T value; this.m_rwLock.EnterReadLock(); try { value = this.Get(key); if (value != null) return value; } finally { this.m_rwLock.ExitReadLock(); } this.m_rwLock.EnterWriteLock(); try { value = this.Get(key); if (value != null) return value; value = creator(key); this.Set(key, value); return value; } finally { this.m_rwLock.ExitWriteLock(); } }
使用前缀树缓存方式,在已有n个对象的缓存容器中查询带有m个节点的表达式树,其时间复杂度正如之前所谈到那样为O(m)——与n无关。这个解决方案的缺点在于构造了大量的Hashtable,可能会导致整个前缀树处于一种非常稀疏的状态,这点可以通过自定义查找方式来替换直接使用Hashtable类进行优化。这属于纯粹的进一步实践,感兴趣的朋友可以自己尝试一下。
完整代码下载:http://code.msdn.microsoft.com/ExpressionCache
相关文章:
沙发?