谈表达式树的缓存（3）：使用前缀树

谈表达式树的缓存（3）：使用前缀树2011-09-30 博客园 Jeffrey Zhao在上一篇文章里我们设法将前缀树构造为一个唯一的字符串，然后使用字符串作为key缓存在字典中。这个想法非常直接，做法也不困难（在遍历时记录详细信息便可）。不过事实上，老赵在思考表达式树的缓存问题时，这种字符串拼接的方式只存在于脑海当中，而上文的实现是为了这一系列文章的完整性而特地编写的。这是因为它的缺点较为明显，正如上文所述，字符串拼接操作较为耗时耗资源，且很容易生成一个长度可观的字符串（并非不能优化，不过实现就复杂了）。于是我们现在设法选择另一个解决方案来处理这个问题。

不过现在，我们先来考虑另一个问题：比较两个字符串是否相同（例如实现一个String.Equals方法）。此时，我们往往会分几步进行：

判断字符串长度是否相等，如果不等，则两个字符串肯定不同。

从头遍历两个字符串，如果找到某一位不相同，则两个字符串相同。

如果完整遍历完整个字符串，则两者相同。

以上算法基本上是我们可以写出的最高效的比较算法。为什么这么说呢？原因主要有以下两点：

我们在比较时，首先使用最容易获得的信息（长度）进行判断，并且在合适的时候（发现某一位不同）及时返回，节省了时间。

比较时不需要保存完整信息（比较字符串的第n位时，从0到n-1位字符无需保留），这样在空间上也节省了下来。

那么我们来思考一下，为什么前一篇文章中谈到的字符串会性能差呢？其实他正是由于违反了上面的 “特点”：

需要对整个树进行完整编码，这样无法通过部分编码上排除各种状况，时间上耗费较大。

必须保留完整路径，造成字符串很长，导致空间上耗费也大。

与字符串比较略有不同，既然我们最终是要匹配完全相同的表达式树，那么一次完整的树遍历是不可避免的，因此第一点可能很难有所改变。那么第二点呢？我们是否可以在进行匹配时，不用保存之前已经遍历的节点，遍历到某个“冲突”则表明匹配失败，而经过一个完整遍历，则表明匹配成功。为了进一步看清需求，我们再说的清楚一点：

对一颗表达式树进行完整遍历，可以看作是构造一个由各节点（或节点的“特性”）构成的序列。

在遍历序列时，无需保存之前遍历的结果。遍历结束时，则表示匹配成功。

“序列”、“遍历”、“匹配”……在心中反复默念几遍，您是否想到了些什么？没错，上述需求似乎符合我们常用的数据结构：前缀树。