12

この質問は簡単に思えますが、その背後にある実際の作業を理解できません。512 MB のチャンクに分割し、Map reduce を使用した Merge Sort を使用するように並べ替えます。

だからここに私が持っている実際の質問があります:

ファイルを 512 MB のチャンクに分割し、別のホスト マシンに送信して並べ替えるとします。これらのマシンがマージ ソートを使用したとします。ここで、2000 台のマシンでそれぞれ 2000、512 メガのチャンクをソートしたとします。それらをマージして戻すと、どのように機能しますか? またサイズが大きくなりませんか？たとえば、2 つの 512 MB をマージすると、RAM のサイズである 1024 MB になりますが、これはどのように機能しますか? サイズが 1 GB を超えるため、どのマシンも 512 MB を超えるチャンクを別のチャンクとマージすることはできません。

マージの最後に、2 つの 0.5 TB チャンクを別の 0.5 TB チャンクとマージするにはどうすればよいでしょうか。仮想メモリの概念はここで機能しますか?

私は自分の基本を明確にするためにここにいます。この非常に重要な質問を (正しく) 正しく尋ねていることを願っています。また、誰がこのマージを行うべきですか (ソート後)? 私のマシンですか、それとも 2000 台のマシンのいくつかですか?

4

5 に答える 5

8

この問題は、より単純な問題に還元できます。この問題は、アプローチを強制するように設計されています。ここにあります：

  • チャンク =~ 1GB をピックアップし、ソートして別のソート済みファイルとして保存します。
  • ファイル システム上に 1GB のソート済みファイルが 1000 個存在することになります。

  • さて、それは単にkソートされた配列を新しい配列にマージする問題です。

    k ソートされた配列をマージするには、一度に k 個の要素を持つ最小ヒープ (優先キュー) を維持する必要があります。

つまり、この場合はk = 1000 (ファイル) です。( 1GB RAM は 1000 個の数字を保存できます)

したがって、優先キューから要素をポップし続け、ディスクに保存してください。

サイズ 1TB でソートされた新しいファイルが作成されます。

参照: http://www.geeksforgeeks.org/merge-k-sorted-arrays/

アップデート

PS:より優れたデータ構造を持つ 1 GB の RAM を備えた単一のマシンで実行できます。

マージは、プライオリティ キューを使用してO(N)未満のスペース、つまりO(K) スペース、つまり問題の中心で実行できます。

于 2014-02-13T12:32:40.560 に答える
6

マージ方法の短いバージョンは次のようになります。

1) マージ元のマシンごとに 1 つのスロットを持つテーブルを作成します。

2) 各マシンに、まだ与えられていない最低のエントリを尋ねます。

3) テーブルから最も低い値のエントリを削除して出力し、そのマシンにまだ与えられていない最も低いエントリでスローを補充するように依頼し、マシンにエントリがない場合はスロットを空のままにします。

4) テーブルが空になるまでステップ 3 を繰り返します。

これにより、一度に N エントリのみを保存する N 台のマシンからマージできます。もちろん、各マシンから M 個のエントリを保持するように簡単に最適化できます。その場合、N*M エントリを保存する必要があり、スロットが空になったら、そのマシンに M エントリを要求して補充します。

于 2011-12-22T03:07:29.687 に答える
4

これが機能するはずの理論的な方法です。2000 個の 512 MB ファイルがあり、1 TB ファイルを 1 つ作成する準備ができているとします。

すべてのファイルを単純にループすると、最初の値が最も低いファイルを見つけて、それを宛先ファイルに移動し、繰り返すと、すべてが順番に終了します。一度に複数の行を開く必要がないため、RAM の使用量は少ないはずです。

明らかに、これを最適化できるはずです-すべてのファイルの最初の行をRAMに保持すると、多少速くなるはずです。

于 2011-12-22T03:08:06.470 に答える
4

ここで、2000 台のマシンでそれぞれ 2000、512 メガのチャンクをソートしたとします。それらをマージして戻すと、どのように機能しますか? またサイズが大きくなりませんか？たとえば、2 つの 512 MB をマージすると、RAM のサイズである 1024 MB になりますが、これはどのように機能しますか? サイズが 1 GB を超えるため、どのマシンも 512 MB を超えるチャンクを別のチャンクとマージすることはできません。

これは、実際のマージソートの実装がどのように機能するかではありません。マージソート (および関連するソート アルゴリズム) の優れた点は、機能させるためにデータセット全体をメモリに保持する必要がないことです。マージするときは、一度にファイルのごく一部をメモリに読み込むだけでよく、後ですぐに書き出されます。

つまり、マージソートにランダム アクセスは必要ありません。この優れた特性がなければ、当時の技術ではテープ ドライブのデータを並べ替えることができなかったでしょう。もちろん、テープ ドライブはランダム アクセス メディアではなく、当時の RAM はキロバイト単位で測定されていました。

于 2011-12-22T03:09:51.257 に答える
1

マージ ソートの優れた点は、ランダム アクセスが必要ないことです。順次アクセスで十分です。これが、データセットがメモリに収まらない場合に最適なソリューションとなる理由です。

1 つのマージ パスには 2 つ (またはそれ以上) の入力が必要で、1 つの出力が生成されます。ファイルが 1 つだけになるまで、入力を出力に結合し続けます。

于 2011-12-22T03:09:24.907 に答える