1

私は外部ソートを使用してこれに答えようとしましたが、インタビュアーは複雑さが高いと答えました nn(log(n)) つまり n square *logn. より良い代替手段はありますか。

質問を簡単にするために、100 個の要素のみに割り当てられたスペースでソートする 1000 個の要素があるとします。外部ソートよりも時間がかからない最適なアルゴリズムは何ですか?

4

3 に答える 3

5

あなた（またはインタビュアー）がどの外部ソートを意味したかはわかりませんが、

私の提案は、10通りの（あなたの場合）マージです：

  • ファイルを MAX_MEM サイズ (100 要素) のチャンクに分割します。
    • これはO(1)
  • メモリ内の各チャンクをソートし、個別のファイルとして保存します
    • これはO((n/max_mem) * (max_mem) log(max_mem)))=O(n log(max_mem))
  • すべてのチャンクを要素のストリームとして開く
  • 各ステップで最下位の要素を選択して、すべてのストリームをマージします。
    • これはO(n log(n/max_mem))minHeapを使用しているか、簡単に使用していO(n^2/max_mem)ます（実際にはより高速になる場合があります）
  • チャンクを削除する

計算に関しては、これはO(n (log(max_mem)+log(n/max_mem)))=O(n log(n))

ディスク I/O に関しては、すべてのマージが 1 つのパスで行われる場合、これは2*n読み取りと2*n書き込みのみです。より一般的には、(1+[depth of the merge tree])*n

すべての書き込みはシーケンシャルです。最初の読み取りはシーケンシャルで、2 番目の読み取りはシーケンシャルで、10 個のファイルからインターリーブされます。

もっと多くのデータがある場合は、繰り返しまたは再帰的なマージが必要になります (チャンクごとに 100、次に N チャンクを繰り返し選択します)。この時点で、@amit の回答で説明されているように、分割 + 並べ替えステップを置換/選択に置き換える価値があります。特に、データがすでにほとんど並べ替えられている場合 (マージ手順を完全に回避することができます)。

N を高くすると、計算量が増加する可能性があります (適切な構造を使用している場合はごくわずかです) が、ディスク I/O の量が大幅に減少することに注意してください (一定量まで。一度にマージするチャンクが多すぎると、不足する可能性があります)。読み取りバッファ用のメモリが不足し、不要な読み取りが発生する可能性があります)。ディスク I/O は高価ですが、CPU サイクルはそうではありません。

于 2012-12-08T08:31:13.877 に答える
3

おそらくインタビュアーは、あなたがこう尋ねることを期待していたでしょう: それらの番号は、J. ベントレー ( Cracking the Oyster ) が言及した固有の 7 桁の電話番号ですか?

于 2012-12-08T09:05:33.687 に答える
3

それを行う標準的な方法は、外部ソートです。

外部ソートでは、複雑性を持つことが重要であるだけでなくO(nlogn)、ディスクの読み取り/書き込みを可能な限り最小限に抑え、ほとんどの読み取りと書き込みを (ランダムではなく) シーケンシャルにすることも重要です。これは、ディスク アクセスがはるかに効率的であるためです。順番に行う場合。

これを行う標準的な方法は、@ JanDvorak によって提案されているように、実際には k-way マージソートですが、いくつかの欠点と、私が修正しようとしている提案への追加があります。

  1. まず、入力に対してRS (Replacement-Selection)を実行すると、最初の「実行」数 (増加するシーケンスの数) が減少するため、通常、後でマージソートに必要な反復の総数が減少します。
  2. バッファリング (入力の読み取りと書き込み) にはメモリが必要です。したがって、メモリ サイズ M とファイル サイズ M*10 の場合、10 方向マージを行うことはできません。ブロックで）。 - マージの「順序」
    の標準式は次のとおりです(M はメモリのサイズで、各「バッファ」(通常はディスク ブロック) のサイズです)。kM/(2b)b
  3. 各マージソートステップはb、前の反復で生成された各「実行」からエントリを読み取りM/2、メモリに書き込むことによって行われます。メモリの残りの部分は、「予測」 (IO の待機を最小限に抑えて継続的な作業を可能にする) 用であり、実行からより多くの要素を要求し、出力バッファー用です。
  4. このアプローチでの反復の合計回数は、 は実行回数log_k(N/(2M))(k以前に計算されたもの)、MはメモリNのサイズ、 はファイルのサイズです。各反復には、ファイル全体の 1 回のシーケンシャル読み取りと 1 回のシーケンシャル書き込みが必要です。

つまり、file_size/memory_size の比率は通常 10 をはるかに超えています。10 の比率のみに関心がある場合は、ローカル最適化が行われる可能性がありますが、より一般的なケースではありません。file_size/memory_size >> 10

于 2012-12-08T08:48:44.937 に答える