1

Imagine the following scenario: I have a 10 Mb array of integers stored on a read-only storage medium. I wish to print out the numbers in ascending order. However, I only have 2 Mb of main memory (and no hard disk).

A very simple O(n2) solution (which doesn't make use of the available main memory) would be to repeatedly scan the entire input array and incrementally output the next smallest integer. I've tried googling for better sorting algorithms, but the answers keep leading me to in-place or external sorting algorithms, which would not work because of the read-only storage constraint. Is there a better solution?

4

1 に答える 1

5

メインメモリを使用して、指定したサイズの関係でスキャンの数を大幅に減らすことができます。

最初のスキャン：これまでに見つかった最小の数で、ほぼメインメモリサイズのメモリ内ストアを保持します。ストアがまだいっぱいになっていない間に、配列から読み取った次の番号を追加します。ストアがいっぱいになったら、ストア内の最大数と比較します。新しい数が小さい場合は、最大数を削除して新しい数を追加します。配列全体がスキャンされたら、見つかった番号を順番に出力し、保存されている最大数と、このチャンクで発生した頻度を覚えておいてください。

後続のスキャン：スキャンされた数が前のチャンクの最大数と等しく、その発生数が前のスキャンの数よりも少ない場合は、発生数を増やしますが、発生数が多い場合はストアに追加しないでください記憶されているカウント以上の数をストアに追加します（必要に応じてストアから最大数を削除します）。スキャンされた数が前回のスキャンの最大数よりも大きいが、ストア内の最大数よりも小さい場合（またはストアがまだいっぱいでない場合）、ストアに追加します（必要に応じて最大数を削除します）。スキャンが完了したら、保存されている番号を順番に出力し、これまでに出力された最大数と合計で出力された数を覚えておいてください（最大数は前回のスキャンと同じである可能性がありますが、

ストアに最適なデータ構造が何であるかはわかりませんが、ヒープが適切な選択だと思います（最大値との比較：O（1）、置換：O（ログサイズ）、出力の最終ソート：O （サイズ*ログサイズ）、バイナリ検索ツリーの場合のように実質的にメモリオーバーヘッドはありません）。

于 2012-09-19T01:09:05.740 に答える