1

これが以前に繰り返された場合は申し訳ありませんが、選択した文言の投稿は見つかりませんでした. 面接の準備をしていて、外部選別について読んでいます。たとえば、32 ビット整数の複数のハード ディスクを並べ替えたい場合は、カウント ソートを行い、64 ビット カウンターを使用して 32 ビット整数をカウントできます。次に、考えられるすべての 32 ビット整数値で、それを表すカウンターがあります。O(1) 時間の代わりに O(nlogn) 時間をかけて、同様のことを行うために外部マージソートを使用することもできます。ただし、おそらく非常に一般的なケースについて考えていましたが、それを行うための最良の方法が思い浮かびません。おそらく多くのハードディスクにまたがるソートされたファイルの束に新しいデータを追加することです。

データがメモリ内にある場合、ヒープ (プライオリティ キュー) を使用して、ログイン時にこの挿入を実行できます。ただし、ハードディスク領域からヒープを作成することはできません。リストでは、O(logn) 検索を使用してデータの場所を見つけ (バイナリ検索の場合は並べ替え)、残りのデータを前後にバンプするか、実装によっては何もシフトする必要がない場合があります。コンテナ (配列、リンクされたリストなど) の。ただし、ハードディスクの世界では、読み取りと書き込みは RAM よりもはるかにコストがかかるため、データをどこかに挿入してから残りのデータをシフト (再書き込み) すると、法外にコストがかかるように見えます。あなたの誰かが私に勧めることができるこれのためのテクニックはありますか? 私は自分自身を読んで喜んでいます.情報を見つけるために私の質問を表現する正しい方法を見つけることができませんでした. ありがとうございました！

4

3 に答える 3

2

ここ（または他の場所）で「外部ソート」を調べると、あなたが説明していることについての議論が見つかります。ここでも external-sorting はタグです。

ただし、ハードディスクの世界では、読み取りと書き込みは RAM よりもはるかにコストがかかるため、データをどこかに挿入してから残りのデータをシフト (再書き込み) すると、非常にコストがかかるように見えます。

外部ソートは、内部で実行するのに十分なメモリ (またはほとんどの場合「プロセスごと」) がない場合に使用します。データ セットが大きすぎて一度にメモリに保持できないことは珍しくありません。そのため、I/O バウンドの並べ替えの実行時コストが高くなることを受け入れます。

于 2013-03-14T13:40:08.020 に答える
2

ソートされたデータのそのファイルを読み取り、ソートしてそこに追加するファイルを読み取り、カウンターを締めて、ソートされたデータファイルを新しく計算されたファイルで単純に上書きします。最新のディスクシステムでは、直接読み取りはランダム読み取りよりも大幅に安価であり、見つけたすべてのintの位置が必要になるため、ボリューム全体の1回の順次読み取りは、単一セクターの〜32回の読み取りよりも時間がかかりません。ソートするファイルの数ごと。

また、32 ビット int の並べ替えは、特に「複数のハードディスク」のような超大規模で、結果が既にカウンターの形式になっている状態で行うのが最適であると言えます。ビット空間なので、64 ビット *2^32 を格納すると、2^33 の 32 ビットのゼロ、次に 2^32 のゼロよりも小さくなる可能性があります...

于 2013-03-14T13:45:34.097 に答える
1

ファイルを保持するためのスペースがメモリにあり、最小要素が k である一連の数値がある場合、k より大きいファイル内のすべての数値を書き直す必要があります。これを回避する方法はありません。それらはすべて、少なくとも 1 つの位置を変更する必要があります。

配列の大部分が既にソートされているという事実を利用しようとしていて、メモリ内にそうするためのスペースがある場合は、挿入された要素をソートし、それをその最小メンバーよりも大きい要素のリストとマージすることは、これを行うための良い、迅速な方法。例えば：

ディスク：

1 2 3 4 5 6 8 10 11 12

挿入: 9 7 13

挿入を並べ替えます。

7 9 13

適用されるディスク上のソート済みリストのサブセットを見つけます: 8 10 11 12

の要素をマージします (Mergesort :) のように

7 8 9 10 11 12 13

それらをディスクにコピーして戻します。

1 2 3 4 5 6 7 8 9 10 11 12 13

一方、メモリ内のスペースがリストの合計サイズよりも極端に小さい場合は、他の手法をお勧めします。例えば：

1 2 3 4 .. 1000 1002 1003... 999,998, 1,000,000...

ディスク上のリストとして

1001、999,999

あなたの挿入として。この状況では、各要素を調べて、その要素よりも小さい挿入リスト内の要素の数を計算してから、そうする必要があります。この単純な例では、単純なカウンターは非常に高速です。1,000,0000 の場合、2 つのジャンプが必要であることがわかります。挿入の数が比較的多い場合は、挿入を並べ替えてから、この要素に対してバイナリ検索を使用して、より大きな配列内の各要素がどこにあるかを見つけることができます。これにより、コピーできるアイテムの数に関する情報が得られます。したがって、対応する top の jump の値は次のようになります。

0 0 0 0 ... 0 1 1 ... 1 2

挿入要素の 1 つをディスクに書き込むことを決定するためのかなり明白な方法を理解していただければ幸いです。

于 2013-03-14T17:45:26.653 に答える