キーが50ビット整数で値が32ビット（最大）整数である1億1100万のキーと値のペア（1つのキーは複数の値を持つことができます-最大2/3）を格納しています。今、私の要件は次のとおりです。
- （キー、値）ペアの高速挿入[重複を許可]
- キーに基づく値の高速取得。
この問題を解決するC/C ++用のライブラリはありますか（MultiMap、B +ツリー、Bツリー、R +ツリーなどを使用）？そのために5/6GBのメインメモリを提供できます。詳細については、以前の投稿をご覧ください。
質問する
366 次
3 に答える
0
Cのプレーンハッシュテーブルは、要素ごとに50 + 32（+14パディング）+32+32ビットを必要とします。（+多分32ビットアライメント）。つまり、要素あたり160（または192）ビット：=要素あたり20（または24）バイトです。ハッシュテーブルには、111 * 20（または111 * 24）Mバイトのメモリが必要です。つまり、2.2GBまたは2.7GBです。
于 2012-04-09T10:45:06.593 に答える
0
要件には、注文したコレクションの必要性は含まれていません。ハッシュマップを使用します。既製のものが見つからない場合は、作成するのは大きな課題ではありません。
于 2012-04-09T10:49:09.593 に答える
0
「5/6ギガバイト」は実際には5または6ギガバイトを意味するため...
50ビットキーと32ビット値を持つ111000000キー/値のペアは、密集した（ビット）配列として格納された場合、（111000000 *（50 + 32））/（8 * 1024 * 1024 * 1024）=1.05ギガバイトまたはメモリを必要とします。
その5倍のメモリがあります。
64ビットシステムでの10レベルのディープスキップリストベースのマップは、最悪のシナリオでは（111000000 *（64 + 32 + 10 * 16））/（8 * 1024 * 1024 * 1024）=3.308ギガバイトかかります。ヒープ管理のオーバーヘッドを処理するためにギガバイトを超えるRAMがあります。
したがって、利用可能なマルチマップを取得して使用することをお勧めします。私の意見では、余分なトリックを使用せずに状況に対処するのに十分なメモリがあります。
- 編集 -
実際、私はC /C++を知りません
さて、C ++を知らない場合、111000000のキーを含むマップをどのように処理することを期待しますか？あなたはいくつかの読書をしなければならないでしょう。
標準ライブラリにはstd::multimapが含まれており、Boostライブラリにはいくつかのクラスがあります。Qt 4には、スキップリストに基づくQMapが含まれています。それらのいずれかを使用してみてください。
于 2012-04-09T11:10:56.510 に答える