.netの効率的なトライ実装

Question

.netのトライ実装を探しています。

私はインメモリオブジェクトプールのインデックス構造として使用する予定です。スレッドセーフである必要はなく（スレッドを1つしか更新しないので）、少なくとも2千万のアイテムを優雅にかつ一定のパフォーマンスで対処できるはずです。

ネット上で見つかったものは、サンプルコードまたはおもちゃプロジェクトのようです。だから、私は本当に生産品質の実装を探しています。利用可能であれば、商用ライブラリもOKです。

PS：あまりにも多くのメモリを使用していて、配列に基づいてメモリの断片化を引き起こす傾向があると思われるハッシュテーブルの実装のように試行を選択しました。 O（1）ルックアップ特性および多数の項目に対する良性のメモリ使用特性を有するそのようなコンテナもOKであり得る。

は、.NET独自のメモリ管理は、私がお勧めしたい方法ではありません第二推測しようとする私の個人的意見では、

Answer 1

、ありがとうございました。ネイティブのシナリオで可能なメモリ割り当てのレベルを制御することはできませんが、同じようにする必要はありません。私は最初にC++（私は自分のヒープで定期的に作業し、メモリローカリゼーションルーチンなどを書く）から移動したときにこれを行うという欲求に執着していましたが、すぐには必要なかったことが素早く明らかになりました。また I.

たとえば、トライの下部に配列MyPooledObjectを配置することもできますが、リファレンスタイプの場合は参照の配列が得られます。それぞれはどこか他の場所にあります - あなたは自分自身を制御することはできません。

代わりに値型を使用していますが、これらはプールされたシナリオでの使用には適していません。カスタム値の型は不変である必要があります（私はそれを正当化せずに安全に言うことができます - 構造体をターゲットとするサイト：stackoverflow.comより多くを参照してください）、したがって再利用可能なオブジェクトとして扱うことはできません。

各オブジェクトがハッシュ対応キーで認識できるインデックス付きオブジェクトのコレクションが必要な場合は、辞書を使用します。あなたは、メモリに収まるようにあまりにも多くのオブジェクトがある場合は

次のいずれか

1）より多くのメモリ

2ゲット）それ

または両方のデータベースとキャッシュローカルセグメントを使用する：あなたは可能性がありAppFabric and its cache featuresを見ると、何百万ものオブジェクトのメモリ内キャッシュを実行する専用のマシンファームを構築できます。ハードウェアのコストは、おそらく.NET用独自のメモリ管理ソリューションを開発するコストよりも少なくなります:)

Answer 2

は、このライブラリを見てみましょう：TrieNet

using Gma.DataStructures.StringSearch; 

... 

var trie = new SuffixTrie<int>(3); 

trie.Add("hello", 1); 
trie.Add("world", 2); 
trie.Add("hell", 3); 

var result = trie.Retrieve("hel");