7

興味深い問題があります。Java で 2 つの Long のセットを交差させたいと考えています。各セットには 1B のメンバーが含まれています。これはセットあたり 4GB です。これは、実行する必要があるサーバーのメモリに収まりません。

この問題を解決するために、どのような興味深い方法があるのか​​ 疑問に思っています。

これまでのところ、メモリに収まるほど小さいディスクから各元のセットのサブセットを読み取り、各サブセットを交差させ、それらを一時的にディスクに書き込むことを考え出しました。最後に、これらのサブセットを通過して交差させることができました。これはマップリデュースの仕事になりそうな予感がします。

たぶん、あなたはいくつかのより良いアイデアを持っているでしょう:) 私はこの問題を思いついた最初の人ではないと思います.

4

9 に答える 9

8

  1. 両方のセットAとB別々に並べ替えます。

  2. セット A から最初の要素を取得し、セット B から最初の要素を削除します

  3. 等しい場合は、結果セットに追加します。

  4. 1 つのセットのアイテムの方が大きい場合は、次のアイテムを 2 番目のセットから取得します。

  5. セットの終わりに達しない限り、2 に進みます。

この方法の利点は、メモリ内に 2 つ以上の long を保持しないことです (ソートを除く)。ソートはディスク上で効率的に実行できます (マージソート)。

于 2012-10-20T18:31:21.270 に答える
2

両方のセットでディスクベースのマージソートを実行します。

それが完了したら、ソートされたファイルを順番に調べて、交差点を新しいファイルに記録するだけです。

于 2012-10-20T18:30:04.957 に答える
2

おそらくソートよりも効率的な方法は、ハッシュを使用し、データをいくつかのビンに分割し、各ビンで交差を行うことです。アイデアは、問題をメモリに収まるサブ問題に分割することです-そうすれば、RAM上で効率的に交差を行うことができます。

R、Sの交点を見つけたいとしましょう：

for each element in R:
   write element in bucket_R[hash(element) % NUM_BUCKETS]
for each element in S:
   write element in bucket_S[hash(element) % NUM_BUCKETS]

//assuming each bucket from bucket_S or bucket_R now fits memory - proceed.
//if it doesn't, you can repeat the previous step with a new hash function.
for each i from 0 to NUM_BUCKETS:
  find bucket_S INTERSECTION bucket_R

重要:
bucket_S、bucket_R または DISK 上で、RAM ではありません。

ディスク アクセス数:

このアプローチによるディスク読み取りの総数は次のとおりです。3 * (|R|+|S|)

  1. 最初の 2 つのループを繰り返しながら R と S の各要素を読み取る
  2. 各要素をハッシュ テーブルに書き込む
  3. すべてのバケットを読み取る

並べ替えベースのアルゴリズムは、1 回の読み取り + 1 回の書き込み (およびデータの追加のトラバーサル) を必要とする可能性が最も高いですが、それよりもはるかに多くの結果が得られます。3 * (|R|+|S|)

PS 私は現在、ファイル システム試験 (月曜日に行われる) の勉強をしています。講義ノートには、ディスクが 1 つあると仮定すると、ほとんどのデータベース システムでこれが推奨されるソリューションであると書かれています。

于 2012-10-20T21:55:07.770 に答える
2

これが私ができると思うことです。明らかにディスクに入れます。それらをソートする必要があります。

  1. 外部ソートを使用してソートする

  2. 比較、

    if a. length < 1 or b.length < 1
  exit
else if a[0] == b[0]
  addToIntersectionSet(a[0])
  remove a[0] from a
  remove b[0] from b
else if a[0] < b[0]
   remove a[0]
else 
  remove b[0]
于 2012-10-20T18:36:06.430 に答える
2

2 つの大きなビット マップ (ビットマップ 1 とビットマップ 2) をメモリまたはディスクでゼロに初期化します (使用可能な場合)。set1 の各値に対して、value 番目の bitmap1 位置を 1 に設定します。set2 の各値に対して、bitmap1 ビットの value 番目の位置を読み取り、1 の場合、value 番目の位置にある bitmap2 を 1 に設定します。 bitmap2、その位置の出力値。

編集: 以下の返信の Jessop は欠陥を指摘しています: それは Java 64 ビット (8 バイト) の long int であり、32 ビット アーキテクチャの C コンパイラの 4 バイト long int ではありません。このソリューションは、64 ビット long では実用的ではありません。

于 2012-10-20T18:50:10.113 に答える
1

これはマップリデュースの仕事のように感じますが、選択するサブセットには十分注意する必要があります。交差点を機能させるには、元のセットのサブセットを同じポイントでカットする必要があります。たとえば、セットがあるとします

A = {1 3 7 9}
B = {2 7 8 9}

そして、それらをそれぞれ2つのサブセットに分割します。

A1 = {1 3} A2 = {7 9}
B1 = {2 7} B2 = {8 9}

次に、交差します。

C1 = A1 inter B1 = {}
C2 = A2 inter B2 = {9}

次に、次のように仮定します。

C = A inter B = C1 union C2 = {9}

これは明らかに間違っています。マップリデュースを機能させるには、一定の値を使用してセットをカットする必要があります。たとえば、A1とB1には5未満の値が含まれ、A2とB2の値は5以上になります。

セットAとBの通常の部分をディスクからフェッチし、インテリジェントな方法でそれらを交差させることもできます。つまり、並べ替えられた要素を段階的に確認し、2つのサブセットのいずれかの終わりに到達したときに停止します。その時点で、余分なサブセット部分をフェッチします。

于 2012-10-20T18:28:47.750 に答える
1

頭に浮かぶ明らかなことの1つは、ディスク上のソートされたセットから始めることです。次に、両方のファイルから同時に読み取り、一致するものを見つけて書き出すことができます。1つのファイルから204を読み取ったとすると、最初の番号が204以上になるまで、他のファイルから読み取ります。その時点で、この特定の番号が交差点に属しているかどうかがわかります。

于 2012-10-20T18:28:58.167 に答える
1

最初のステップは、各セットを並べ替えることです。小さいブロックを並べ替え、並べ替えをマージして、並べ替えられたファイルを作成します。

ソートしたら、両方のセットをウォークスルーできます。

于 2012-10-20T18:31:11.913 に答える
1

512 個のファイルを簡単に開いたままにしておくことができるため、両方のセットをディスク上の 256 個のチャンク (最大 16M アイテム、サイズはそれぞれ 64 メガバイト) にプレブラウズできます。これは、set.A.00 から set.B.ff までの各 Long の最上位バイトに基づいて実行できます。

次に、対応するチャンクの各ペア ( にset.A.42対応する 0x42 で始まる Long を含むset.B.42) をロードし、それらを使用して 16M バイト配列を初期化します。すべて 0 に初期化しi、最初のチャンクから値を読み取るときに、インデックス i をインクリメントします。 -th)。次に、2 番目のチャンクを読み込みますが、今回は 2 ずつインクリメントします。

完了したら、アレイのスキャンを実行します。0 は値がどちらのチャンクにも存在しないことを意味し、1 は最初のセットにのみ存在することを意味し、2 は 2 番目のセットにのみ存在し、3 は両方に存在することを意味します。そして、結果を結果ファイルに書き込みます。

結果ファイルがソートされる場合でも、ソートする必要はありません (チャンクを順番にチェックし、順番に最終スキャンを実行するため)。

これはすべて O(n) で実行され (すべてのステップは線形時間で実行されます)、最大で 16M の RAM が必要です。

512 個の開いているファイルが多すぎる場合は、最初の 7 つの最上位ビットを使用して、256 個の開いているファイルと 32M の RAM を使用できます。または、128 個の開いているファイルと 64M の RAM など。

また、それぞれのサイズが 16384 の一連の 256 個の「バケット」を保持することもできます (ファイルシステムのキャッシュがあまり良くない場合は、おそらくより効率的です) Longs(したがって、これも 16M になります)。バケットがいっぱいに近づくと、ディスク上の対応するチャンク ファイルを開き、Longこれまでに見つかった 16384 をダンプして、ファイルを閉じます。Long次に、セット B についても同じことを行います。一度に 2 つ以上のファイルを開いたままにしておくと、0 (可能性は低い) から 1600 万の s を含む 512 個のファイルができあがります。

于 2012-10-20T18:43:31.827 に答える