关于Trie字典树性能问题
来源：10-3 Trie字典树的查询
Klaus_Mikaelson
2018-06-16
老师，您好：
关于Trie字典树，您在视频中讲到，Trie查询的速度和元素的个数没有关系，和单词的长度有关系。
下面的性能对比包括读取文件的时间，只包括插入和查询：
System.out.println("\tTotal words: " + words1.size());
long start = System.nanoTime();
for (String word : words1) {
set.add(word);
}
System.out.println("\tTotal different words: " + set.size());
for (String word : words1) {
set.contains(word);
}
long end = System.nanoTime();
return (end - start) / 1000000000.0;您也进行了LinkedSet、BSTSet和TrieSet进行了性能对比。我使用双城记作为数据源，性能对比如下所示：
TrieSet Time: 0.165550323 BSTSet Time: 0.146506406
后来我把数据源改成了词汇量更大的战争与和平，发现Trie比二分搜索略更慢：
TrieSet Time: 0.195874424 BSTSet Time: 0.145736233
后来我估计是因为插入的操作太耗时了，所以就单独统计查询操作的时间：
傲慢与偏见：
TrieSet Time: 0.045231067 BSTSet Time: 0.04074773
词汇量更大的双城记：
TrieSet Time: 0.059717239 BSTSet Time: 0.059854082
词汇量更大的战争与和平
TrieSet Time: 0.092482286 BSTSet Time: 0.210517965
为啥Trie的插入的时间比BST还要长呢？
1回答
-
赞实验精神：）
我们这里实现的Trie，效率比较低的核心原因，是Trie中使用了TreeMap。TreeMap的底层实现是红黑树，虽然从复杂度分析的角度，红黑树是很高效的（各项操作均为O(logn)），但是，一定要注意，复杂度分析关注的是n趋于无穷的情况。对于小样本数据，一个复杂的复杂度更优的算法，很有可能比不上一个简单的复杂度更低的算法。因为常数项的不同。如果你曾经看过我的《算法与数据结构》，就一定会有印象，在我们编写的归并排序和快速排序算法中，对于n比较小的情况，我们转而使用复杂度更高的插入排序去优化，就是这个原因。虽然插入排序的复杂度比归并排序，快速排序都要高，但是只有在n很大的情况才能显现出来，在n很小的情况下，插入排序更快：）
我们的Trie中使用的TrieMap（红黑树）同理。红黑树中由于有复杂的旋转操作（在这个课程的第十三章会介绍），虽然整体平均复杂度更低，但是对于小样本数据，是没有太大的性能优势的。所以，在这里，其实，使用HashMap代替更好。如果你能保证你存储的单词只包含小写字母，直接使用数组将是更快的：）为了验证这一点，我编写了一套测试程序，参考这里：https://github.com/liuyubobobo/Play-with-Data-Structures/tree/master/10-Trie/Optional-01-Trie-Using-HashMap-and-Array/src
其中，
Trie仍然是我们在这个课程中，内部结点使用TreeMap做映射的Trie；
Trie2的内部结点中，使用HashMap做映射；
Trie3的内部结点中，使用一个包含26个元素的数组做映射，这就限制了Trie3中存储的单词，只能包含小写字母。
其中，在Main的测试用，我同时加载了《傲慢与偏见》和《双城记》两本书的单词，以稍微增大数据量。
在我的计算机上，一次典型的运行结果是这样的：）
Total different words: 12177 BSTSet: 0.464858395 s Total different words: 12177 TreeMap Trie: 0.394749343 s Total different words: 12177 HashMap Trie: 0.293205009 s Total different words: 12177 Array(Map) Trie: 0.146712532 s
其中，基于TreeMap的Trie将是最慢的：）
基于数组的Trie最快，因为相比HashMap，数组也不需要计算哈希函数：）（关于HashMap的内部原理，可以参见这个课程的第十四章）
有兴趣可以下载一下我的测试代码，看看在你的环境下是否有和我的环境下类似的结果：）
P.S.1：
注意：在这里，为了能让我们的第三个Trie可以运行，FileOperation的分词部分有所修改，只判断isLetter是不够的，因为双城记中包括法文字符，所以我自己写了一个isEnglishLetter的方法，相信聪明的你一看就懂：）
P.S.2：
对于你给出的最后两个词汇量更大的测试，Trie还是有优势的：）
P.S.3
最后，对于Trie来说，其实还有一个重要的时间开销。由于Trie消耗的空间比较大（每个节点会有若干个指针），所以给这些承载指针的空间（TreeMap，HashMap或者数组）开辟内存也是一个额外的时间消耗：）
722021-08-23
相似问题