優化的基於樹狀位壓縮數組的字元集合，在提供高性能的同時並不需要消耗過多記憶體，可以完全取代任何用到 HashSet ...
之前在《基於樹狀位壓縮數組的字元集合》中介紹了一種利用位壓縮數組來減少空間占用和提高集合操作效率的字元集合 CharSet。
實際測試下來，CharSet 的耗時只有 HashSet<char> 的 50%~80%，而集合操作的耗時更是只有 10%。舊文章里最後的測試結論有問題，應該是誤使用 Debug 包來做性能測試導致的，最新的測試分別測試了下列五個場景的性能，並調整了測試的迴圈次數使得 HashSet<char> 耗時接近，便於對比：
- 單字元操作：包含 70%
Add調用和 30%Remove調用。 - 小範圍操作：包含 70%
Add調用和 30%Remove調用，範圍長度 1~10） - 大範圍操作：包含 70%
Add調用和 30%Remove調用，範圍長度 1~100） - 查找操作：
Contains調用。 - 集合操作：
UnionWith、ExceptWith，SymmetricExceptWith和IntersectWith調用。
結果如圖 1 所示：
圖 1 HashSet 對比 CharSet
可以看到，CharSet 的性能優於 HashSet<char>，特別是集合操作，位壓縮數據可以批量進行集合操作，大大提高了性能。並且由於 CharSet 的記憶體消耗基本是固定的，GC 壓力也遠遠小於 HashSet<char>。
但是在實際使用過程中，涉及 Unicode 範圍的邏輯很少會對單個字元做操作，更多的是對字元範圍做操作，之前在《判斷字元寬度》中整理的寬字元範圍就是一個很好的例子，這裡用到了 45 個字元範圍，大部分範圍長度小於 10，但最大的一個字元範圍達到了 22224 個字元。具體的字元範圍統計情況可以參見下圖。
圖 2 字元範圍統計
對於這類大範圍字元操作，雖然 CharSet 的效率還是比較高的，但與其他操作仍然處在在同一個水平。
基於平衡二叉樹的字元集合
那麼應該如何在範圍操作這種常見場景下進行優化呢？一種想法是拋棄位壓縮數組，直接將基於範圍操作重新實現一套字元集合。這裡選用了 AVL 樹作為底層數據結構，與紅黑樹相比實現更為簡單，性能也差別不大。
將字元範圍的起始值作為 AVL 樹的鍵，結束值作為相應節點的值，實現了一個 RangeCharSet。
但可惜的是，實測下來這樣的實現性能並不高。如圖 3 所示，RangeCharSet 的性能基本都明顯差於 HashSet<char>，GC 壓力也很高；只有作為優化目的的大範圍操作性能明顯極高，耗時只有 HashSet<char> 的 23%。
圖 3 HashSet 對比 RangeCharSet
不過 RangeCharSet 的性能還是高於同樣基於平衡二叉樹的 SortedSet<char>，說明這裡的瓶頸在於平衡二叉樹，性能還是比不上哈希表的。
優化的基於樹狀位壓縮數組的字元集合
第一條路走不通，只好再回來優化 CharSet 了。字元範圍操作的性能不理想，原因在於需要對字元範圍做遍歷，越大的字元範圍，這裡的消耗就越大。
如何避免這裡的遍歷行為？可以同樣利用位操作來進行批量操作。例如，需要將 \x05 到 \x32 範圍內的所有位置置 1，可以直接通過 $(1 << 32) << 2 - (1 << 5)$ 計算出位掩碼，再通過或操作實現置 1。
如果操作涉及到了數組內的多個位置，也是同樣的操作，這樣字元的遍歷次數可以減少到原先的 1/64（將 ulong 作為存儲單位），即使是完整 char 範圍的操作，也只需要 1024 次操作。
同時，之前允許將 CharSet 第二層數組設置為 null 來表示數組範圍的所有位置都是 0，那麼可以考慮通過將第二層數組設置為 [] 來表示數組範圍的所有值都是 1，就可以快速處理一些長度大於 1024（第二層數組可以容納的字元數）的連續的 0 或 1。這樣最大迴圈次數可以進一步減少到不超過 100。
在應用以上兩類優化後，CharSet 的判斷邏輯更為複雜，單字元操作和查找操作性能都有下降；集合操作性能基本持平；範圍操作性能得到了極大提升。
圖 4 HashSet 對比 CharSet 2
新的 CharSet 減少了大範圍連續 1 場景的記憶體消耗，也利用 ArrayPool 實現記憶體復用，整體對記憶體更為友好。
以前面提到的寬字元範圍為例：
- 字元範圍包含 42274 個字元，按
char[]存儲需要 82.6KB。 CharSet只會包含 16 個底層數組，其他部分由於全為0或1而沒有額外的記憶體消耗，總記憶體消耗約為 2.5KB。RangeCharSet包含 45 個 AVL 節點，總記憶體消耗約為 1.4KB。- 按只包含字元範圍起止的
char[]，需要 180B。這樣的壓縮表示下，二分查找進行匹配的性能略高於RangeCharSet，約為CharSet的 2.5 倍，只適合包含少量字元範圍的簡單的場景。
總的來說，CharSet 在提供高性能的同時並不需要消耗過多記憶體，可以完全取代任何用到 HashSet<char> 的場景。只有在極限優化記憶體的只讀場景，才需要考慮是否使用只包含字元範圍起止的 char[] 來代替。
CharSet 的所有代碼可以在這裡找到。
作者：CYJB
出處：http://www.cnblogs.com/cyjb/
GitHub：https://github.com/CYJB/
本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。
