1GB RAMのマシンで1TBファイルをソート

Question

この質問は簡単ですが、その背後にある実際の作業を理解することはできません。 私は人々が言うと知っている、512 Megsの塊に分解し、Map reduceを使用してマージソートを使うように並べ替えます。だからここ

は私が持っている実際の質問です：

私は512メグスチャンクにファイルを分割し、それらを並べ替えるために別のホスト・マシンに送信するとします。 これらのマシンでマージソートが使用されているとします。 今は、2000台のマシンにそれぞれ2000、512メガのチャンクを並べています。今私はそれらを元に戻すときに、どのように機能するのですか？サイズは再び増加し続けるでしょうか？たとえば、2つの512メガをマージすると1024メガバイトが作成されますが、これは私のRAMのサイズですので、どのように動作しますか？どのマシンでも512メガ以上のチャンクを別のチャンクとマージすることはできません。その理由はサイズが1GBを超えるからです。

2つの0.5 TBチャンクをもう1つの0.5 TBチャンクとマージすることができます。仮想メモリの概念はここで始まりますか？

私はここで基礎を明確にしています。私は、この非常に重要な質問を正しく（正しく）求めていることを願っています。また、誰がこのマージを（ソート後に）行うべきですか？私のマシンか、それらの2000台のマシンのいくつか？

Answer 1

ここでは動作する理論的方法があります。 2000TBのファイルを持っていて、1TBのファイルを作成できるとします。

すべてのファイルをループするだけで、FIRSTの値が最も小さいものを見つけて、それを目的のファイルに移動し、それを繰り返すとすべてが順番に終わります。一度に複数の回線を開く必要はないので、RAMの使用量はごくわずかです。

明らかにこれを最適化できるはずです - すべてのファイルの最初の行をそのままRAMに入れておくと、やや速くなるはずです。

Answer 2

マージする方法のショートバージョンが、このようなものです：

1）あなたがからマージされている各マシンに1つのスロットを持つテーブルを作成します。

2）各マシンに、まだ与えていないエントリの中で最低のものを尋ねます。

3）テーブルから一番低い値のエントリを削除して出力し、マシンにエントリがない場合はスロットを空のままにし、 。

4）テーブルが空になるまで、手順3を繰り返します。

これにより、一度にN個のエントリだけを格納するN台のマシンからマージすることができます。もちろん、各マシンからM個のエントリを保持するために、それを簡単に最適化することができます。その場合は、N * Mエントリを格納する必要があります。スロットが空の場合は、そのマシンにMエントリの再充填を依頼してください。

Answer 3

マージソートの大きな点は、ランダムアクセスが必要ないことです。順次アクセスが行います。これは、データセットがメモリに収まらないときの完璧なソリューションになります。

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

Answer 4

ここでは2000個のマシンにそれぞれ2000個の512 MBのチャンクがあるとします。今すぐ 私はそれらを元に戻すと、どのように機能しますか？サイズは再び増加し続けるでしょうか たとえば、2つの512メガをマージすると、1024Megsになります。 これは私のRAMのサイズなので、どのように動作しますか？どんなマシンでも は512メガチャンクを超えるチャンクを別のチャンクとマージすることができません。 サイズ> 1 GBです。

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

つまり、mergesortのランダムアクセスは必要ありません。この素敵な不動産でなければ、その時点で利用可能な技術はsort the data on tape drivesには不可能です。もちろん、テープドライブはランダムアクセスメディアではなく、RAMはキロバイト単位で測定されます。

Answer 5

この問題は、の簡単な問題になる可能性があります。この問題は、あなたにアプローチを強制するように設計されています。ここでは、次のとおりです。

• チャンクを拾う=〜1ギガバイト、ソート&別のソートされたファイルとして保存します。
• ファイルシステムには1GBソートファイルが1000個あります。

• 今や、kソートされた配列を新しい配列にマージするという単純な問題です。

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

すなわち我々の場合でのk = 1000（ファイル）。 （1GB RAMに1000個の数値を格納することができます）

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

サイズが1TBの新しいファイルが作成されます。

参照してください：http://www.geeksforgeeks.org/merge-k-sorted-arrays/

を更新

PS：は

マージが未満で行うことができ、より良いデータ構造で1ギガバイトのRAMを搭載した単一のマシン上で行うことができますO（N）スペース優先キュー付き、すなわちO（K）スペースつまり問題の中心です。