技术开发 频道

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

【IT168技术文档】

转载自Jeff Zhao的博客

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

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

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

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

    想到这里,您应该已经得出结论了……这不就是散列值吗?在.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;
    }

    ...
    }

   

0
相关文章