tries

尝试

该课程为构建基于TRIE的容器提供了基础。

在基本形式上，TTRIE类可用于存储基于16、32和64位的数据元素。

该结构提供了固定的深度Trie实现，该实现依次呈现相等的时间来查找，删除和添加节点。

结构的顺序为o（d），其中d是Trie的深度，如果构建为存储16、32或64位值，则取决于它。对于16位d = 4 for 32位d = 8和64位d = 16

为了保持节点尺寸较小，将只使用每个节点的16个分支，并且指示标志和内部指针索引以16位单词和64位整数编码。

向分支机构进行的指针是动态管理的，因此只有需要添加新的分支时，仅在指针阵列上分配指针，这将预先分配的指针阵列的浪费最小化为较低级分支。它会减慢添加。

叶子是在原地分配的，而不是由上一个分支节点指向的单个节点。

最后，可以通过ttrie的派生类动态控制叶子节点，从而可以轻松实现使用ttrie作为基础的字典。

总而言之，在Mac中分配了Lazarus（Freepascal）分配器分配的一些测试，以与存储的对象大小成比例的存储效率约为40％，这并不糟糕，鉴于可以进行添加，查找和删除操作的性能。

该课程还提供了一种包装方法，该方法用于在发出大量删除后检查存储。

Tintegerhashtrie和Tstringhashtrie是Thashtrie Generic类的后代。 Thashtrie有两种操作模式：

• 使用哈希表作为根节点，带有Trie结构，每个级别的每桶16个节点
• 来自根节点的完整哈希结构

Hash Table当然提供了更好的性能，但是Hashtrie在存储少量元素时具有更有效的内存足迹。

测试了针对Delphi的Tdictionary <>和C＃Dictionary <>类的Tstringhashtrie。

Tstringhashtrie击败了C＃和Delphi实现。使用root节点的哈希表时，差异更大。

大负载的总体内存足迹也更好，范围从30％-40％好。对于少量元素，使用纯Hashtrie而不是哈希表词根节点最终使用将使用较少的内存。

在Delphi 2007中编译的测试产生了更好的结果，因为在插入结构之前，字符串不必从UTF16转换为ANSI。

tstringhashtrie支持UTF8形式的Unicode。