c++ - トライ実装

Question

C/C++ での trie の速度とキャッシュ効率の高い実装はありますか? トライが何であるかは知っていますが、車輪を再発明して自分で実装したくありません。

score 38 · Accepted Answer

ANSI Cの実装を探している場合は、FreeBSDからそれを「盗む」ことができます。探しているファイルはradix.cと呼ばれます。カーネルでルーティングデータを管理するために使用されます。

score 19 · Accepted Answer

質問はすぐに使える実装に関するものだったと思いますが、参考までに...

Judy に飛びつく前に、「 A Performance Comparison of Judy to Hash Tables 」を読んでおく必要があります。次に、タイトルをグーグルで検索すると、一生の議論と反論を読むことができます.

私が知っている明示的にキャッシュを意識したトライは、HAT-trieです。

HAT トライは、正しく実装すると非常に優れたものになります。ただし、プレフィックス検索の場合は、ハッシュバケットの並べ替え手順が必要であり、これはプレフィックス構造の考え方と多少衝突します。

やや単純なトライはバーストトライであり、これは基本的にある種の標準ツリー (BST など) とトライの間の補間を提供します。概念的に気に入っており、実装がはるかに簡単です。

score 7 · Accepted Answer

私はlibTrieで幸運を祈りました。特にキャッシュに最適化されていない可能性がありますが、パフォーマンスは常に私のアプリケーションにとってまともです。

score 5 · Accepted Answer

GCCには、「ポリシーベースのデータ構造」の一部として少数のデータ構造が付属しています。これには、いくつかのトライの実装が含まれます。

score 4 · Accepted Answer

参考文献、

Double-Array Trieの実装に関する記事（実装を含むC）
TRASH-動的LCトライとハッシュデータ構造-（IPルーティングテーブルでアドレスルックアップを実装するためにLinuxカーネルで使用される動的LCトライを説明する2006年のPDFリファレンス

score 4 · Accepted Answer

Judy arrays : ビット、整数、および文字列用の、非常に高速でメモリ効率のよい順序付けされたスパース動的配列。Judy 配列は、任意のバイナリ検索ツリー (avl および red-black-trees を含む) よりも高速でメモリ効率が高いです。

score 3 · Accepted Answer

Cedar、HAT-Trie、およびJudyArrayは非常に優れています。ここでベンチマークを見つけることができます。

ベンチマーク結果

score 2 · Accepted Answer

http://tommyds.sourceforge.net/で TommyDS を試すこともできます。

nedtries および judy との速度比較については、サイトのベンチマークページを参照してください。

score 1 · Accepted Answer

キャッシュの最適化は、おそらくやらなければならないことです。データを、通常は 64 バイト程度の単一のキャッシュラインに収める必要があるためです (ポインターなどのデータを結合し始めると、おそらくうまくいくでしょう)。 . しかし、それはトリッキーです:-)

score 0 · Accepted Answer

私のデータセットで言及されているいくつかの TRIE 実装と比較して、marisa-trie で非常に良い結果 (パフォーマンスとサイズのバランスが非常に良い) が得られました。

score 0 · Accepted Answer

Burst Trie の方がスペース効率が良いようです。CPUキャッシュは非常に小さいため、インデックスからどれだけのキャッシュ効率を得ることができるかわかりません。ただし、この種のトライは十分にコンパクトであり、大きなデータセットを RAM に保持できます (通常のトライでは保持できません)。

私はバーストトライの Scala 実装を作成しました。これには、GWT の先行入力実装で見つけたいくつかの省スペース技術も組み込まれています。

12 に答える 12