1

2^30 個の符号なし 32 ビット整数値を含むファイルがあり、それらを並べ替える必要があるため、それを行うための最速のアルゴリズムを作成したいと考えています。利用可能なすべてのプロセッサを使用する必要があり、256MB を超えるメモリを使用しないでください。

今思うこと: 最大 int 値 (32 ビット整数の場合) Sm= 2^32、最低 = 0。使用可能なメモリは M=2^28 です。

  • の出力ファイルを分割

    Sm*(整数のサイズ)/M = 2^32*2^5/2^28 = 2^9 パーツ; 各パーツのサイズ 2^32/2^9 = 2^23.

まず、入力ファイルから int 値を読み取り、それがどの範囲にあるかをチェックし、この範囲の整数で一時ファイルに入れる単純なリーダーを作成します。その後、2^9 個のファイルが作成されます。

1 file= Integers from 0:2^23
2 file = 2^23:2^24
3 file = 2^24:(2^24+2^23),
and etc...
  • qsort やピラミッド ソートなどの標準アルゴリズムでソートを行います (このアルゴリズムに関するアドバイスはありますか?)

ここでは並列ソートのために Python.multiprocessing のようなものを使用できますが、各プロセスが開始する前に使用可能な空きメモリを安全に計算する必要があります

このアプローチについてどう思いますか？よりクリーンで簡単なソリューションが存在する可能性がありますか?

4

5 に答える 5

3
  1. 一度にメモリに収まるものを読み取り (これをブロックと呼びましょう)、並べ替えてからディスクに書き戻します (つまり、256 MB のチャンクを並べ替えます)。
  2. すべてのブロックを同時に開き、各ブロックから最初の n エントリを読み取り、ヒープを構築します(n は 256 MB を埋めるようなものです)。
  3. ヒープから最小要素をフェッチし (それがどのブロックから来たかに注意してください)、宛先ファイルに書き出します
  4. 同じ入力ブロックから次の要素を読み取ってヒープに追加し、すべてのデータが処理されるまで前の手順を繰り返します

256 MBytes は 2^28 バイトまたは 2^26 (4 バイト) の整数であるため、2^4 = 16 ブロックをソートするだけで済みます。

于 2012-04-16T12:10:31.450 に答える
2

1)。整数を部分に分割する

a. [0, 2^20 - 1], [2^20, 2^21 - 1]....

2)。各部分について、各整数の数を計算できます（基数ソートのようなもの）。各部分の時間の複雑さは部分の長さです。また、スペースの複雑さは部品の長さでもあります。

// for each part
int start = 0;      // the starting point of the part
int end = 2^20 - 1; // the ending point of the part
int *hash = new int[end - start + 1];
for (int i = start; i <= end; ++i) {
    // read a integer val
    ++hash[val];
}
for (int i = start; i <= end; ++i) {
    if (hash[i] > 0) {
        for (int j = 0; j < hash[i]; ++j) {
            // print i
        }
     }
}

3)。256MB = 256 * 2^20 = 64 * 2^20(int) なので、64 個のパーツを並行して処理できます。また、必要に応じて 2^20 を他の値に設定することもできます。

4)。とにかく、このアルゴリズムの総時間計算量は O(n) + O(2 ^ 32) である必要があります。n は整数の数を示します。n が 2^32 に近い非常に大きい場合、このアルゴリズムは非常にうまく機能します。さらに、このアルゴリズムは並行して処理できます。

5)。このアルゴリズムは、パーツがソートされているため、マージ プロセスを必要としません。

6)。上記のヒープソリューションは、並行して処理されていないようです。

于 2012-04-17T09:10:54.350 に答える
2

ここで重要なのは「符号なし 32 ビット整数値」です。radix sortを使用してソートできます。Wiki ページでは、Python で完全な例を提供しています。

すべてを一度に並べ替えるには十分なメモリがないため、メモリに合わせて作業を分割し、それぞれを並べ替えて結果をディスクに保存し、マージ ソートのマージ パスと同様の方法で結果をマージする必要があります。マージでは、全体をメモリにロードする必要はありません。必要なのは、最終結果を書き込んでいる間にパーシャルから読み取ることだけです。

于 2012-04-16T12:19:12.693 に答える
1

MergeSortの使用を検討してください。簡単な説明はここにあります：http：//en.wikipedia.org/wiki/Merge_sort

マージソートは、並列実装とメモリの制約に適しています。

于 2012-04-16T12:22:22.543 に答える
0

基数ソートはしばしばO（n）と言われますが、実際にはO（nlogn）です。これは、最大数の桁数*数に比例する時間が必要であり、桁数がlog（n）になります。

3レベルの複合ソートを使用することをお勧めします。

  1. 32または64前後の長さの小さなサブリストの挿入ソート-最適なものを見つけるためのベンチマーク-ティムソートがこれをカバーします。
  2. 物理メモリの最大量までの大きなサブリストのティムソートまたはマージソート。timsortはPythonとJavaでソートメソッドに使用され、非常に高速ですが、Cのようなもので作業している場合に重要な、マージソートよりも複雑なアルゴリズムです。シンプルで、mergesortを使用します。
  3. ラージでは、mergesortを使用して、ソートされたラージサブリストを含むソートされたファイルをマージします。

Pythonのマルチプロセッシングモジュールを使用すると、スカラー型の配列（整数など）を共有メモリに格納できます。'覚えておくべきことです。

間違いなく、各コアに大きなサブリストを並べ替えてもらいます。これは、複数のコアを備えたシステムで大いに役立ちます。＃3にminheapを使用するのが良い場合もあれば、配列だけを使用する方が良い場合もあります（大きなサブリストの数が少ない場合）。

于 2012-04-16T17:50:47.760 に答える