技术开发 频道

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

    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),这也达到了最为理想的时间复杂度。

0
相关文章