RAMサイズより大きなデータをソートする

Question

これはGoogleのインタビューの質問です。 64GBのRAMを搭載し、すべての整数（8バイト）を含む2台のマシンで128GBのデータ全体をソートします。少量のRAMを追加することもできます。これを拡張して、1000台のマシンに格納されたデータをソートします。

私は外部の並べ替えを考え出しました。そこで、データ全体をチャンクに分割し、マージソートを使用します。それは最初にチャンクをソートして戻し、もう一度それらを賢明にしてマージします。より良い方法がありますか？複雑さは何でしょうか？

Answer 1

クイックソートを個別に使用して64GBのソートを行い、64GBアレイの両方の外部メモリ保持ポインタを使用すると、RAM1とRAM2の順番でデータ全体を保持し、ポインタがRAM1のポインタより小さければ、ポインタの値がRAM2にある場合は、ポインタがRAM1の終わりに達するまで、値をRAM2にスワップします。

は、すべてのN RAMをソートするのと同じコンセプトを採用しています。それらのペアをとり、上記の方法でソートしてください。 N/2ソートRAMが残っています。上記の再帰的に同じ概念を使用してください。

Answer 2

ChingPingは、サブセットごとにO（n log n）ソートを行い、その後に線形マージ（要素の入れ替え）を行います。クイックソートの問題（とn log nの大半は、n個のメモリを必要とするという問題です。代わりに定数メモリを使用するSmoothSortを使用し、O（n log n）で実行することをお勧めします。

最悪あなたが何か持っている場合のシナリオは次のとおりです。

両方のセットを逆に並べられ

setA = [maxInt .. 1] 
setB = [0..minInt] 

を、その後合併は逆の順序である

- ChingPingのソリューションの（IMOより明確に）説明がされています。 ：

Have a pointers 'pointerA', 'pointerB' initialized at the beginning of each array 
While setA's pointer is not at the end 
    if (setA[pointerA] < setB[pointerB]) 
    then { pointerA++; } 
    else { swap(setA[pointerA], setB[pointerB]); pointerB++; } 

セットは現在両方ともソートされるべきです。

Answer 3

すでに2台のマシンのケースに対する回答があります。

ソートされる128GBのデータが1台のハードドライブ（または任意の外部デバイス）に1つのファイルとして保存されているとします。何台のマシンやハードドライブを使用しても、オリジナルの128GBファイルを読み込み、ソートされた128GBファイルを書き込む時間は同じです。唯一の節約は、ソートされたデータのチャンクを作成する内部RAMベースのソートの間に発生します。残りのハードドライブに1つのソートされた128GBファイルにnウェイ・マージを行うためにn + 1個のハード・ドライブとマージするのにかかる時間は同じであり、残りの128GBソート・ファイルを書き込む時間ハードドライブ。

n台のマシンの場合、データは128GB/nチャンクに分割されます。マシンのそれぞれは、ランダムアクセスオーバヘッドを減らすために、一度に64MBの読み込みサブチャンクを交互に読み出すことができるため、 "最後の"マシンは、それまでのすべてのマシンがすべてのチャンクを読み込むのを待っていません。

n個のマシン（それぞれ64GBラム）とn> = 4のn + 1ハードドライブの場合、O（n）時間の複雑さを持つ基数ソートを各マシンで使用して、n個の作業で32GB以下のチャンクを作成できますハードドライブを同時に起動し、宛先ハードドライブにnウェイをマージします。

大きなnの利益を制限するリターンが小さくなる点があります。 n> 16を越えるところでは、内部のマージスループットがディスクのI/O帯域幅より大きくなる可能性があります。マージプロセスがI/OバウンドではなくCPUバウンドの場合、I/O時間よりも大きなマージオーバーヘッドと並行してチャンクを作成する時間は、CPUオーバーヘッドのトレードオフになります。