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。