談表達式樹的緩存（5）：引入散列值
2009-03-20 01:40 Jeffrey Zhao 閱讀(13689) 評論(16) 收藏 舉報到目前為止，我們已經(jīng)實現(xiàn)了三種緩存方式：首先我們設(shè)法構(gòu)建唯一字符串，但是由于它的代價較高，于是我們使用了前綴樹進行存儲；又由于前綴樹在實際操作中所花的時間和空間都有不令人滿意之處，我們又引入了二叉搜索樹。那么二叉搜索樹又有什么缺點呢？其實前文已經(jīng)談到過了，那就是從理論上來說，它的時間復(fù)雜度相對前兩個要高，在最壞情況下將會出現(xiàn)O(m * log(n))的時間復(fù)雜度——每次比較兩個前綴樹需要耗費O(m)，共比較O(log(n))次。
很顯然，與最理想的時間復(fù)雜度O(m)相比，其差距就在于n，也就是緩存空間中已有的元素數(shù)量。如果元素越多，則n越大，log(n)也會隨之增大，則耗費O(m)的“次數(shù)”也就越多。換句話說，如果我們要改進性能，就要想辦法減少比較次數(shù)。一個比較容易想到的做法便是對緩存空間中的n個元素進行“分組”，在每次查詢時首先使用很小的時間復(fù)雜度，確定被查詢的表達式樹處于哪個組中，然后只需要與這個組中為數(shù)不多的幾個元素進行比較便可。這樣耗費O(m)的操作次數(shù)就少了，性能隨之提高。
既然要進行分組，那么我們其實就是要從每個表達式樹中提取“特征值”，再根據(jù)這個“特征值”進行分組——不過這是有條件的，例如：
- 特征值計算要盡可能的快，否則光計算一次特征值就消耗大量時間，得不償失。
- 根據(jù)特征值要能夠快速確定分組，原因如第1點。
- 特征值要可以將元素盡可能地分散在不同組中，這樣每個組里的元素會變得更少，更節(jié)省比較次數(shù)。
想到這里，您應(yīng)該已經(jīng)得出結(jié)論了……這不就是散列值嗎？在.NET Framework中，一個對象的散列值為一個32位整型數(shù)值，然后便可以從一個以Int32類型為鍵的字典中快速地獲取一個“分組”，這就已經(jīng)滿足了上述第2點要求。因此，問題的關(guān)鍵在于如何“快速”地求出一個表達式樹的散列值，并且要使這個散列值能夠盡可能地分布均勻。一個表達式樹的散列值，顯然是由它內(nèi)部的元素組成，因此我們只需要遍歷它的每個元素，將這些元素散列值結(jié)合為一個單一的散列值即可——這是一個O(m)的操作，非常高效。
為此，老趙實現(xiàn)了一個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方法，可用于計算一個表達式數(shù)的散列值。與之前的幾種ExpressionVisitor實現(xiàn)類似，ExpressionHasher也準備一些輔助方法供其他方法調(diào)用。這些輔助方法接受不同類型的參數(shù)，完全避免了數(shù)據(jù)的裝箱/拆箱，盡可能保持算法的高效。從上面的代碼看出，我們不斷地向這些輔助方法內(nèi)傳入對象時，它們會被累加到HashCode屬性中——這就是老趙在這里使用的“組合方式”，將表達式樹中每個元素的散列值進行組合，最終成為整個表達式數(shù)的散列值。老趙無法證明這是一種優(yōu)秀的散列組合算法，但是從測試上來看，這么做的效果還是不錯的（事實上，老趙隨機生成了大量表達式還沒有出現(xiàn)碰撞）。更關(guān)鍵的一點是，這么做非常高效，如果將這些元素拼接起來，并得到最終字符串的散列值可能會有更好的結(jié)果，但是其性能就比整數(shù)的相加要差許多了。
現(xiàn)在，我們只需要在Visit每個節(jié)點的時候，把節(jié)點的屬性作為表達式樹的每個元素傳入對應(yīng)的輔助方法便可，以下為部分代碼：
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); } ...
按照我們剛才的設(shè)想，首先計算出一個表達式樹的散列值，然后從字典中獲取具體的一個分組，再從這個分組中進行查找。使用這個方法則得到了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)的時間復(fù)雜度，從字典中查找分組需要O(1)，如果散列值夠好的話，每個分組中的表達式樹數(shù)量（k）應(yīng)該非常少，這樣從中進行查詢的時間復(fù)雜度（O(log(k))）就非常接近于常數(shù)了。因此，HashedListCache的查找操作，其時間復(fù)雜度為O(m)，這也達到了最為理想的時間復(fù)雜度。
到目前為止，我們?yōu)榱私鉀Q表達式樹的緩存問題，已經(jīng)提出了4種不同的處理方式，并且編寫了多個操作表達式樹的輔助類：
- SimpleKeyBuilder：將表達式樹構(gòu)造成唯一的字符串。
- PrefixTreeVisitor：根據(jù)表達式樹構(gòu)造一顆前綴樹。
- ExpressionComparer：比較兩個表達式樹的“大小”關(guān)系。
- ExpressionHasher：計算一個表達式樹的散列值。
回想起第一種做法，我們使用最原始的方式，使用字典來存儲對象，不過我們需要拼接出一個龐大的字符串，因為它具有“唯一性”。但是其實從那時開始，我們就已經(jīng)走了一條彎路。在.NET Framework中，一個對象如果要作為字典的“鍵”，難道一定要是字符串嗎？很顯然，答案是否定的。事實上，任何類型的對象都可以作為字典的鍵，而字典認為兩個“鍵”對象相同依靠的是對象的GetHashCode方法和Equals方法。字典的整個查詢分兩步走：
- 首先根據(jù)GetHashCode獲取對象散列值，用于確定需要查找的對象在那個分組（或者說是“桶”，在數(shù)據(jù)結(jié)構(gòu)中稱為散列表的“buckets”）中。
- 每個分組的對象數(shù)量很少，然后在使用Equals方法依次進行比較，最終得到相同的那個值。
因為有了ExpressionComparer和ExpressionHasher，我們已經(jīng)可以非常輕松地實現(xiàn)那個作為“鍵”的對象了：
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; } }
最后再實現(xiàn)一個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的實現(xiàn)其實和HashedListCache比較接近，不過從理論上說，DictionaryCache的性能不如HashedListCache。因為同樣在根據(jù)散列值獲取到分組后，DictionaryCache中的分組元素數(shù)量可能會比HashedListCache要多（因為字典中多個散列值也可以在同一個分組中）；同時，字典在同組的k個元素中找到指定元素使用O(k)的遍歷算法，而二叉搜索樹只要O(log(k))的時間復(fù)雜度——此消彼長，DictionaryCache的性能自然就要略差一些了。
至此，老趙在這個話題中計劃談起的5種解決方案都已經(jīng)講述完畢了，您覺得哪種做法的效果最好呢？在今后的文章中，老趙將會對5種解決方案進行性能上的比較并進行分析，同時給出每種方案的優(yōu)點、缺點和改進余地——其實這些才是最重要的，朋友們千萬不要錯過，也歡迎大家和我一起討論。
最后再學(xué)著打一個廣告：如果朋友們喜歡老趙的文章，可以通過RSS訂閱進行持續(xù)關(guān)注（訂閱地址為http://www.rzrgm.cn/JeffreyZhao/rss）。
完整代碼下載：http://code.msdn.microsoft.com/ExpressionCache
相關(guān)文章：
浙公網(wǎng)安備 33010602011771號