在這次的 coding4fun 活動中已經有很多同學分享了精彩的優化思路。我的思路其實大同小異，下面就挑一些于衆不同的地方分享吧：
第一個不同點：
在結構上選擇了 簡化版的 trie 作為查找結構。簡化版 trie 的結構就是一顆 n 叉樹, 每個節點對應一個狀态。選擇簡化版 trie 的原因是它的樹狀結構很容易用 cas實作無鎖并行，而相比 hashtable 沒有 hash 沖突和 rehash的問題，相比複雜 trie 結構如 double-array trie 又比較容易實作：
簡化版 trie 的一個重要參數就是樹的寬度（w），對應每一層有多少個子節點，它等于存放子節點的數組大小。如果 w 越大，每個節點占據的記憶體就越大，節點使用率就越低。trie 的每一層可以有不同的 w, 在極限外推下，如果 trie 樹的第一層 w非常大，保證絕大部分節點在第一層能放下，這個記憶體結構就與 hashtable 沒有太大差別了：
對 trie 的調優集中在節點使用率上。如果節點使用率越高, 相同單詞量的情況下資料結構占據的記憶體就越小（假設記憶體能完全放下的話）, cpu 随機通路這些節點的 cache hit 就會越高。—— 短時間内沒法對樹的查找複雜度 o(log n) 進行改造, 是以隻能設法降低資料結構的記憶體占用（工作集）。
trie 樹的查找是先把輸入拆分成一系列 “狀态” 序列, 然後根據這組狀态序列在用 “樹” 表示的狀态遷移有向圖中定位最終的節點。在簡化的 trie 結構中, “狀态”的總數就決定了 trie 樹的寬度 w 。是以怎樣把輸入有效的拆分成 “狀态” 或者說定位子節點 index 是同樣重要的, 例如輸入字元串 ‘abcdefg’：
如果按原始 char 内碼拆分, 生成的子節點 index 序列是： { 65, 66, 67, 68, 69, 70, 71 }，需要一棵 w = 256 的 trie 樹存放；
如果隻考慮字母, 忽略大小寫壓縮一下, 生成的子節點 index 序列是： { 0, 1, 2, 3, 4, 5, 6 }，隻需要一棵 w = 26 的 trie 樹就能放下；
如果在上一條的基礎下, 按 bit 逐位拆分每個字母，則産生的 index 序列是： { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0 }, 隻需要 w = 2 的 trie（它其實是棵二叉樹） , 但是查找路徑會增加很多。
btw：其實這就是bitwise trie，不過第一 java 下不能利用 cpu 指令優化位運算，第二 bitwise trie 更适合定長輸入，是以測試性能并不太友好。
更加靈活（複雜）的拆分辦法，在上述按 bit 拆分的基礎上, 再合并相鄰 bit 增加寬度, 降低查找路徑。例如合并 3 位： { 0, 4, 0, 4, 0, 3, 0, 2, 2, 1, 6, 0 }, 需要一個 w = 8 的 trie 存儲。這個方法可以讓任意 w 值的 trie 樹接受任意的狀态序列輸入。
為了友善對不同 w 和結構的 trie 性能進行測試, 我定義了一組 tries / sequencer 接口, 由 tries 接口維護 “狀态” 資料結構，sequencer 産生 “狀态” 的 index 序列。 在全部的測試中我嘗試了若幹種不同的 tries 和 sequencer 實作，最後發現按照方式 2 來最大限度的壓縮 index 序列的 alphabetsequencer 與最簡的 simpletries/concurrenttries（使用 cas 并行插入節點） 實際性能最好。這一塊就不多介紹了, 大家有興趣可以閱讀 gitlab 的代碼。
第二個不同點：
與大部分同學利用記憶體映射檔案一次性把檔案讀到記憶體不同，我在一開始就直接把檔案平均分成若幹個分區，讓每個工作線程單獨掃描一個分區進行分詞，這樣可以實作完全并行：
因為平均分區這個辦法太簡單, 可能會出現尾部 “半個單詞” 的問題, 漏掉分區結尾的單詞。解決尾部半個單詞的辦法很簡單，寫成僞代碼是這樣的：
if（不是從檔案開頭讀取） {
忽略分區的第一個單詞；
}
讀取和計算分區中的單詞；
if（沒有讀到檔案末尾） {
繼續向後多讀一個單詞，直到單詞結束；
具體的并發執行過程如下圖。其中并發加載是最慢的，消耗一般在 3s以上，而并發排序一般是 6x-8x 毫秒：
實際調優中發現, 盡管多個線程并發通路相同的資料結構, 但是因為單詞總量不大（3w 多）, trie 樹的絕大部分節點都是在運作的最初階段插入的, cas 沖突消耗的時間很少（100-200ms 級别）, 主要的消耗還是在樹查找與記憶體通路。