Hello World
Spiga

谈表达式树的缓存(2):由表达式树生成字符串

2009-03-17 00:58 by 老赵, 11131 visits

谈到使用表达式树作为key进行缓存,您脑海中最早浮现出来的解决方案是什么?老赵看来,大部分朋友的第一反应自然就是将作为key的表达式树,使用一定规则生成一个字符串。简而言之,这个生成字符串的规则F需要能够保证:

  1. 在同一个缓存空间内,同样的表达式树能够生成相同的字符串。
  2. 在同一个缓存空间内,不同的表达式树生成不同的字符串。

似乎有些罗嗦,朋友们明白便是。其中“在同一个缓存空间”的前提,其实只是放宽了后续要求的条件。因为在不同的缓存空间内,即使不同的表达式树生成了同样的字符串,它们也不会冲突;同理,不同缓存空间内的相同表达式树,也不一定非要得到相同的字符串——事实上,不同的缓存空间很可能对于字符串有不同的要求,这一点强求不得。

例如,在上一篇文章的例子中,构建“GetUserByID_100”和“GetUserByName_jeffz”两个字符串一般已经足够了。因为我们往往会将它们放在同一个缓存空间中(例如,UserService中的Cache容器),而与其它的缓存空间(例如AdminService)完全隔离。而如果打破了这个限制,那么这样的字符串生成规则就不够用了,我们就要设计新的字符串规则(如UserService_GetUserByID_100)。

对于之前的例子来说,构造简单的“GetUserByID_100”这种字符串已经足够进行缓存了,不过如果要把一个表达式树转化为一个字符串,并不是一件容易的事情。有朋友在我上一篇的文章后面回复到“直接用Expression<T>的ToString方法不行么?”答案是显而易见的(希望朋友们能够少猜测,多实践),例如:

Expression<Func<int, int>> exp1 = i => i;
Expression<Func<long, long>> exp2 = i => i;

Console.WriteLine(exp1.ToString());
Console.WriteLine(exp2.ToString());

您会发现两个明显不同的表达式树ToString后得到了同样的内容。表达式树的ToString方法是丢失信息的。例如,如果表达式树中涉及方法调用,那么ToString也只会包含方法名,而无法表现出方法所属的类,以及它的返回值。如果要把一个表达式树完整地生成字符串,自然要用到ExpressionVisitor。我们这里把转化用的类称为是SimpleKeyBuilder:

public class SimpleKeyBuilder : ExpressionVisitor
{
    public string Build(Expression exp)
    {
        this.m_builder = new StringBuilder();
        this.Visit(exp);
        return this.Key;
    }

    public string Key { get { return this.m_builder.ToString(); } }

    private StringBuilder m_builder;
}

Visit方法的访问是一个递归的过程,其中会调用不同的VisitXxx方法,而各VisitXxx方法又会再次调用Visit方法,最终遍历整个表达式树,而我们要做的,就是在遍历时记录足够的信息,使得两个表达式树“当且仅当”完全相同时才生成同样的字符串。嗯?“在同一缓存空间内”不见了?没错,为了保证解决方案的通用性,我们在这里假设缓存区间只有一个。

值得一提的是,整个遍历操作形成了一个完整的遍历序列,而这个序列有个重要的特点:“只有结构完全相同的两个表达式树,其各节点的遍历序列完全相同,反之亦然”。请注意,“结构完全相同”是“遍历序列相同”的“充分并必要条件”,但是“结构完全相同”是“完全相同”的“必要但不充分条件”。因此“遍历序列相同”并不能保证“完全相同”,这是因为ExpressionVisitor在遍历表达式树时只关注其结构,而不关注其细节。例如某个参数的类型,某个常量的值,都不属于“结构”的范畴。因此我们在生成字符串时,需要记录的并不只是遍历的路径,还需要包括各详细信息。

方便起见,我们先准备一些辅助方法,它们会将“各信息”一一放入StringBuilder中:

protected virtual SimpleKeyBuilder Accept(int value)
{
    this.m_builder.Append(value).Append("|");
    return this;
}

protected virtual SimpleKeyBuilder Accept(bool value)
{
    this.m_builder.Append(value ? "1|" : "0|");
    return this;
}

protected virtual SimpleKeyBuilder Accept(Type type)
{
    this.m_builder.Append(type == null ? "null" : type.FullName).Append("|");
    return this;
}

protected virtual SimpleKeyBuilder Accept(MemberInfo member)
{
    if (member == null)
    {
        this.m_builder.Append("null|");
        return this;
    }

    return this.Accept(member.DeclaringType).Accept(member.Name);
}

protected virtual SimpleKeyBuilder Accept(object value)
{
    this.m_builder.Append(value == null ? "null" : value.ToString()).Append("|");
    return this;
}

然后再遍历每个节点的时候,我们将数据不断地推入:

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

    this.Accept("$b$").Accept((int)exp.NodeType).Accept(exp.Type);
    var result = base.Visit(exp);
    this.Accept("$e$");

    return result;
}

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

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

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

...

完整的代码不止如此,虽然我们不需要覆盖(override)所有ExpressionVisitor的方法,但是一些必要的元素还是不可或缺的。不过,关键之处并不在这里。假设我们的VisitXxx方法已经能够完整地描述各数据,但是那些Accept方法足够详细吗?答案是否定的,至少之前的代码便有几点问题:

  1. 在描述一个Type时,FullName提供的信息完整吗?是否需要AssemblyQualifiedName?(这点请朋友们自行思考,或者一起讨论一下)。
  2. 在描述一个MemberInfo时,难道只记录它的DeclaringType和Name就够了吗?
  3. 在描述一个Object时,会使用ToString方法来进行记录。

显而易见,第三个问题是无法满足要求的。因此,如果您需要在正式场合使用这个方法,就必须根据您自己的需求来修改一下这方面的问题——例如,使用Serialize?亦或是,约定在此出现的每个相同类型的对象,它们的ToString方法都进行了合适地重载。

如果您的“嗅觉”比较灵敏,应该已经发现这个解决方案的缺点了:那就是字符串会特别庞大。这点并非无法改进,例如您可以把一些重复的,占用数据量大的信息替换成数据量小的信息——其实就是传统的进行数据压缩的算法。不过这方面编程相对较为复杂,且属于优化阶段而不能说明解决方案的真正思路,因此这就留给朋友们作为练习吧。

如果您感兴趣的话,还可以看一下http://code.msdn.microsoft.com/exprserialization,它提供了表达式树的完整的序列化功能,它可以把一个表达式树对象与XML进行双向转化。不过其字符串体积也无可避免的庞大,谁让表达式树天生就那么复杂呢?

当然,如之前所说,Key的生成规则与缓存的划分密切相关。换句话说,如果您能在项目里对缓存空间进行适当的划分,那么在这样的前提下您也可以使用“不那么详细”的生成规则,这有可能会进一步压缩字符串的体积。

实现了SimpleKeyBuilder,那么SimpleKeyCache的编写自然易如反掌,不加赘述:

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

    public T Get(Expression key, Func<Expression, T> creator)
    {
        T value;
        string cacheKey = new SimpleKeyBuilder().Build(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();
        }
    }
}

那么这个解决方案的时间复杂度是多少呢?假设表达式树有m个节点,缓存里有n个对象。那么从理论上说,构造一个Key的时间复杂度是O(m),而通过Key从字典里进行查询的时间复杂度是O(1),因此该解决方案的时间复杂度是O(m)

不过这是个理论值,其实际的结果呢?大家不妨思考一下,老赵在介绍完全部5种解决方案之后会单独开篇讨论一下这方面的问题。

 

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

相关文章:

Creative Commons License

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

Add your comment

67 条回复

  1. volnet(可以叫我大V)
    *.*.*.*
    链接

    volnet(可以叫我大V) 2009-03-17 01:00:00

    刚好逛到首页,沙发完再看

  2. 老赵
    admin
    链接

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

    --引用--------------------------------------------------
    volnet(可以叫我大V): 刚好逛到首页,沙发完再看
    --------------------------------------------------------
    我总是打算花1小时写完的文章结果花了2小时,果然是搞软件的,按时完工几乎不可能。

  3. wingoo
    *.*.*.*
    链接

    wingoo 2009-03-17 01:03:00

  4. 老赵
    admin
    链接

    老赵 2009-03-17 01:09:00

    --引用--------------------------------------------------
    wingoo: 早
    --------------------------------------------------------
    早,不过兄弟我要去睡了。

  5. volnet(可以叫我大V)
    *.*.*.*
    链接

    volnet(可以叫我大V) 2009-03-17 01:30:00

    public class SimpleKeyBuilder : ExpressionVisitor

    这样的继承不好,因为两者之间的多态是骗人的,所以用组合会比较好

  6. volnet(可以叫我大V)
    *.*.*.*
    链接

    volnet(可以叫我大V) 2009-03-17 01:32:00

    Jeffrey Zhao: --引用--------------------------------------------------
    wingoo: 早
    --------------------------------------------------------
    早,不过兄弟我要去睡了。
    --------------------------------------------------------
    这么早睡了?天,越来越不像你了,哈哈

  7. 老赵
    admin
    链接

    老赵 2009-03-17 01:36:00

    --引用--------------------------------------------------
    volnet(可以叫我大V): public class SimpleKeyBuilder : ExpressionVisitor

    这样的继承不好,因为两者之间的多态是骗人的,所以用组合会比较好
    --------------------------------------------------------
    哪里骗人了,你组合一个试试看。除非使用新的遍历结构,比如SAX的XML遍历方式,如果用ExpressionVisitor就没得选择。

  8. 老赵
    admin
    链接

    老赵 2009-03-17 01:38:00

    @volnet(可以叫我大V)
    hmmm……我似乎懂你的意思了,也知道你为什么会想错了,哈哈。
    建议可以下载代码调试一下,还有看看ExpressionTree到底是做什么的,不要光从我给的代码片段上来看……

  9. volnet(可以叫我大V)
    *.*.*.*
    链接

    volnet(可以叫我大V) 2009-03-17 01:38:00

    我的意思是,永远不会把SimpleKeyBuilder 的对象像多态一样地去使用,因为它的目的很单纯,所以把它嵌进去会比较好

  10. 老赵
    admin
    链接

    老赵 2009-03-17 01:40:00

    --引用--------------------------------------------------
    volnet(可以叫我大V): 我的意思是,永远不会把SimpleKeyBuilder 的对象像多态一样地去使用,因为它的目的很单纯,所以把它嵌进去会比较好
    --------------------------------------------------------
    听不懂,我觉得是你理解错了,你写一个“嵌进去的”试试看吧。

  11. 老赵
    admin
    链接

    老赵 2009-03-17 01:42:00

    @volnet(可以叫我大V)
    这个遍历的确是要基于多态才能作的啊,所以要调试,调试……嗯嗯,看看代码是怎么左右翻飞上蹿下跳的。

  12. volnet(可以叫我大V)
    *.*.*.*
    链接

    volnet(可以叫我大V) 2009-03-17 01:43:00

    不过想了想,也不好嵌,ExpressionVisitor貌似是abstract

  13. 老赵
    admin
    链接

    老赵 2009-03-17 01:48:00

    --引用--------------------------------------------------
    volnet(可以叫我大V): 不过想了想,也不好嵌,ExpressionVisitor貌似是abstract
    --------------------------------------------------------
    这不是关键,ExpressionVisitor类是自己的,改个protected/public,abstract之类的都是很简单的。
    你别猜阿,调试一下,看看代码是怎么在子类父类的实现之间穿梭的。

  14. 老赵
    admin
    链接

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

    --引用--------------------------------------------------
    volnet(可以叫我大V): 这么早睡了?天,越来越不像你了,哈哈
    --------------------------------------------------------
    你又忘了我是搞软件的,拖进度是必然的——嗯,现在真去睡了

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

    哈哈1[未注册用户] 2009-03-17 07:52:00

    弄个GUID,缓存Expression<Func<int, int>>,不可以吗
    不行GUID+命名

  16. 沉默杨仔
    *.*.*.*
    链接

    沉默杨仔 2009-03-17 08:30:00

    留名,学习

  17. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2009-03-17 08:42:00

    学习!!!!!!!!!!!!!

  18. 老赵
    admin
    链接

    老赵 2009-03-17 08:51:00

    --引用--------------------------------------------------
    哈哈1: 弄个GUID,缓存Expression<Func<int, int>>,不可以吗
    不行GUID+命名
    --------------------------------------------------------
    如果你能找到一个合理的Expression => GUID的映射,保证每个相同Expression得到同样的GUID,不同的则对应不同的GUID,那么当然可以。
    不过,怎么做呢?呵呵。

  19. 钧梓昊逑
    *.*.*.*
    链接

    钧梓昊逑 2009-03-17 08:52:00

    为什么要生成字符串,为什么不重写 GetHashCode ?

  20. 老赵
    admin
    链接

    老赵 2009-03-17 08:53:00

    @钧梓昊逑
    嗯,打个比方说,我有一个Expression<Func<int, int>>对象了,您试试看重写一下它的GetHashCode?
    而且,对于缓存键来说,光重写GetHashCode就够了吗?
    自然,目前的解决方案肯定不是所有情况下都最好的,不过这个系列的文章最后我也会谈到,有时候这个解决方案也是仅有的,或者说最合适的选择。

  21. 钧梓昊逑
    *.*.*.*
    链接

    钧梓昊逑 2009-03-17 08:58:00

    HMM,生成字符串比较直观,找到一个表达式树到整形的函数f而且满足那两个条件会比较困难,用一个字符串中转,比较好处理一点

  22. 老赵
    admin
    链接

    老赵 2009-03-17 09:01:00

    @钧梓昊逑
    您有一个误区,那就是认为“对于缓存键来说,光重写GetHashCode就足够了”,不过您要知道,您是找不到这样一个函数的。
    因为Int32是有限的,而表达式树是无限的,所以不可能找到满足条件的Exp -> Int32的映射。
    当然,您的想法思路是有价值的,可惜没有继续深入下去,我还有4种缓存策略要谈,您可以继续关注一下。

  23. 钧梓昊逑
    *.*.*.*
    链接

    钧梓昊逑 2009-03-17 09:02:00

    是了,类库提供的开泛型类型没办法重写唉
    只能通过外部的方法或者扩展方法来实现了

  24. 钧梓昊逑
    *.*.*.*
    链接

    钧梓昊逑 2009-03-17 09:04:00

    这样的完全映射的确是找不到的,但是我们的存储空间也不是无限的,所以只要碰撞概率小于能够接受的范围就OK了,当然,另外还得重写Equals方法

  25. 老赵
    admin
    链接

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

    @钧梓昊逑
    您无法保证在“有限的存储空间”内就“不会遇到这样的情况”,而且对于一个映射F来说,一旦出现了碰撞那么每次都会出现碰撞,这不是“再试一次”就能搞定的问题。
    因此说,“碰撞概率小于一定接受范围就OK了”是不够的,这也是为什么要重写Equals方法的原因。重写Equals方法不是“可选”的,是“必须”的。
    重写GetHashCode不是为了找到一对一映射(因为这是找不到的),它的目的是离散化,减少Equals方法的比较次数。

  26. deerchao
    *.*.*.*
    链接

    deerchao 2009-03-17 09:19:00

    我觉得这个思路太复杂,性能太低.
    可以考虑综合GetHashCode,以及表达式值相等判断来做一个更简单更高效的算法.
    其实也就相当于做一个支持一键多值的Dictionary--这个东西应该是已经有了,我记得好像PowerCollections里有吧. 这个Dictionary的Key是hashcode,值是Expression和自动生成用作缓存键的GUID字符串.
    当然如果实际使用中hashcode碰撞太厉害,还得针对具体情况分析和微调.

  27. 有所为,有所不为
    *.*.*.*
    链接

    有所为,有所不为 2009-03-17 09:34:00

    老赵一天就睡六个小时?
    够吗?经常运动吗?注意身体啊。。。。
    下次上海再活动,希望能见到本人,HOHO

  28. 老赵
    admin
    链接

    老赵 2009-03-17 09:35:00

    @deerchao
    嗯?我现在是Expresssion作为key,不是把Expression作为Value。
    如果PowerColleciton里有的话,不如介绍一下?
    的确综合GetHashCode,表达式相等会高效,但是不简单,思路还是现在的简单吧,呵呵。接下去我会谈到更好的做法的。
    不过其实这个做法经过测试,也并不是说特别低到哪里去,使用GetHashCode+Equals也不是最高效的。总之,这次的话题很有意思,呵呵。

  29. DarthVader
    *.*.*.*
    链接

    DarthVader 2009-03-17 10:08:00

    粗看了一下你的文章,不太了解你的需求。在DLR中有对CallSite的Cache,实际上也是一种对表达式的缓存,处理方法和你现在的不一样,简单说他缓存的是表达式的表述(GetUserByID),你缓存的好像是具体的表达式(GetUserByID_100)。

  30. 老赵
    admin
    链接

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

    @DarthVader
    简单的说,我是在实现一个Dictionary<Expression, T>,把不同的Expression实例,通过某种方法,可以作为字典的Key进行存取。
    比如第一篇文章,就是把Expression转化为字符串,再作为Key进行缓存。

  31. deerchao
    *.*.*.*
    链接

    deerchao 2009-03-17 11:13:00

    我说的只是根据表达式生成键生成这个功能里用得到一个MultiDictionary(PowerCollections里有这个类).至于真正的缓存功能,我根本没考虑.

    其实我的思路非常简单:来一个表达式,我就分配给你一个Key,并记录下来,以备查询.

    具体做法是这样:
    对于一个表达式,我们求它的hashcode,然后在一个多值Dictionary里找键为这个hashcode的所有值.
    如果有多个的话--意味着多个表达式与当前表达式具有相同的hashcode,我们只能一个个与当前表达式进行值比较,看哪个值与它相等.也有可能与所有已有表达式都不相等,那样的话就得生成一个新条目,存入我们的词典. 这个过程意味着我们要保存所有值不相等的表达式.好在表达式对象生成之后都是不可更改的.
    如果有一个,其实也和上面一样,判断是否相等,然后返回原先生成的结果,或者生成新结果并记录.
    如果没有,当然就是生成新结果了.

    也就是说,我的MultiDictionary的Key是个int, Value是 Expression 和 string的Turple.我觉得保存一份表达式的引用是没什么大问题的,因为通常要缓存的值里本身就有键的引用.

  32. deerchao
    *.*.*.*
    链接

    deerchao 2009-03-17 11:17:00

    当然我的解决方案是不能长时期连续运行--如果程序里生成的Expression会经常动态变化(不在一个有限集合内)的话,不然那个登记本会越来越来满,效率越来越低..

    改进方案是把这个东西整合到Cache里边去.从Cache里移除表达式后,也从那个登记本里移除记录的条目. 我这个方法属于高中生用风扇吹空盒的类型.还是期待你的更加高级的办法 :)

  33. 老赵
    admin
    链接

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

    @deerchao
    你说的就是标准的哈希表的实现方式阿,呵呵。
    你说的一点没错,其实我也是这样想过的,以后的文章里就会提到。思路比较简单,但是实现上还是比较复杂的。其实,这个SimpleKeyBuilder在我的思考中从来只是个构想,没有写下来过,是为了这系列文章的完整性而补充的,呵呵。
    希望您可以继续关注后面的文章,我尽量以一天一篇的速度进行更新。:)

  34. 老赵
    admin
    链接

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

    --引用--------------------------------------------------
    deerchao: 当然我的解决方案是不能长时期连续运行--如果程序里生成的Expression会经常动态变化(不在一个有限集合内)的话,不然那个登记本会越来越来,效率越来越低..

    改进方案是把这个东西整合到Cache里边去.从Cache里移除表达式后,也从那个登记本里移除记录的条目.
    --------------------------------------------------------
    嗯,这就是另外一个方面的内容的,我们先不去考虑它。
    在实际生产中,除非动态生成Expression,生成的表达式树总是在一个有限的集合内的。

  35. deerchao
    *.*.*.*
    链接

    deerchao 2009-03-17 11:32:00

    动态生成Expression的可能性还是相当大的,因为Expression的现在很多都应用在翻译成SQL上.
    而各种查询条件的参数(Expression里的常量)就可能来自于用户输入.

  36. 老赵
    admin
    链接

    老赵 2009-03-17 11:41:00

    @deerchao
    嗯,说得对,Schema是相当有限的,但算上常量就无穷无尽了。
    不过这个处理方式其实就是缓存一样的做法:如果Value因为过期等原因被抛弃了,那么保留的key也一并被回收便是。

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

    韦恩卑鄙 2009-03-17 13:22:00

    --引用--------------------------------------------------
    Jeffrey Zhao: @deerchao

    嗯?我现在是Expresssion作为key,不是把Expression作为Value。

    --------------------------------------------------------



    那似乎不需要生成string 只需要用vistor +重写Equals 就可以做到?

    还在看得半懂不懂中

  38. 老赵
    admin
    链接

    老赵 2009-03-17 13:56:00

    @韦恩卑鄙
    思路么,我上一篇文章说过,会把大家的思路带着绕一圈,这样才有比较,哈哈。不过事实上字符串也不是完全不可取的,有些情况下也是必不可少的使用方式,例如需要远程通信时,字符串可用于直接序列化输出。其他方法往往只是单进程内搞搞。
    各位大牛们的思路以后都会提到的,别急,别急……

  39. catcher
    *.*.*.*
    链接

    catcher 2009-03-17 13:58:00

    结构完全相同”是“遍历序列相同”的“充分并必要条件”,但是“结构完全相同”是“完全相同”的“必要但不充分条件”。

    这句话不符合逻辑吧,虽然我明白你的意思

  40. 老赵
    admin
    链接

    老赵 2009-03-17 14:27:00

    @catcher
    你是指那个“但是”不符合逻辑?
    上面这句话没有因果关系,是陈述并列的两个命题。

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

    韦恩卑鄙 2009-03-17 15:46:00

    --引用--------------------------------------------------
    Jeffrey Zhao: @韦恩卑鄙

    思路么,我上一篇文章说过,会把大家的思路带着绕一圈,这样才有比较,哈哈。不过事实上字符串也不是完全不可取的,有些情况下也是必不可少的使用方式,例如需要远程通信时,字符串可用于直接序列化输出。其他方法往往只是单进程内搞搞。

    各位大牛们的思路以后都会提到的,别急,别急……
    --------------------------------------------------------
    我就知道你是卖关子阿

    等你把实话都交待了
    回头干脆做个 ExpIdnfer 专门生成唯一guid算了,哼哼

  42. 老赵
    admin
    链接

    老赵 2009-03-17 15:51:00

    @韦恩卑鄙
    怎么做?谈一下?

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

    韦恩卑鄙 2009-03-17 15:56:00

    我在等你实话全交待阿


    根据你绕一圈的结果 自然会有一个比较好的办法生成简短有效的特征量了。 我看好你!

  44. 老赵
    admin
    链接

    老赵 2009-03-17 16:01:00

    @韦恩卑鄙
    说实话,没有……真的不骗你……

  45. ITAres
    *.*.*.*
    链接

    ITAres 2009-03-17 16:27:00

    字符串会特别庞大的问题,可以用gethashcode()来解决。。。。

  46. 老赵
    admin
    链接

    老赵 2009-03-17 16:29:00

    @ITAres
    你用GetHashCode,就必须还要重载Equals,那么你怎么写Equals方法呢?光提供GetHashCode是一点作用也没有的……还有就是GetHashCode该怎么写呢?都不是一句话能说清楚的啊,呵呵。
    大家要相信老赵,如果那么简单的话,我就不会写这些文章了,嗯嗯……
    // 范兄弟最近可好?

  47. ITAres
    *.*.*.*
    链接

    ITAres 2009-03-17 16:51:00

    @Jeffrey Zhao
    赵老大,还记得我啊。。太开心了。


    我的意思是说:string expressionString = "很长很长的字符串";

    string cacheKey = expressionString.GetHashCode();

  48. 老赵
    admin
    链接

    老赵 2009-03-17 16:54:00

    @ITAres
    不够啊,GetHashCode()是一个散烈函数,是把n多东西变成一个int32,可能两个不同的字符串的GetHashCode结果是一样的……

  49. ITAres
    *.*.*.*
    链接

    ITAres 2009-03-17 17:04:00

    @Jeffrey Zhao
    唉,算法太烂了,刚才了解了一下散列算法。。是有这个问题。

    虽然机率很小,但还是存在的。

    赵神童天下第一

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

    韦恩卑鄙 2009-03-17 17:13:00

    --引用--------------------------------------------------
    ITAres: @Jeffrey Zhao
    唉,算法太烂了,刚才了解了一下散列算法。。是有这个问题。

    虽然机率很小,但还是存在的。

    赵神童天下第一
    --------------------------------------------------------
    那么 把 一个字符串 md5一次 sha1一次 shaxx一次 把三个结果拼在一起
    还会碰撞的几率是多少涅。。。。

  51. ITAres
    *.*.*.*
    链接

    ITAres 2009-03-17 17:19:00

    @韦恩卑鄙
    效率大低了吧。。

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

    韦恩卑鄙 2009-03-17 17:26:00

    要算算缓存造成的效能节省咯

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

    韦恩卑鄙 2009-03-17 17:28:00

    我个人是觉得
    虽然md5类的算法 存在碰撞 但是两个碰撞都是一个结构完整的xml文档 概率是*(—·#—(*·—#(*·#的

    所以不一定要算三次 一个md5 也许就不大可能碰撞了


    如果缓存节省的消耗不如一次md5 那么还真是没什么意思了

  54. 老赵
    admin
    链接

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

    @韦恩卑鄙
    不知道,不过从无限的集合映射到有限的集合,肯定会重复。而且同时用用多个散列函数,是否能更散列……不知道啊,凭感觉有可能散列度不升反降。

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

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

    不会哦 两个算法就算只有1bit的差别 那也会增加有限集合容量一倍
    何况md5 和sha 是绝对不会一样的

    sha1-sha(n)我没研究过

  56. 老赵
    admin
    链接

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

    @韦恩卑鄙
    这你说的我都知道,但是组合使用两者的效果为什么就比用一个好呢?

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

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

    哎? 减少碰撞概率到无限接近于零 不就是接近唯一么
    GUID 本身也是低概率碰撞么
    假设 md5(str) 碰撞概率是 10^10
    sha1(str)碰撞概率是 10^15
    那么 md5(str) & sha1(str) 碰撞概率 就是 10^15 到 10^25
    干脆就忽略碰撞可能吧

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

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

    这里说的不是value相加
    我是说byte[]的连接

  59. 老赵
    admin
    链接

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

    @韦恩卑鄙
    我明白你的意思,但是为啥组合一下概率就是相乘呢?那么不断hash/hash/hash那岂不是概率小到比GUID重复还低了?
    我觉得不会那么简单。

  60. catcher
    *.*.*.*
    链接

    catcher 2009-03-18 12:33:00

    --引用--------------------------------------------------
    Jeffrey Zhao: @catcher
    你是指那个“但是”不符合逻辑?
    上面这句话没有因果关系,是陈述并列的两个命题。
    --------------------------------------------------------
    @Jeffrey Zhao
    我觉得应该这么说吧
    结构完全相同”是“遍历序列相同”的“充分条件”,“遍历完全相同”是“结构完全相同”的“必要条件”。
    充分必要条件一般是两者可以相互推出

  61. 老赵
    admin
    链接

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

    @catcher
    是啊,充要条件就是要可以互相推出的。
    不过,文章写得没错,“结构完全相同”是“遍历序列相同”的确是等价的,可以互相推出的。
    只是说结构、遍历序列而已,不包含其中的数值云云。具体原因可以看一下ExpressionVisitor的实现。

  62. catcher
    *.*.*.*
    链接

    catcher 2009-03-18 13:27:00

    哦,原来你的意思只指树的同构。但这也不是等价的,如下二树的前序遍历都是a,b,c,但结构不同啊。
    a
    / \
    b c


    a
    /
    b
    \
    c

  63. 老赵
    admin
    链接

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

    @catcher
    表达式树的遍历不是二叉树的前续遍历啊,表达式树的遍历会涉及到节点的类型,比如MethodCallExpression还会遍历它的所有ParameterExpression。
    具体实现看一下ExpressionVisitor的实现吧。
    // 其实我的确也有所怀疑,但是我还没有找出反例(似乎找的出,似乎找不出,我再仔细想想,呵呵),也没有证明这个命题……
    // 但是我可以证明文章里的方法是正确的,因为文章在构造字符串时形成了“边界”。换句话说,因为我补充了一些条件,因此那个命题成立了。

  64. catcher
    *.*.*.*
    链接

    catcher 2009-03-18 16:35:00

    我没明白表达式树到底和普通树有什么本质的区别(看了下msdn好像是普通的树,然后好像加上了对参数的索引)。 我觉得二叉树是树的一种特例,所以拿他来举了一下反例,普通树也应该一样吧,呵呵。
    至于你说到表达树会涉及到的节点类型的问题,那如果两个表达式刚好所有节点都对应一样,那又如何?

    其实我的观点是不能靠一种遍历顺序来确定树的结构(丢失了一些信息),至于结点的值或类型那是另一回事。

  65. 老赵
    admin
    链接

    老赵 2009-03-18 16:41:00

    @catcher
    当然有本质区别,呵呵。
    表达式树中每个节点是有类型的,不同类型的节点使用不同的方法去访问(VisitUnary,VisitBinary等等),不同方法的访问方式也不同,由此构成了一个访问序列(也就是方法调用序列)。这与普通二叉树不同,因为普通二叉树的每个节点是不区分类型的,并且使用同一个方法来访问。
    因此我说,如果结构相同,那么遍历得到的序列也相同,反之也成立。

  66. 老赵
    admin
    链接

    老赵 2009-03-18 16:49:00

    @catcher
    如果要举反例,其实就是要找出两个表达式树exp1和exp2它们的结构不同,但是遍历时产生的方法调用序列是相同的,也就是说都是:
    M1 -> M2 -> M3 -> ... -> Mn,其中M1...Mn都属于VisitUnary,VisitBinary等方法。

  67. mhsy2003
    122.225.55.*
    链接

    mhsy2003 2010-08-04 10:59:05

    请问,文章中所说的

    完整的代码不止如此,虽然我们不需要覆盖(override)所有ExpressionVisitor的方法,但是一些必要的元素还是不可或缺的。

    这里如何判断哪些元素是必要的,我初学Expression。自己写了一遍ExpressionVisitor,理解了表达式树遍历的流程,但是我不知道这里SimpleBuilder来说为什么你的代码里面那些overrider是必须的元素,能解释下么,非常感谢。

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我