12

数十億の整数を含む非常に大きなファイルがありk、これらの値の最大の要素を見つけたいとします。

トリッキーな部分は、kそれ自体も非常に大きいことです。つまり、k要素をメモリに保持することはできません (たとえば、1000 億の要素を含むファイルがあり、100 億の最大の要素を見つけたいとします)。

でこれを行うにはどうすればよいO(n)でしょうか。

私が思ったこと：

ファイルの読み取りを開始し、最大の要素を保持する別のファイルでチェックしますk(昇順でソート)。読み取った要素が 2 番目のファイルの最初の行よりも大きい場合は、最初の行を削除して 2 番目の行に挿入します。 file 、時間の複雑さはO(NlogK)(そのファイルにランダムにアクセスできる場合、それ以外の場合は「O(Nk)」になります)

でこれを行うアイデアはありますが、（クイックソートのパーティショニングアルゴリズム）のO(n)外部バージョンがあれば、でSelection algorithmこれを行うことができると思いますがO(n)、どこにも見つかりませんでした

4

6 に答える 6

11

これは、標準のマージ タイプ アルゴリズムを使用して非常に簡単に行うことができます。

1000 億の数字があり、上位 100 億が必要だとします。いつでも 10 億個の数字をメモリに保持できると言います。

したがって、パスを作成します。

while not end of input
    read 1 billion numbers
    sort them in descending order
    save position of output file
    write sorted numbers to output file

次に、それぞれ 10 億個の数字の 100 ブロックを含むファイルを作成します。各ブロックは降順でソートされます。

ここで最大ヒープを作成します。各ブロックの最初の番号をヒープに追加します。次の番号を読み取ることができるように、ファイル内のブロック番号または番号の位置も追加する必要があります。

それで：

while num_selected < 10 billion
    selected = heap.remove()
    ++num_selected
    write selected to output
    read next number from the selected block and place on heap

数字がどのブロックから来たのかを追跡するという複雑な作業が少しありますが、それほど悪くはありません。

最大ヒープには 100 を超えるアイテム (基本的にはブロックごとに 1 つのアイテム) が含まれることはないため、2 番目のパスではメモリは問題になりません。少しの作業で、ブロックごとに小さなバッファーを作成することで、大量の読み取りを回避できます。これにより、選択された数値ごとにディスク読み取りのコストが発生しなくなります。

これは基本的に単なるディスク マージ ソートですが、アーリー アウトがあります。

最初のパスの複雑さは ですb * (m log m)。ここで、b はブロックの数、m はブロック内のアイテムの数です。ファイル内の項目の総数 N は に等しくなりb * mます。2 番目のパスの複雑さは ですk log b。ここkで、 は選択するアイテムの数、b はブロックの数です。

于 2013-07-05T04:59:11.263 に答える