tries
1.0.0
このクラスは、トライベースのコンテナを構築するための基礎を提供します。
基本的なフォームでは、Ttrieクラスを使用して、16、32、および64ビットベースのデータ要素を保存できます。
この構造は、固定された深度トライの実装を提供します。これにより、ノードの検索、削除、追加の時間を均等にレンダリングします。
構造の順序はo（d）です。ここで、dはトライの深さであり、16、32、または64ビットの値を保存するために構築されているかどうかに依存します。 16ビットの場合d = 4 32ビットd = 8、64ビットd = 16
ノードサイズを小さく保つために、ノードごとに16のブランチのみが使用され、インジケータフラグと内部ポインターインデックスが16ビットワードと64ビット整数でエンコードされます。
ブランチへのポインターは動的に管理されるため、新しいブランチを追加する必要がある場合、ポインターアレイにポインターのみが割り当てられます。これにより、事前に割り当てられたポインターアレイの無駄が低レベルのブランチに最小限に抑えられます。ただし、減速が追加されます。
葉は、最後のブランチノードで指摘されている個々のノードとしてではなく、その場で割り当てられます。
最後に、葉のノードは、ttrieの派生クラスによって動的に制御され、ttrieをベースとして使用して辞書を簡単に実装できるようにします。
全体として、MAC内のLazarus（Freepascal）Allocatorによって割り当てられたメモリを保存するテストを行うと、保存されたオブジェクトのサイズに比例して約40％のストレージ効率がレンダリングされます。
また、クラスは、多くの削除が発行されたときにストレージを抑えるために使用するために使用されるパック方法も提供します。
TintegerhashtrieとTstringhashtrieは、Thashtrieジェネリッククラスの子孫として提供されています。 Thashtrieには2つの操作モードがあります。
ハッシュテーブルはもちろんパフォーマンスを向上させますが、Hashtrieは少数の要素を保存する際に、より効率的なメモリフットプリントを備えています。
Delphiのtdictionary <>およびC＃dictionary <>クラスに対してtstringhashtrieをテストしました。
Tstringhashtrieは、C＃とDelphiの実装の両方を破ります。ルートノードにハッシュテーブルを使用すると、差が大きくなります。
大きな負荷のメモリフットプリントは、30％〜40％の範囲で優れています。ハッシュテーブルルートノードではなく、純粋なハッシュトリーを明確に使用して少数の要素の場合、メモリが劇的に少ないメモリを使用します。
Delphi 2007でコンパイルされたテストは、構造に挿入する前にUTF16からANSIへのストリングを訪れる必要がなかったため、さらに優れた結果をもたらしました。
TstringHashtrieはUTF8フォームのUnicodeをサポートしています。
