マージソートを最適化するには？

Question

私は、各ソート順に数字だけを含む1ギガバイトの2つのファイルをしました。今私は、ファイルの内容を読み取る方法を知っているとソートそれらは別のファイルにマージソートアルゴリズムと出力、それを使用しますが、私が興味は、私が傷を心配しないでください（こののみ使用して100MBのバッファサイズを行う方法にありますスペース）。例えば、一つの方法は、CAN、誰もが私に実装する方法任意のアイデアを与える（ファイルの両方から50メガバイトのチャンクを読み込み、ソート、それ、それがソートされているように私は、新しい要素を読むことができたと私は両方のファイルの最後に到達するまでのプロセスを継続することですこれ）。

Answer 1

彼らはすでに、各ファイルにソートしているので、

は、あなたのように聞こえるだけではなく、ソートして、あなたのファイルでのマージの番号にする必要があります。

：このですにマージソートのmerge部分

function merge(left,right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) ≤ first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append left to result
            break             
        else if length(right) > 0
            append right to result
            break
    end while
    return result

今、あなたはちょうど2つのバッファに両方のファイルからの番号の最初の50メガバイトを読むことができ、マージアルゴリズムを適用し、バッファの一つが（そのすべての数字を分析）枯渇したときに、必要なファイルから別の50メガバイトを読みます。ソート何もする必要はありません。

あなたは自分のバッファの一つが空のチェックであるという条件を必要としています。それがあるときは、バッファが関連付けられているファイルから続きを読むます。

Answer 2

標準ライブラリを利用しないのはなぜ？

#include <fstream>
#include <iterator>
#include <algorithm>

int main()
{
   std::ifstream in1("in1.txt");
   std::ifstream in2("in2.txt");
   std::ofstream ut("ut.txt");
   std::istream_iterator<int> in1_it(in1);
   std::istream_iterator<int> in2_it(in2);
   std::istream_iterator<int> in_end;
   std::ostream_iterator<int> ut_it(ut, "\n");

   std::merge(in1_it, in_end, in2_it, in_end, ut_it);
}

Answer 3

あなたはおそらくI / Oのオーバーヘッドを回避するために、合理的なチャンクで読み取り/書き込みたいです。 だから、おそらく〜30M、INPUT1、INPUT2および出力の3つのバッファを使用します。

は入力バッファのいずれかが空であるか、または出力バッファがいっぱいになるまで継続して行っていき、その後、空/リフィルに/空/フルバッファを読み書きます。

あなたはディスクからのデータの大きなチャンクを読み出し/書き込みされます。

その方法

あなたはソートを行っている間、あなたは、データのリード/ライトを非同期I / Oを必要とすることを越えて。しかし、それはやり過ぎおそらくです。

Answer 4

あなたが唯一のマージではなく、完全なソートをやっているので、

は、それだけで、基本的なマージループです。純粋にシーケンシャルI / O。バッファを心配する必要はありません。ジャケットのジッパーを写真。それは簡単です。 （注：数値は、ファイル内のバイナリ形式であるならば、それははるかに高速かもしれないだけでなく、ファイルが小さくなりますが、プログラムはI / Oが制限され、数字が完全に正確になります。）

double GetNumberFromFile(FILE file){
  if (feof(file)){
    return BIGBIGNUMBER;
  }
  else {
    return ReadADouble(file);
  }
}

double A = GetNumberFromFile(AFILE);
double B = GetNumberFromFile(BFILE);
while (A < BIGBIGNUMBER && B < BIGBIGNUMBER){
  if (A < B){
    write A;
    A = GetNumberFromFile(AFILE);
  }
  else if (B < A){
    write B;
    B = GetNumberFromFile(BFILE);
  }
  else {
    write A;
    write B; // or not, if you want to eliminate duplicates
    A = GetNumberFromFile(AFILE);
    B = GetNumberFromFile(BFILE);
  }
}
while (A < BIGBIGNUMBER){
    write A;
    A = GetNumberFromFile(AFILE);
}
while (B < BIGBIGNUMBER){
    write B;
    B = GetNumberFromFile(BFILE);
}

<時間> あなたの質問に応えて、別のファイルをコピーし、シンプルな問題を考えます。あなただけのファイルシステムがで本当に良いです、シーケンシャルI / Oを、やっています。あなたは、ファイルからのバイトまたはint型のような小さな単位を読んで、そして他にそれを書くための簡単なループを記述します。あなたがバイトを読み取ろうとすぐに、システムは素敵な大きなバッファを割り当てると、バッファにファイルの大きな塊をスワイプして、あなたはバッファからバイトを供給します。あなたは、それは目に見えないあなたのために別のものをgloms別のバッファを必要とするまで、ということをやって続けています。ものと同じ種類のは、あなたが書いているファイルで発生します。今では、入力を反復処理することができますので、CPUは、かなり速いです読み取りや書き込みが任意のよりも速く行くことができないので、それは、バッファを読み書きするのにかかる時間の割合で、出力にコピー、バイト外部ハードウェア。大きなバッファが役立つだろう唯一の理由は、読書の部分である/時間を書くことは、「レイテンシー」それが所望のトラックにヘッドを移動し、所望のセクタが集まってくるのを待つのにかかる基本的に時間と呼ばれるものです。ヘッドはとにかくジャンプしているので、ほとんどのファイルシステムは、ディスクの周りに振りかけているチャンクにファイルを分割します。あなたはそれを聞くことができます。

コピーしてあなたのようなマージアルゴリズムの唯一の違いは、それは2つのファイルでないものを読んでいるです。どちらにしても、基本的な時系列はバッファのシリーズは、CPU動作の少量が点在読み込みと書き込みです。 の間、（そうの無を起こりそうすることを、の重複を行うためにI / O可能です>バッファ間の遅延は、読み出しと書き込みが、それはCPUが1000倍遅かったとき、大きな取引でした。）

あなたがファイルを読み書きしているように、それを手配することができます場合は、

もちろん、別々の物理ディスクドライブ上のすべてであり、ドライブは、ヘッドの動きの量を最小限に抑えることができ、非常に断片化されていない、と大きなバッファのかもしれないのヘルプ。しかし、基本的には、簡単なプログラムで、あなたはかなりのない程度のディスクにデータを移動することができ、そして巨大なバッファが役立つかもしれませんが、のような簡単なコードを約早く行くことを期待することができます。

Answer 5

ベンチマーク。値ごとの値とブロックの読み取りをお読みください。違いを感じます！ =）