c# - アプリケーションのメモリ内検索インデックスが大量のメモリを消費します - 何か提案はありますか?

Question

デスクトップアプリケーションでは、転置インデックスを使用して単純な検索エンジンを実装しました。

残念ながら、一部のユーザーのデータセットは非常に大きくなる可能性があります。たとえば、転置インデックスが作成される前に最大 1 GB のメモリを消費します。転置インデックス自体は、インデックスを作成するデータとほぼ同じ量のメモリを消費します (さらに 1GB の RAM)。

アプリケーションごとに 2GB のメモリという 32 ビット Windows の制限に達したり、スペックの低いコンピュータを使用しているユーザーがメモリの需要に対処するのに苦労したりするため、明らかにこれはメモリ不足エラーの問題を引き起こします。

逆インデックスは次のように保存されます。

Dictionary<string, List<ApplicationObject>>

これは、各オブジェクトが処理されるデータロード中に作成され、applicationObject のキー文字列と説明語が転置インデックスに格納されます。

だから、私の質問は次のとおりです。検索インデックスをより効率的に空間的に保存することは可能ですか? おそらく、別の構造または戦略を使用する必要がありますか? あるいは、一種の CompressedDictionary を作成することは可能ですか? たくさんの文字列を保存しているので、圧縮性が高いと思います。

score 3 · Accepted Answer

いくつかの解決策があります。

配列にApplicationObjectsがある場合は、インデックスのみを格納します-小さい場合があります。
UTF-8を使用して、C ++/CLIを少し使用して辞書を格納できます。
わざわざすべての異なる文字列を保存するのではなく、Trieを使用してください

score 3 · Accepted Answer

非常に小さなリストがたくさんあることに気付くかもしれません。

頻度がどのようなものかを大まかに調べることをお勧めします。辞書エントリの中に単一の要素リストがあるもの、2つの要素リストがあるものなどがあります。複数の個別の辞書を保存できる可能性があります。1つは「要素が1つしかない」用です。（直接マッピング）次に、「2つの要素があります」（2つの参照を含むPair構造にマップします）など、ばかげたものになるまで（おそらく約3エントリで）、その時点で通常のリストに戻ります。単純なインターフェイスの背後にあるロット全体をカプセル化します（エントリの追加/エントリの取得）。そうすれば、無駄なスペース（ほとんどの場合、空のバッファー、カウントなど）が大幅に少なくなります。

これがあまり意味をなさない場合は、私に知らせてください。私はいくつかのコードを考え出すようにします。

score 3 · Accepted Answer

1GBになる場合は...ディスクに入れます。Berkeley DB のようなものを使用します。それはまだ非常に高速です。

.net インターフェイスを提供するプロジェクトを次に示します。

http://sourceforge.net/projects/libdb-dotnet

score 1 · Accepted Answer

私はbobwienholtに同意しますが、データセットのインデックスを作成している場合、これらはどこかのデータベースからのものであると思います。DTSearchやLucene.netなどの検索エンジンでそれを検索するのは理にかなっていますか？

score 1 · Accepted Answer

Lucene が行ったアプローチを取ることができます。最初に、ランダムアクセスインメモリストリーム (System.IO.MemoryStream) を作成します。このストリームは、ディスク上のものをミラーリングしますが、その一部のみをミラーリングします (間違った部分がある場合は、ディスクから別のものをロードします)。 . これには頭痛の種が 1 つあります。辞書にはファイルマップ可能な形式が必要です。ウィキペディアには、ページング手法の説明があります。

ファイルマップ可能なシナリオについて。Reflector を開いて Dictionary クラスを反映すると、バケットで構成されていることがわかります。おそらく、これらの各バケットをページおよび物理ファイルとして使用できます (この方法では、挿入が高速になります)。次に、「item x deleted」値をファイルに挿入するだけで値を大まかに削除し、ファイルを頻繁にクリーンアップすることもできます。

ちなみに、バケットは同一のハッシュを持つ値を保持します。保存する値が GetHashCode() メソッドをオーバーライドすることが非常に重要です (コンパイラは Equals() について警告するので、それもオーバーライドします)。これを行うと、ルックアップの速度が大幅に向上します。

score 1 · Accepted Answer

Memory Mapped File Win32 API を使用して、メモリ構造を透過的にバックアップするのはどうですか?

http://www.eggheadcafe.com/articles/20050116.aspには、有効にするために必要な PInvokes があります。

score 0 · Accepted Answer

0

インデックスは追加されるだけですか、それともキーを削除しますか?

于 2008-10-21T16:08:33.843 に答える

c# - アプリケーションのメモリ内検索インデックスが大量のメモリを消費します - 何か提案はありますか?

7 に答える 7

Related

Reference