Hello World
Spiga

谈表达式树的缓存(5):引入散列值

2009-03-20 01:40 by 老赵, 12472 visits

到目前为止,我们已经实现了三种缓存方式:首先我们设法构建唯一字符串,但是由于它的代价较高,于是我们使用了前缀树进行存储;又由于前缀树在实际操作中所花的时间和空间都有不令人满意之处,我们又引入了二叉搜索树。那么二叉搜索树又有什么缺点呢?其实前文已经谈到过了,那就是从理论上来说,它的时间复杂度相对前两个要高,在最坏情况下将会出现O(m * log(n))的时间复杂度——每次比较两个前缀树需要耗费O(m),共比较O(log(n))次。

很显然,与最理想的时间复杂度O(m)相比,其差距就在于n,也就是缓存空间中已有的元素数量。如果元素越多,则n越大,log(n)也会随之增大,则耗费O(m)的“次数”也就越多。换句话说,如果我们要改进性能,就要想办法减少比较次数。一个比较容易想到的做法便是对缓存空间中的n个元素进行“分组”,在每次查询时首先使用很小的时间复杂度,确定被查询的表达式树处于哪个组中,然后只需要与这个组中为数不多的几个元素进行比较便可。这样耗费O(m)的操作次数就少了,性能随之提高。

既然要进行分组,那么我们其实就是要从每个表达式树中提取“特征值”,再根据这个“特征值”进行分组——不过这是有条件的,例如:

  1. 特征值计算要尽可能的快,否则光计算一次特征值就消耗大量时间,得不偿失。
  2. 根据特征值要能够快速确定分组,原因如第1点。
  3. 特征值要可以将元素尽可能地分散在不同组中,这样每个组里的元素会变得更少,更节省比较次数。

想到这里,您应该已经得出结论了……这不就是散列值吗?在.NET Framework中,一个对象的散列值为一个32位整型数值,然后便可以从一个以Int32类型为键的字典中快速地获取一个“分组”,这就已经满足了上述第2点要求。因此,问题的关键在于如何“快速”地求出一个表达式树的散列值,并且要使这个散列值能够尽可能地分布均匀。一个表达式树的散列值,显然是由它内部的元素组成,因此我们只需要遍历它的每个元素,将这些元素散列值结合为一个单一的散列值即可——这是一个O(m)的操作,非常高效。

为此,老赵实现了一个ExpressionHasher类,用于计算一个表达式树的散列值,如下:

public class ExpressionHasher : ExpressionVisitor
{
    public int Hash(Expression exp)
    { 
        this.HashCode = 0;
        this.Visit(exp);
        return this.HashCode;
    }

    public int HashCode { get; protected set; }

    protected virtual ExpressionHasher Hash(int value)
    {
        unchecked { this.HashCode += value; }
        return this;
    }

    protected virtual ExpressionHasher Hash(bool value)
    {
        unchecked { this.HashCode += value ? 1 : 0; }
        return this;
    }

    private static readonly object s_nullValue = new object();

    protected virtual ExpressionHasher Hash(object value)
    {
        value = value ?? s_nullValue;
        unchecked { this.HashCode += value.GetHashCode(); }
        return this;
    }

    ...
}

ExpressionHasher有个Hash方法,可用于计算一个表达式数的散列值。与之前的几种ExpressionVisitor实现类似,ExpressionHasher也准备一些辅助方法供其他方法调用。这些辅助方法接受不同类型的参数,完全避免了数据的装箱/拆箱,尽可能保持算法的高效。从上面的代码看出,我们不断地向这些辅助方法内传入对象时,它们会被累加到HashCode属性中——这就是老赵在这里使用的“组合方式”,将表达式树中每个元素的散列值进行组合,最终成为整个表达式数的散列值。老赵无法证明这是一种优秀的散列组合算法,但是从测试上来看,这么做的效果还是不错的(事实上,老赵随机生成了大量表达式还没有出现碰撞)。更关键的一点是,这么做非常高效,如果将这些元素拼接起来,并得到最终字符串的散列值可能会有更好的结果,但是其性能就比整数的相加要差许多了。

现在,我们只需要在Visit每个节点的时候,把节点的属性作为表达式树的每个元素传入对应的辅助方法便可,以下为部分代码:

protected override Expression Visit(Expression exp)
{
    if (exp == null) return exp;

    this.Hash((int)exp.NodeType).Hash(exp.Type);
    return base.Visit(exp);
}

protected override Expression VisitBinary(BinaryExpression b)
{
    this.Hash(b.IsLifted).Hash(b.IsLiftedToNull).Hash(b.Method);
    return base.VisitBinary(b);
}

protected override Expression VisitConstant(ConstantExpression c)
{
    this.Hash(c.Value);
    return base.VisitConstant(c);
}

protected override Expression VisitMemberAccess(MemberExpression m)
{
    this.Hash(m.Member);
    return base.VisitMemberAccess(m);
}

protected override Expression VisitMethodCall(MethodCallExpression m)
{
    this.Hash(m.Method);
    return base.VisitMethodCall(m);
}

...

按照我们刚才的设想,首先计算出一个表达式树的散列值,然后从字典中获取具体的一个分组,再从这个分组中进行查找。使用这个方法则得到了HashedListCache:

public class HashedListCache<T> : IExpressionCache<T> where T : class
{
    private ReaderWriterLockSlim m_rwLock = new ReaderWriterLockSlim();
    private Dictionary<int, SortedList<Expression, T>> m_storage =
        new Dictionary<int, SortedList<Expression, T>>();

    public T Get(Expression key, Func<Expression, T> creator)
    {
        SortedList<Expression, T> sortedList;
        T value;

        int hash = new ExpressionHasher().Hash(key);
        this.m_rwLock.EnterReadLock();
        try
        {
            if (this.m_storage.TryGetValue(hash, out sortedList) &&
                sortedList.TryGetValue(key, out value))
            {
                return value;
            }
        }
        finally
        {
            this.m_rwLock.ExitReadLock();
        }

        this.m_rwLock.EnterWriteLock();
        try
        {
            if (!this.m_storage.TryGetValue(hash, out sortedList))
            {
                sortedList = new SortedList<Expression, T>(new ExpressionComparer());
                this.m_storage.Add(hash, sortedList);
            }

            if (!sortedList.TryGetValue(key, out value))
            {
                value = creator(key);
                sortedList.Add(key, value);
            }
            
            return value;
        }
        finally
        {
            this.m_rwLock.ExitWriteLock();
        }
    }
}

计算一个表达式树的散列值需要耗费O(m)的时间复杂度,从字典中查找分组需要O(1),如果散列值够好的话,每个分组中的表达式树数量(k)应该非常少,这样从中进行查询的时间复杂度(O(log(k)))就非常接近于常数了。因此,HashedListCache的查找操作,其时间复杂度为O(m),这也达到了最为理想的时间复杂度。

到目前为止,我们为了解决表达式树的缓存问题,已经提出了4种不同的处理方式,并且编写了多个操作表达式树的辅助类:

  1. SimpleKeyBuilder:将表达式树构造成唯一的字符串。
  2. PrefixTreeVisitor:根据表达式树构造一颗前缀树。
  3. ExpressionComparer:比较两个表达式树的“大小”关系。
  4. ExpressionHasher:计算一个表达式树的散列值。

回想起第一种做法,我们使用最原始的方式,使用字典来存储对象,不过我们需要拼接出一个庞大的字符串,因为它具有“唯一性”。但是其实从那时开始,我们就已经走了一条弯路。在.NET Framework中,一个对象如果要作为字典的“键”,难道一定要是字符串吗?很显然,答案是否定的。事实上,任何类型的对象都可以作为字典的键,而字典认为两个“键”对象相同依靠的是对象的GetHashCode方法和Equals方法。字典的整个查询分两步走:

  1. 首先根据GetHashCode获取对象散列值,用于确定需要查找的对象在那个分组(或者说是“桶”,在数据结构中称为散列表的“buckets”)中。
  2. 每个分组的对象数量很少,然后在使用Equals方法依次进行比较,最终得到相同的那个值。

因为有了ExpressionComparer和ExpressionHasher,我们已经可以非常轻松地实现那个作为“键”的对象了:

private class CacheKey
{
    private IComparer<Expression> m_comparer = new ExpressionComparer();

    public Expression Expression { get; private set; }

    public CacheKey(Expression exp)
    {
        this.Expression = exp;
    }

    private int m_hashCode;
    private bool m_hashCodeInitialized = false;

    public override int GetHashCode()
    {
        if (!this.m_hashCodeInitialized)
        {
            this.m_hashCode = new ExpressionHasher().Hash(this.Expression);
            this.m_hashCodeInitialized = true;
        }

        return this.m_hashCode;
    }

    public override bool Equals(object obj)
    {
        if (obj == null) return false;
        if (obj.GetType() != this.GetType()) return false;

        CacheKey other = (CacheKey)obj;
        return this.m_comparer.Compare(this.Expression, other.Expression) == 0;
    }
}

最后再实现一个DictionaryCache:

public class DictionaryCache<T> : IExpressionCache<T> where T : class
{
    private ReaderWriterLockSlim m_rwLock = new ReaderWriterLockSlim();
    private Dictionary<CacheKey, T> m_storage = new Dictionary<CacheKey, T>();

    public T Get(Expression key, Func<Expression, T> creator)
    {
        T value;
        CacheKey cacheKey = new CacheKey(key);

        this.m_rwLock.EnterReadLock();
        try
        {
            if (this.m_storage.TryGetValue(cacheKey, out value))
            {
                return value;
            }
        }
        finally
        {
            this.m_rwLock.ExitReadLock();
        }

        this.m_rwLock.EnterWriteLock();
        try
        {
            if (this.m_storage.TryGetValue(cacheKey, out value))
            {
                return value;
            }

            value = creator(key);
            this.m_storage.Add(cacheKey, value);
            return value;
        }
        finally
        {
            this.m_rwLock.ExitWriteLock();
        }
    }
}

DictionaryCache的实现其实和HashedListCache比较接近,不过从理论上说,DictionaryCache的性能不如HashedListCache。因为同样在根据散列值获取到分组后,DictionaryCache中的分组元素数量可能会比HashedListCache要多(因为字典中多个散列值也可以在同一个分组中);同时,字典在同组的k个元素中找到指定元素使用O(k)的遍历算法,而二叉搜索树只要O(log(k))的时间复杂度——此消彼长,DictionaryCache的性能自然就要略差一些了。

至此,老赵在这个话题中计划谈起的5种解决方案都已经讲述完毕了,您觉得哪种做法的效果最好呢?在今后的文章中,老赵将会对5种解决方案进行性能上的比较并进行分析,同时给出每种方案的优点、缺点和改进余地——其实这些才是最重要的,朋友们千万不要错过,也欢迎大家和我一起讨论。

最后再学着打一个广告:如果朋友们喜欢老赵的文章,可以通过RSS订阅进行持续关注(订阅地址为http://www.cnblogs.com/JeffreyZhao/rss)。

 

完整代码下载:http://code.msdn.microsoft.com/ExpressionCache

相关文章:

Creative Commons License

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

Add your comment

20 条回复

  1. 横刀天笑
    *.*.*.*
    链接

    横刀天笑 2009-03-20 00:17:00

    沙发,抢到了,睡觉~~

  2. 老赵
    admin
    链接

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

    --引用--------------------------------------------------
    横刀天笑: 沙发,抢到了,睡觉~~
    --------------------------------------------------------
    好吧,我今天也要早睡,早上游泳,你们谁也别拦着我

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

    紫色永恒 2009-03-20 08:11:00

    受教了,RSS早就订了的
    ps 你要干嘛,谁拦得住你啊。。。

  4. 文明的天空
    *.*.*.*
    链接

    文明的天空 2009-03-20 08:11:00

    先抢个坐

  5. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-03-20 08:21:00

    老赵真是夜猫子啊,拦不住啊
    能用BST的话,也可以考虑用堆,虽然时间复杂度一样,不过常数小不少。
    堆是我狠喜欢的数据结构。
    当然Hash就更快咯,不过需要好好设计。好在Expression的Hash设计比较容易……

  6. 老赵
    admin
    链接

    老赵 2009-03-20 08:28:00

    --引用--------------------------------------------------
    紫色永恒: 受教了,RSS早就订了的
    ps 你要干嘛,谁拦得住你啊。。。
    --------------------------------------------------------
    病魔,我刚准备去游泳,但是拉肚子了,稀里哗啦

  7. 老赵
    admin
    链接

    老赵 2009-03-20 08:34:00

    --引用--------------------------------------------------
    JimLiu: 老赵真是夜猫子啊,拦不住啊
    能用BST的话,也可以考虑用堆,虽然时间复杂度一样,不过常数小不少。
    堆是我狠喜欢的数据结构。
    当然Hash就更快咯,不过需要好好设计。好在Expression的Hash设计比较容易……
    --------------------------------------------------------
    你搞错了吧,BST和堆虽然都是基于二叉树的,但是堆又不是用来根据某个key查找元素的。堆是用来查找最大(或最小)值的,所以适合实现优先队列(priority queues)。
    http://en.wikipedia.org/wiki/Heap_(data_structure)

  8. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-03-20 08:57:00

    @Jeffrey Zhao
    呃……这个,的确没考虑到,这里需要进行查找
    无视我……

  9. overred
    *.*.*.*
    链接

    overred 2009-03-20 09:22:00

    http://msdn.microsoft.com/en-us/library/ms379571.aspx#datastructures20_2_topic5
    The System.Collections.Hashtable Class
    The System.Collections.Generic.Dictionary Class

    =_=

  10. 老赵
    admin
    链接

    老赵 2009-03-20 09:29:00

    @overred
    咋了?

  11. overred
    *.*.*.*
    链接

    overred 2009-03-20 09:31:00

    @Jeffrey Zhao
    类似Dictionary的bucket做法。分段思想

  12. 老赵
    admin
    链接

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

    @overred
    什么叫做“类似”……本来就是在说Dictionary……

  13. overred
    *.*.*.*
    链接

    overred 2009-03-20 09:42:00

    @Jeffrey Zhao
    罪过。。。罪过

  14. deerchao
    *.*.*.*
    链接

    deerchao 2009-03-20 09:52:00

    弱弱地问一句,为什么求hash值时用unchecked +, 不用^?

  15. 老赵
    admin
    链接

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

    @deerchao
    异或适合两个hashcode求缓存,不一定适合聚合缓存,尤其是现在的情况下不少布尔值,他们的hashcode要么0要么1。如果用聚合,n ^ 1 ^ 1 == n,效果就变差了。
    感觉最好的效果,似乎还是拼接字符串——我打算下周给出一个更好的聚合方式,周末会努力一把的。

  16. 老赵
    admin
    链接

    老赵 2009-03-20 17:00:00

    话说,今天那个卑鄙韦恩到哪里去了?

  17. 链接

    DJ尐舞 2010-07-11 19:04:38

    protected virtual ExpressionHasher Hash(object value)
    {
        value = value ?? s_nullValue;
        unchecked { this.HashCode += value.GetHashCode(); }
        return this;
    }
    

    老赵,请问上面的value.GetHashCode(),是根据value的值计算的,还是根据引用呢?

  18. lixiong
    58.41.86.*
    链接

    lixiong 2011-03-22 19:52:23

    这个不能证明没有碰撞的吧.甚至是可以证明有碰撞的. 如果一但有一个碰撞就完蛋了.把人家数据库的drop当select cache起来了怎么办....

  19. 老赵
    admin
    链接

    老赵 2011-03-23 00:52:07

    @lixiong

    肯定有碰撞啊,无限的集合怎么可能一一映射到有限的集合。这里引入散列和Dictionary一个目的,就是减小碰撞,最后肯定要个“相等”比较的。

  20. lixiong
    131.107.0.*
    链接

    lixiong 2011-03-23 09:35:58

    看了msdn,才知道Dictionary是需要compare 和 hashcode两个协同工作的. 我以前一直以为只需要gethashcode就够了....

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我