Hello World
Spiga

谈表达式树的缓存(3):使用前缀树

2009-03-18 01:24 by 老赵, 10287 visits

上一篇文章里我们设法将前缀树构造为一个唯一的字符串,然后使用字符串作为key缓存在字典中。这个想法非常直接,做法也不困难(在遍历时记录详细信息便可)。不过事实上,老赵在思考表达式树的缓存问题时,这种字符串拼接的方式只存在于脑海当中,而上文的实现是为了这一系列文章的完整性而特地编写的。这是因为它的缺点较为明显,正如上文所述,字符串拼接操作较为耗时耗资源,且很容易生成一个长度可观的字符串(并非不能优化,不过实现就复杂了)。于是我们现在设法选择另一个解决方案来处理这个问题。

不过现在,我们先来考虑另一个问题:比较两个字符串是否相同(例如实现一个String.Equals方法)。此时,我们往往会分几步进行:

  1. 判断字符串长度是否相等,如果不等,则两个字符串肯定不同。
  2. 从头遍历两个字符串,如果找到某一位不相同,则两个字符串不相同。
  3. 如果完整遍历完整个字符串,则两者相同。

以上算法基本上是我们可以写出的最高效的比较算法。为什么这么说呢?原因主要有以下两点:

  • 我们在比较时,首先使用最容易获得的信息(长度)进行判断,并且在合适的时候(发现某一位不同)及时返回,节省了时间。
  • 比较时不需要保存完整信息(比较字符串的第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

相关文章:

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

41 条回复

  1. 痕
    *.*.*.*
    链接

    2009-03-18 00:50:00

    沙发?

  2. 老赵
    admin
    链接

    老赵 2009-03-18 00:51:00

    --引用--------------------------------------------------
    痕: 沙发?
    --------------------------------------------------------
    好吧……

  3. 老赵
    admin
    链接

    老赵 2009-03-18 01:02:00

    代码终于也上传玩了,看会儿书,睡觉。

  4. rainnoless
    *.*.*.*
    链接

    rainnoless 2009-03-18 01:12:00

    留个言睡觉,偶一篇文章又难产几天了,开来只能开膛破肚了,呵呵。

  5. holywolf
    *.*.*.*
    链接

    holywolf 2009-03-18 08:10:00

    C#高级编程里怎么没看到表达式树的介绍,谁找到了,告诉我在哪一章

  6. 紫色永恒
    *.*.*.*
    链接

    紫色永恒 2009-03-18 08:13:00

    老赵每日都这个时候睡觉 想不瘦都难啊

  7. 哈哈1[未注册用户]
    *.*.*.*
    链接

    哈哈1[未注册用户] 2009-03-18 08:22:00

    建树之前,应该都知道干什么的。
    所以自己定义的key,应该就可以。

  8. 老赵
    admin
    链接

    老赵 2009-03-18 09:05:00

    --引用--------------------------------------------------
    holywolf: C#高级编程里怎么没看到表达式树的介绍,谁找到了,告诉我在哪一章
    --------------------------------------------------------
    C# 3.0和.NET 3.5的东西,那本书是讲什么的?

  9. 老赵
    admin
    链接

    老赵 2009-03-18 09:05:00

    --引用--------------------------------------------------
    哈哈1: 建树之前,应该都知道干什么的。
    所以自己定义的key,应该就可以。
    --------------------------------------------------------
    我为啥总是听不懂你想表达什么意思,呵呵

  10. 阿不
    *.*.*.*
    链接

    阿不 2009-03-18 09:09:00

    看似一个比较的好的表达式树的比较方法。
    我也想过对Expression做缓存,
    也想过ToString
    也想过.Equals
    ...

  11. 老赵
    admin
    链接

    老赵 2009-03-18 09:10:00

    --引用--------------------------------------------------
    紫色永恒: 老赵每日都这个时候睡觉 想不瘦都难啊
    --------------------------------------------------------
    我从80长到120的时候每天也是这个时候睡觉,所以睡眠多少和胖瘦没有必然联系。

  12. 老赵
    admin
    链接

    老赵 2009-03-18 09:12:00

    --引用--------------------------------------------------
    阿不: 看似一个比较的好的表达式树的比较方法。
    我也想过对Expression做缓存,
    也想过ToString
    也想过.Equals
    ...
    --------------------------------------------------------
    最后结论是?

  13. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-03-18 09:31:00

    老赵阿 我怎么觉得这种碰撞概率高于md5涅

  14. 老赵
    admin
    链接

    老赵 2009-03-18 09:53:00

    --引用--------------------------------------------------
    韦恩卑鄙: 老赵阿 我怎么觉得这种碰撞概率高于md5涅
    --------------------------------------------------------
    这里哪里有什么碰撞了,这里完整的序列查找,找到了就是唯一一个。

  15. 木野狐(Neil Chen)
    *.*.*.*
    链接

    木野狐(Neil Chen) 2009-03-18 10:04:00

    "查询性能与集合中元素的数量n无关,对于查找一个长度为m的序列,其时间复杂度总是O(n)"

    好像有一个笔误,这里应该是 O(m).

  16. 老赵
    admin
    链接

    老赵 2009-03-18 10:04:00

    --引用--------------------------------------------------
    木野狐(Neil Chen): &quot;查询性能与集合中元素的数量n无关,对于查找一个长度为m的序列,其时间复杂度总是O(n)&quot;

    好像有一个笔误,这里应该是 O(m).
    --------------------------------------------------------
    谢谢

  17. 阿不
    *.*.*.*
    链接

    阿不 2009-03-18 10:06:00

    --引用--------------------------------------------------
    Jeffrey Zhao: --引用--------------------------------------------------
    阿不: 看似一个比较的好的表达式树的比较方法。
    我也想过对Expression做缓存,
    也想过ToString
    也想过.Equals
    ...
    --------------------------------------------------------
    最后结论是?
    --------------------------------------------------------
    最近是没有找到好的办法。
    但是为了缓存,每次都要先遍历整棵树,显然有点太耗性能了
    这里是使用前序遍历?找到不同的退出?然后相同的条件是整个树都遍历结束?

  18. 老赵
    admin
    链接

    老赵 2009-03-18 10:21:00

    @阿不
    就算你ToString一下,它也是要遍历的啊,呵呵(当然,因为Expression Tree是只读的,所以调用多次ToString也只需要构造一次就够了)。
    遍历整颗树是必须的,就像你比较字符串,不比较完怎么能知道是否相同?而且纯遍历来说,并不花时间,关键是你在遍历的时候做了哪些事情(比如拼接字符串就比普通比较要耗时)。
    这里就是把整个表达式树的遍历看作是一个序列,然后用前缀树构造索引,文章和代码都写得很清楚了。
    从理论上讲,这个方法的时间复杂度已经是最优的了,因为你要找到匹配,则必须完全遍历,因此O(m)是至少的——前缀树的优点就是怎么样都是O(m)……

  19. 阿不
    *.*.*.*
    链接

    阿不 2009-03-18 10:35:00

    @Jeffrey Zhao
    我目前没有其它好的想法,你的这种方案目前应该是比较优的了。
    通常想到做Expression Tree 缓存,是在与数据库交互的时候。这时个缓存Expression Tree的意义是重大的。如果从Entity Framework或其它的框架通过缓存Expression Tree来提供底层的缓存支持的话,那是最好不过的。
    但是从另一方面来讲,需要被缓存的数据往往都只是一小部分,对这些关键数据的缓存对系统的性能起着决定性的作用。所以我目前的做法,是对这部分关键数据作特殊的处理,它不是缓存Expression Tree ,而是直接缓存数据。

  20. 老赵
    admin
    链接

    老赵 2009-03-18 10:43:00

    @阿不
    应该说,不是用ExpressionTree做key,而是用其他东西作key。
    其实我研究这个问题的原因是,的确有非用Expression Tree作缓存的场景,所以这个问题是绕不开的。

  21. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-03-18 10:48:00

    --引用--------------------------------------------------
    Jeffrey Zhao: --引用--------------------------------------------------
    韦恩卑鄙: 老赵阿 我怎么觉得这种碰撞概率高于md5涅
    --------------------------------------------------------
    这里哪里有什么碰撞了,这里完整的序列查找,找到了就是唯一一个。
    --------------------------------------------------------
    昨天的脑我还没洗干净 是我不好 哈哈

  22. Anytao
    *.*.*.*
    链接

    Anytao 2009-03-18 10:59:00

    你倒墨水的速度,是相当的可怕,等待后续喽。

  23. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-03-18 11:08:00

    这两天有点掉进序列化的陷阱了。

    这种不错。

    但是内存里放好多Expression还是会不放心

    目前找不到不放心的点在哪里 还在阅读中

  24. 老赵
    admin
    链接

    老赵 2009-03-18 11:11:00

    --引用--------------------------------------------------
    Anytao: 你倒墨水的速度,是相当的可怕,等待后续喽。
    --------------------------------------------------------
    这个东西准备了两个星期了,准备这星期倒个七七八八的……

  25. 老赵
    admin
    链接

    老赵 2009-03-18 11:13:00

    @韦恩卑鄙
    嗯,我目前感觉到的就是前缀树的老问题,如果没有精细实现,索引会比较庞大。而且查找虽然理论是O(1)的,但是与普通的比较相比,操作还是比较多。 所以我也在继续想接下去的做法,还有3种比较有意思的……其实都比较简单。

  26. 老赵
    admin
    链接

    老赵 2009-03-18 11:21:00

    @韦恩卑鄙
    还有就是,从理论上说,如果精细实现,那么内存占用(相对其他存储)不会有太多差距,因为前缀树记录的是“路径”,而不用保持每个Expression Tree——其实就是把Expression Tree给打散了,分散在路经上。不过路径之间可以有公用,因此还可以节省一些空间,因此实现的好理论上甚至会节省。
    在这方面问题,还是在于特定实现中,前缀树开辟的空间是否“稀疏”。

  27. DiryBoy
    *.*.*.*
    链接

    DiryBoy 2009-03-18 11:42:00

    喜欢这种现代的实现方法!收藏学习了。

  28. 老赵
    admin
    链接

    老赵 2009-03-18 13:40:00

    @DiryBoy
    谢谢指出,那是因为PrefixTreeVisitor原本在代码里叫Builder,我写文章的时候临时觉得不妥所以修改的,疏忽了,呵呵。
    // 前缀树一点不现代的,既不是我发明的也已经出来很久了……

  29. yzlhccdec
    *.*.*.*
    链接

    yzlhccdec 2009-03-18 14:50:00

    恩,昨天吃饭的时候看了你前几篇文章,当时第一想法就是构造树,不过想的是后缀树(没深入搞过,只是知道这么一个概念,不过觉得树应该能做),唉。。吃完饭就忘记有这么一回事了。。。。

  30. yzlhccdec
    *.*.*.*
    链接

    yzlhccdec 2009-03-18 14:59:00

    2008的新数据类型里面有个hierarchyid,是用binary表示树的。。不晓得你把数变成binary可不可行。。。。

  31. 老赵
    admin
    链接

    老赵 2009-03-18 15:02:00

    @yzlhccdec
    你说得是SQL Server,而且Hierarchyid也不是这样用的,这里的“树”和Hierarchy“树”也不是同一个东西……

  32. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-03-18 15:52:00

    理了下思路 我觉得一直不舒服的地方是树的key都是expression

    可能是asp3时代对于持久对象带来的巨大性能消耗产生了心理障碍,我比较习惯让复杂的对象序列化以后做key 。。。

    也就是说 结合上一章每个expression node变成string作key我大概就放心了
    -0-









  33. 老赵
    admin
    链接

    老赵 2009-03-18 15:55:00

    @韦恩卑鄙
    前缀树的每个节点里存放的是路径中的一个元素阿,前缀树里不存放Expression的。
    这就好比字符串的前缀树不保存字符串本身,每个节点只是保存一个char而已(也就是字符串这个这个序列的一个元素)。

  34. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-03-18 16:19:00

    对对 可能是我基础不牢 我说得expression node
    就是你说得元素、


    就算是元素 也算是复杂对象 所以我觉得有点难过


    protected override Expression VisitBinary(BinaryExpression b)
    protected override Expression VisitConstant(ConstantExpression c)
    protected override Expression VisitMemberAccess(MemberExpression m)
    protected override Expression VisitMethodCall(MethodCallExpression m)

    这些类型没有及时销毁 让我感到莫名恐惧
    把这些类型给序列化后作key我可能就舒服一些

  35. yzlhccdec
    *.*.*.*
    链接

    yzlhccdec 2009-03-18 17:19:00

    @Jeffrey Zhao
    可能我没说清楚,我的意思是把Expression变成结构化的binray流不知可不可行。哦,还有一个问题,对于那些不考虑子句顺序的expression,你的比较结果貌似是不一样的?

  36. 老赵
    admin
    链接

    老赵 2009-03-18 17:22:00

    @yzlhccdec
    1、其实变成字符串就是变成流嘛,而且其实计算机里任何东西都是数据流。
    2、没错,1 + 2与2 + 1是两个不同的东西。

  37. yzlhccdec
    *.*.*.*
    链接

    yzlhccdec 2009-03-18 21:56:00

    @Jeffrey Zhao
    话是这样说没错,但是性能还是有差距的,说白了就类似xml序列化和二进制序列化的差别。期待下文。。。

  38. 老赵
    admin
    链接

    老赵 2009-03-18 22:50:00

    @yzlhccdec
    我觉得没有什么差距,字符串也是不断拼接的流式数据,其比较和使用byte[]相比没有任何空间和时间上的差距。
    这和二进制序列化/xml序列化没有可比性,两种序列化是算法上和序列化方式上的差别。

  39. 真的,这家伙很懒.
    *.*.*.*
    链接

    真的,这家伙很懒. 2009-06-03 01:04:00

    2.从头遍历两个字符串,如果找到某一位不相同,则两个字符串相同。
    应该是"...则两个字符串不相同"吧?

  40. 老赵
    admin
    链接

    老赵 2009-06-03 09:07:00

    @真的,这家伙很懒.
    谢谢,已经改正了!

  41. lixiong
    58.41.86.*
    链接

    lixiong 2011-03-22 19:33:35

    原来匿名类型还有这个用途!!!巧用了GetHashCode()的诡异实现阿~~~

    "Because the Equals and GetHashCode methods on anonymous types are defined in terms of the Equals and GetHashcode of the properties, two instances of the same anonymous type are equal only if all their properties are equal."

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我