在这次的 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 级别）, 主要的消耗还是在树查找与内存访问。