Hello World
Spiga

谈表达式树的缓存(4):使用二叉搜索树(AVL树)

2009-03-19 09:05 by 老赵, 10514 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

相关文章:

Creative Commons License

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

Add your comment

37 条回复

  1. Anytao
    *.*.*.*
    链接

    Anytao 2009-03-19 01:17:00

    趁机占一次沙发,明早细细品味,老赵同志早点睡:-)

  2. 老赵
    admin
    链接

    老赵 2009-03-19 01:33:00

    --引用--------------------------------------------------
    Anytao: 趁机占一次沙发,明早细细品味,老赵同志早点睡:-)
    --------------------------------------------------------
    睡了睡了……

  3. rainnoless
    *.*.*.*
    链接

    rainnoless 2009-03-19 01:39:00

    mark,睡觉,二叉树这个关键词偶看到了,飘过,翻书去回顾下二叉树的概念,呵呵。

  4. Typhone[未注册用户]
    *.*.*.*
    链接

    Typhone[未注册用户] 2009-03-19 02:42:00

    很显然SortList不是二叉树
    它就是一个每次插入,修改时进行排序的有序线性表
    所以查找的时间复杂度为O(log n),删除,插入为O(n)
    只是空间复杂度要好于红黑树SortDictionary

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

    紫色永恒 2009-03-19 08:50:00

    二叉都出来了。。老赵这系列准备写几章呀?

  6. 痕
    *.*.*.*
    链接

    2009-03-19 08:51:00

    貌似赵老师现在对数据结构很感兴趣

  7. 老赵
    admin
    链接

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

    --引用--------------------------------------------------
    Typhone: 很显然SortList不是二叉树
    它就是一个每次插入,修改时进行排序的有序线性表
    所以查找的时间复杂度为O(log n),删除,插入为O(n)
    只是空间复杂度要好于红黑树SortDictionary
    --------------------------------------------------------
    没看过代码,不知道,我是看MSDN中SortedList的文档:
    The SortedList<(Of <(TKey, TValue>)>) generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary
    当然它后面也提到了O(n)的插入时间复杂度,又像是个排序的线性表,所以很奇怪——当然,我也倾向于你说得这是个Sorted的List,名字是这么些的么,呵呵。

  8. 老赵
    admin
    链接

    老赵 2009-03-19 09:08:00

    --引用--------------------------------------------------
    痕: 貌似赵老师现在对数据结构很感兴趣
    --------------------------------------------------------
    什么叫做现在很感兴趣?我一直强调数据结构的重要性,现在只是刚好有个东西要做,然后需要选取合适的数据结构而已。这些都是要一直留在脑子里的,然后需要的时候就拿出来用。

  9. 老赵
    admin
    链接

    老赵 2009-03-19 09:09:00

    --引用--------------------------------------------------
    紫色永恒: 二叉都出来了。。老赵这系列准备写几章呀?
    --------------------------------------------------------
    还有一篇,会提出剩下两种状况。
    再有一篇,进行性能测试。
    可能还会有一篇,再分析一下。
    所以还有2-3篇。

  10. 痕
    *.*.*.*
    链接

    2009-03-19 09:34:00

    @Jeffrey Zhao
    呵呵 不要生气 我只是觉得数据结构在业务中的重要性不如大学考试 上学期数据结构成绩不怎么好...-_-..

  11. 老赵
    admin
    链接

    老赵 2009-03-19 09:36:00

    --引用--------------------------------------------------
    痕: @Jeffrey Zhao
    呵呵 不要生气 我只是觉得数据结构在业务中的重要性不如大学考试 上学期数据结构成绩不怎么好...-_-..
    --------------------------------------------------------
    哪里生气了,呵呵。
    不过如果你不学好这些,你估计一辈子也就只能做做CRUD了。人的知识体系是连续的,一旦出现缺门,就提高不了了。

  12. 痕
    *.*.*.*
    链接

    2009-03-19 09:48:00

    @Jeffrey Zhao
    这学期我要再重新学西一遍数据结构和算法 不放过这些基础课 把根基打牢固了. 谢谢老赵的指点~

  13. 怪怪
    *.*.*.*
    链接

    怪怪 2009-03-19 09:52:00

    @Jeffrey Zhao
    我的经验是,不用追求严格的连续,蛙跳式前进也不错 ^^

    你这个还真是,那天讨论的类似于DFA的方法和原始方法或者字符串Key方法,的折中 :P

  14. 老赵
    admin
    链接

    老赵 2009-03-19 09:54:00

    @痕
    加油,加油

  15. 老赵
    admin
    链接

    老赵 2009-03-19 09:55:00

    @怪怪
    是啊是啊,其实就是想到一个,觉得哪里不好就改进哪里,前进前进后退后退的。

  16. ppchen(陈荣林)
    *.*.*.*
    链接

    ppchen(陈荣林) 2009-03-19 09:56:00

    每天都有你的文章可以看 :)
    只是数据结构忘得差不多了,惭愧啊

  17. 老赵
    admin
    链接

    老赵 2009-03-19 09:58:00

    --引用--------------------------------------------------
    怪怪: @Jeffrey Zhao
    我的经验是,不用追求严格的连续,蛙跳式前进也不错 ^^
    --------------------------------------------------------
    那不就是我么,跳、跳、跳,然后撞墙,于是回头补、补、补,呵呵。

  18. 老赵
    admin
    链接

    老赵 2009-03-19 09:59:00

    @ppchen(陈荣林)
    还好还好,其实已经准备了两个星期,现在只是倒出来而已。

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

    韦恩卑鄙 2009-03-19 11:11:00

    用hashcode作比较*(@#&*(@&#!
    ExpressionComparer 部分的代码多少还是有点痛苦 有没有更好的办法呢?




    感觉到这一节就有点歪了 老赵别有用心阿

    “不过如果不学好这些,估计一辈子也就只能做做CRUD了。人的知识体系是连续的,一旦出现缺门,就提高不了了。”

    才是老赵你一直想表达的吧!

    恩恩

  20. 老赵
    admin
    链接

    老赵 2009-03-19 11:14:00

    @韦恩卑鄙
    要HashCode的话等下次吧,马上就能看到了,嘿嘿。
    不过哪里偏了,Comparer也是不可或缺的阿,一个类要做key不是要实现GetHashCode和Equals吗?没有Comparer咋干Equals?
    至于有没有更好的Compare办法……我想不到。不过为啥又痛苦了呢?现在既没有构造新对象,又不会保存复杂对象,一些简单的比较为啥还让你那么痛苦呀?

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

    韦恩卑鄙 2009-03-19 11:48:00

    本次的痛苦来源自这个巨大的
    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));

    还真得十分清楚每个类型的node怎样compare 才行 老赵你可真辛苦。 我的痛苦是替你感到疲劳

    期待下一节ing


  22. 老赵
    admin
    链接

    老赵 2009-03-19 11:51:00

    @韦恩卑鄙
    没办法啊,谁让C#是编译期静态绑定的呢?
    还好,基本上是从ExpressionVisitor里直接拷过来的,然后Replace一下,嗯嗯。

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

    韦恩卑鄙 2009-03-19 12:06:00

    有关此集合的泛型版本,请参见 System.Collections.Generic..::.SortedList<(Of <(TKey, TValue>)>)。

    SortedList 元素可通过其键来访问 (如任意 IDictionary 实现中的元素),或通过其索引来访问(如任意 IList 实现中的元素)。

    SortedList 对象在内部维护两个数组以存储列表的元素;即,一个数组用于键,另一个数组用于相关联的值。每个元素都是一个可作为 DictionaryEntry 对象进行访问的键/值对。键不能为 nullNothingnullptrnull 引用(在 Visual Basic 中为 Nothing),但值可以。

    SortedList 对象的容量是 SortedList 可以保存的元素数。随着向 SortedList 中添加元素,容量通过重新分配按需自动增加。可通过调用 TrimToSize 或通过显式设置 Capacity 属性减少容量。

    SortedList 对象的元素将由键按照特定的 IComparer 实现(在创建 SortedList 时指定),或按照键本身提供的 IComparable 实现进行排序。不论在哪种情况下,SortedList 都不允许重复键。

    索引顺序基于排序顺序。当添加元素时,元素将按正确的排序顺序插入 SortedList,同时索引会相应地进行调整。当移除元素时,索引也会相应地进行调整。因此,当在 SortedList 对象中添加或移除元素时,特定键/值对的索引可能会更改。

    由于要进行排序,所以在 SortedList 对象上操作比在 Hashtable 对象上操作要慢。但是,SortedList 允许通过相关联键或通过索引对值进行访问,可提供更大的灵活性。

    可使用一个整数索引访问此集合中的元素。此集合中的索引从零开始。



    - -|||||||||||||||||

    似乎真的不是树啊。。。

  24. 老赵
    admin
    链接

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

    @韦恩卑鄙
    果然不是树,看来真的不是树,树估计是SortedDictionary?
    不过你可以看一下SortedList<TKey, TValue>方法的描述……MSDN范低级错误了。

  25. 老赵
    admin
    链接

    老赵 2009-03-19 12:24:00

    http://msdn.microsoft.com/en-us/library/ms132319.aspx [img]/images/cnblogs_com/jeffreyzhao/sorted-list-msdn.jpg[/img]

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

    韦恩卑鄙 2009-03-19 12:27:00

    我看的是3.5的非泛型版本

    也许4.0有所修改?或者说泛型版本有所区别?


    算法基本上一样 仅仅是insert 的时候就版本带来了 array拼接的性能损耗

  27. 老赵
    admin
    链接

    老赵 2009-03-19 12:29:00

    @韦恩卑鄙
    是二分查找,不是树,虽然查找操作都是O(log(n)),不过插入就是O(n)和O(log(n))的区别的。算法不同,(查找操作)时间复杂度一样。
    还是我搞错了,轻信了MSDN,已经在文章中注释了……
    // 不过兄弟能不能修改一下上面的评论,把代码去了吧……否则我删了,嘿嘿。

  28. 老赵
    admin
    链接

    老赵 2009-03-19 12:30:00

    @韦恩卑鄙
    应该是MSDN写错了吧,前后有矛盾。
    SortedList是对的,SortedList<TKey, TValue>的描述错了。

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

    韦恩卑鄙 2009-03-19 12:35:00

    二分法查找本质和平衡树完全一样
    唯一可惜的就是insert 的时候要连接array

    文章不需要大改 太好了

  30. 老赵
    admin
    链接

    老赵 2009-03-19 12:37:00

    --引用--------------------------------------------------
    韦恩卑鄙: 二分法查找本质和平衡树完全一样
    唯一可惜的就是insert 的时候要连接array

    文章不需要大改 太好了
    --------------------------------------------------------
    最多把SortedList改为SortedDictionary,嘿嘿。

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

    韦恩卑鄙 2009-03-19 12:41:00

    也不是完全没有好处
    二分法永远平衡

  32. 老赵
    admin
    链接

    老赵 2009-03-19 12:44:00

    @韦恩卑鄙
    数据结构和算法么总归是合适的环境下用,没有通吃的,恩恩。

  33. 甲乙丙丁
    *.*.*.*
    链接

    甲乙丙丁 2009-03-19 14:09:00

    正好在学习树方面的知识

  34. zeus2
    *.*.*.*
    链接

    zeus2 2009-03-19 19:08:00

    红黑树是很复杂的, AVL树就简单了多,不过AVL树性能好像比红黑树好点。
    不知道有没证据。

  35. 郑明
    *.*.*.*
    链接

    郑明 2009-03-19 20:23:00

    好象用动态规划生成树通用点..

  36. 老赵
    admin
    链接

    老赵 2009-03-19 20:24:00

    @郑明
    没听懂,仔细说说?

  37. cwbboy[未注册用户]
    *.*.*.*
    链接

    cwbboy[未注册用户] 2009-03-20 10:16:00

      要补好数据结构,会发现补一下离散数学就更好。。。~~~~ 这就像从一个树的叶子开始往上编历。。。^o^

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我