0

私は非常に大きなテーブルを持っています:

id1 id2 count
1   234   4
1    5    123
1   432   5
23  234   7

id1 と id2 にはさまざまな値があります。count には限られた数値 (1 ～ 30000 など) があり、それらのほとんどが 1 に等しいことがわかっています。

このテーブルを .net ディクショナリに保存すると、約 10 GB のメモリが必要になります。このデータを格納するためのメモリ効率の良いデータ構造を見つけたいです。

完全なハッシュは理想的な解決策かもしれませんが、問題は衝突です。テーブルに存在しない ID の値を取得できます。多分DAWGが助けることができますか？または、他の何か？

データ構造の主な目的は、id1 と id2 によるカウントを取ることです。

4

2 に答える 2

1

ほとんどすべてのカウントが 1 の場合、カウントが 1 であるすべての ID ペアを含む HashSet と、カウントが 1 より大きい ID ペアの辞書の 2 つのデータ構造を使用できます。これにより、インクリメントとチェックが行われます。カウントは少し遅くなりますが、スペースを節約できるはずです。(.Net のデータ構造が内部でどのように配置されているのかわからないので、推測するのをためらっていますが、C++ であれば、値にもよりますが、スペースの消費を 25 ～ 30% 削減できると思います。 「ほぼすべて」の。）

それでも十分なスペースを節約できない場合は、いくつかの可能性の概要を次に示します。

一般に、コンテナー データ構造のコストは、要素のデータのサイズ、要素ごとのオーバーヘッド、およびデータ構造ごとのオーバーヘッドで構成されます。ハッシュ テーブルには、要素ごとのオーバーヘッドが中程度あります (バケット内の次の要素への 1 つのリンクと、割り当て/配置のオーバーヘッド)。また、バイナリ ツリーには、要素ごとに多くのオーバーヘッドがあります (2 つ以上の場合、通常は 3 つのリンクに加えて、割り当て/配置のオーバーヘッド)。技術的には、ベクターには要素ごとのオーバーヘッドはありませんが、通常は挿入時間を短縮するために過剰に割り当てられるため、要素ごとに 50 ～ 100% のオーバーヘッドがあると考える必要があります。

結果の 1 つは、要素の数を減らす方法を見つければ、多くの場合、スペースを節約できるということです。たとえば、上で提案したように、ID ペアの HashSet を使用できます。しかし、個々の id1 値がペアよりもはるかに少ない場合 (つまり、id が繰り返される場合) は、id1 を id2 のベクトルにマッピングする辞書に置き換えることができます。これにより、オーバーヘッドが削減される可能性があります。これには大きな欠点があります。ルックアップと挿入のコストがはるかに高くなります。さらに、要素ごとのハッシュテーブルのオーバーヘッドが予想されるベクトルの割り当て超過のオーバーヘッドを超える場合にのみ役立ちます。

于 2013-04-27T03:25:03.737 に答える