9

これは、クラッキング コーディング インタビューからの別の質問です。それを読んでも、まだ疑問が残ります。

9.4 If you have a 2 GB file with one string per line, which sorting algorithm 
    would you use to sort the file and why?

解決

インタビュアーが 2GB のサイズ制限を与えるとき、それはあなたに何かを伝えるはずです。どうしようか？データの一部のみをメモリに取り込みます.. アルゴリズム:

利用可能なメモリの量は? X MB のメモリが利用可能であると仮定しましょう。

  1. ファイルを K 個のチャンクに分割します。ここで、X * K = 2 GB です。各チャンクをメモリに取り込み、通常どおり O(n log n) アルゴリズムを使用して行を並べ替えます。行をファイルに保存します。

  2. 次に、次のチャンクをメモリに取り込み、並べ替えます。

  3. 完了したら、それらを 1 つずつマージします。

上記のアルゴリズムは、外部ソートとも呼ばれます。ステップ 3 は N-way マージと呼ばれます。外部ソートを使用する理由は、データのサイズにあります。データが大きすぎてすべてをメモリに入れることができないため、ディスク ベースの並べ替えアルゴリズムを使用する必要があります。

疑問に思う：

ステップ 3 でマージソートを実行しているときに、2 つの配列を比較するとき、比較するたびに 2*X のスペースが必要ですか? 制限は X MB でした。チャンクを (X/2)*2K = 2GB にする必要がありますか? したがって、各チャンクは X/2 MB になり、2K チャンクになります。または、マージソートが間違っていることを理解しているだけですか? ありがとう！

4

3 に答える 3

9

http://en.wikipedia.org/wiki/External_sorting

ウィキペディアをざっと見てみると、マージ プロセス中にチャンク全体をメモリに保持することは決してないことがわかります。したがって、基本的に、K 個のチャンクがある場合、K 個の開いているファイル ポインターがありますが、メモリ内の各ファイルから常に 1 行しか保持できません。メモリ内にある行を比較し、最小のもの (たとえば、チャンク 5 から) を並べ替えられたファイル (メモリ内ではなく、開いているファイル ポインター) に出力し、その行をそのファイルの次の行で上書きします (この例では、ファイル 5) をメモリに格納し、すべてのチャンクの最後に到達するまで繰り返します。

于 2012-05-21T00:52:26.893 に答える
6

まず、ステップ 3 自体はマージソートではなく、全体がマージソートです。ステップ 3 は単なるマージであり、並べ替えはまったく含まれていません。

必要なストレージに関しては、2 つの可能性があります。

1 つ目は、並べ替えられたデータを 2 つのグループにマージすることです。次の 3 つのグループがあるとします。

A: 1 3 5 7 9
B: 0 2 4 6 8
C: 2 3 5 7

その方法では、単一のグループにマージAしてから最終結果にマージします。BYYCZ

Y: 0 1 2 3 4 5 6 7 8 9         (from merging A and B).
Z: 0 1 2 2 3 3 4 5 5 6 7 7 8 9 (from merging Y and C).

これには、2 つのリストのそれぞれから「次の」要素を格納するだけでよいという点で、一定のメモリ要件が非常に小さいという利点がありますが、もちろん、複数のマージ操作を行う必要があります。

2 番目の方法は、任意のグループから次の要素を選択する「適切な」N 方向マージです。それを使用して、すべてのリストの最小値をチェックして、次に来るものを確認します。

Z: 0 1 2 2 3 3 4 5 5 6 7 7 8 9 (from merging A, B and C).

これには 1 回のマージ操作のみが含まれますが、より多くのストレージ (基本的にはリストごとに 1 つの要素) が必要になります。

どちらを選択するかは、使用可能なメモリと要素のサイズによって異なります。

たとえば、100M のメモリが利用可能で、要素のサイズが 100K の場合、後者を使用できます。これは、2G ファイルの場合、ソート フェーズに 20 グループ (それぞれ 100M) が必要であるためです。つまり、適切な N ウェイ マージには、100K x 20、つまり約 2M が必要であり、メモリの可用性を十分に下回っています。

あるいは、1M しか利用できないとしましょう。これは約 2000 (2G / 1M) グループになり、これに 100K を掛けると 200M になり、容量をはるかに超えます。

そのため、複数のパスでそのマージを行う必要があります。ただし、 2 つのリストをマージする複数のパスである必要はないことに注意してください。

たとえば、各パスが 10 個のリストをマージする中間点を見つけることができます。100K の 10 グループはメグにすぎないため、メモリの制約に収まり、マージ パスが少なくなります。

于 2012-05-21T00:50:54.600 に答える
2

マージプロセスはそれよりもはるかに簡単です。それらを新しいファイルに出力しますが、基本的に必要なのは一定のメモリだけです。一度に 2 つの入力ファイルのそれぞれから 1 つの要素を読み取るだけで済みます。

于 2012-05-21T00:49:31.483 に答える