5

K個のファイルがあります。私はそれらをX1、X2、...、XKと呼びます。
これらの各ファイルは、 doubleのNx1配列です。
これは、実際にはNK x 1配列があり、 K配列に分割されていることを意味します。この大きな配列をXと呼びましょう。

Xをソートする必要があり、すべてのデータをメモリにロードできません。この並べ替えを実行し、結果を別々のファイルに保存するための効率的なアルゴリズムは何ですか？

H要素をソートしたいだけの場合、私はそれを行う方法を知っています（もちろん効率的ではありません）：

  1. X1を並べ替えて、 sX1として保存します
  2. A = sX1（1：H、1） //Matlabで
  3. X2とAを 並べ替える
  4. 他のファイルについても手順1、2、3を繰り返します

ただし、メモリの問題があるため、 Hを大きくすることはできません。

限られたメモリの質問で並べ替えを更新
することは 、役に立ちましたが、この質問とは異なります。その質問の回答またはMikeBの回答を使用する場合は、これにも回答する必要があります。Kファイルを1つのファイルにマージしてから、外部ソートアルゴリズムを使用する必要があります。はいの場合、どのように？

ありがとう。

4

1 に答える 1

7

あなたが試みていることは、外部ソートと呼ばれます。各パーティションは、それ自体でソートされます。次に、すべてのパーティションをマージして、最終的なソート済みリストを作成する必要があります。上位のいくつかのアイテムのみを探している場合は、マージを早期に終了できます。

外部マージ用の既存のソリューション matlab ソリューションがいくつかあるようです。mathworks のファイル交換サイトへのリンクは次のとおりです。

更新: リンクしたコードは、matlab での実行方法を示しています。具体的には、ここのコード: http://www.mathworks.com/matlabcentral/fileexchange/29306-external-merge-sort/content/ext_merge/extmerge.mは、マージする必要があるファイルのリストを取得し、最終的にそれらをマージします1 つのファイルに。

元の問題ステートメントでは、X1 から XK までの K 個のファイルがあると述べました。外部ソートは、最初にこれらのファイルをソートしてから、それらを 1 つのファイルにマージします。簡単な実装では、次のような疑似コードを使用します。

// external merge-sort algorithm
For each file F in (X1 ... XK)
    Read file F into memory array R
    Sort R
    Overwrite file F with sorted data from R
    Clear array R in memory
For N = K-1 down to 1
    in-order merge file XN+1 and XN into file X'
    erase file XN+1 and XN
    rename file X' as XN

最初のフェーズはソートであることがわかります。各ファイルをメモリに読み込み、並べ替え、書き戻します。これは I/O ですが、効率的です。うまくいけば、できるだけ多くのメモリを使用して、できるだけ多くのメモリをソートできるようにしています。最初のループの終わりには、K 個のファイルがあり、それぞれが独自の値のドメイン内でソートされています。

K 個のファイルがソートされた場合、次のステップはそれらをマージすることです。2 つのファイルをマージしてもメモリは消費されませんが、大量の I/O が発生します。2 つのファイルのマージは次のようになります。L と R という名前の 2 つのファイルがあれば、それらを O にマージできます。

// merge two files algorithm
Get value LV from L
Get value RV from R
While L is not EOF AND R is not EOF
    if ( LV <= RV )
        write LV into O
        get value LV from L
    else 
        write RV into O
        get value RV from R
While L is not EOF
    get LV from L
    write LV into O
While R is not EOF
    get RV from R
    write RV into O

マージソートの 2 番目のループは、2 つのファイル N+1 と N を 1 つのファイル N にマージします。各ファイルをループしてマージします。これは大量のデータの読み取りと再書き込みを行いますが、ループ内で複数のファイルを処理することにより、それよりも少し効率的になります。しかし、私が書いたようにうまくいきます。

于 2012-12-18T16:10:48.197 に答える