外部ソートアルゴリズムを使用したソートの予想時間

Question

ソートの最小予想時間（秒）を知っている人は誰でも、16ビットの整数の64MBバイナリファイルを使用します。つまり、16777216の値を昇順に並べ替えます「メモリ不足例外」を発生させる可能性のある内部ソートアルゴリズムまたはデータ構造2つの補助ファイルにデータを配布し、それらをマージして最終的なソートされたシーケンスを生成します。これは、外部マージソートがどのように機能するかを表したものです。k繰り返しです。

アルゴリズムに関するいくつかの仮定は、Javaで書かれており、バッファされた読者とライターを使用し、5GBのメモリを搭載したデュアルコアWindowsマシン上で実行されているということです。

私は少し奇妙だと知っていますが、いくつかの最小時間は私が願って推定することができますか？もっと情報が必要な場合は、尋ねてください。

ありがとう！

Answer 1

一般的な外部ソートでは、通常、I/O時間が制限要因になります。 標準アルゴリズムを使用する場合、外部ソートにかかる時間は、入力ファイル全体を2回読み書きするのに要する時間です。

外部ソートは2回のパスで行われたとします。最初のパスでは、入力ファイルは固定サイズのブロック単位で読み込まれます。各ブロックが読み取られると、ソートされた後、一時ファイルに書き込まれます。最初のパスが終了すると、入力ファイル内のすべての項目が一度読み込まれ、一度書き込まれます。

第2パスでは、k-wayマージを使用して一時ファイルを1つのソート済み出力ファイルに結合します。ここでもまた、すべてのアイテムがディスクから一度読み込まれ、ディスクに一度書き込まれます。

入力ファイルがすでにソートされており、ブロックソートアルゴリズムが適切に実装されている場合、個々のブロックをソートする時間はほとんどありません。マージと同じです：既にソートされたファイルは、kウェイマージのための最良のケースです。

現代のデスクトップハードウェアでは、1ギガバイトあたり約20秒、読書の場合は2倍、おそらく書込みの場合は2倍です。したがって、ギガバイトあたり約1分の絶対最小時間が必要です。大規模なファイルの読み書きではベンチマークを自分で行うこともできますが、OSのファイルキャッシュを無効にするか、何らかの形でそれを考慮する必要があります。それ以外の場合は、良い数字を取得していない。

ソートとマージには、もちろん時間がかかります。あなたが気にしているブロック・サイズの配列を作成し、乱数を繰り返し入力してソートすることで、各ブロックのソートに要する時間を見積もることができます。 10または100のソートを行うのにかかる時間を平均します。それは見積もりの​​ための妥当な数です。

私の経験では、kブロックをマージするのに要する時間を見積もってみましょう。（_を記録

マージ時間=（コピー時間）*（ログ：第2のパスが）しかし、長い、それは時間がログ入力ファイル（ログ（ブロック数））をコピーするのにかかるとかなり近いです2（ブロック数）））

私は1GBのファイルがあり、64MBのブロックを使用しています。したがって、マージするブロックは16個です。私は既にギガバイトをコピーするのに1分かかることを確認しました。したがって、マージを実行するのにかかる時間の見積もりには、ログの1分分のログがあります。（ログ（16））です。 log(log(16))は2に等しいので、16個の入力ファイルを結合するのに約2倍の時間がかかります。これは、結合されたサイズの単一ファイルをコピーするだけです。

あなたはすべて一緒にそれを置くとき、あなたはブロックサイズにB

• 時間を使用してファイルサイズSのあなたの典型的な外部ソートを行うために必要な時間の見積もりについては、以下で終わりますサイズがのファイルをコピー（読み書き）するにはS;プラス
• ソート時間S/Bブロック;プラス
• 時間は、時間が_が2ログサイズのファイルSを（読み取りおよび書き込み）をコピーします（ログイン（S/B））

それは仕方によって、重要です上記のブロックソートのベンチマークを行う。整数は、通常、文字列よりもはるかに高速にソートされます。最初の数文字では文字列が大きく異なる文字列は、最初の20文字で同じ文字列よりも高速にソートされます。ベンチマークを実行するときは、できるだけ実際のデータに近いデータを使用することをお勧めします。

Answer 2

ObjectInputStreamの使用について考える必要があります。 IntegerはSerializableを実装しているので、はるかに簡単で迅速になります。参照：

long howLong(String path) throws IOException, ClassCastException{ 
    long start = System.currentTimeMillis(); 
    ObjectInputStream ois = new ObjectInputStream(new FileInputStream(new File(path))); 

    List<Integer> allInts = new ArrayList<>(); 
    while(ois.ready()){ 
     allInts.add((Integer)ois.readObject()); 
    } 
    ois.close(); 
    sortList(allInts); 

    ObjectOuputStream oos = new ObjectOutputStream(new FileOutputStream(newFile(path))); 

    for(Integer i:allInts){ 
     oos.writeObject(i); 
    } 
    oos.close(); 
    long end = System.currentTimeMillis();  

    //returns how long the alg took 
    return (end-start)/1000; 
} 

private <E extends Comparable<E>> void sortList(List<E> l){ 
    boolean sorted; 
    while(!sorted){ 
     soreted=true; 
     for(int i=0,n=l.size()-1;i<n;i++){ 

      if(arr1[i].compareTo(arr1[i+1])>0){ 
       E tmp = l.get(i); 
       l.get(i) = l.get(i+1); 
       l.get(i+1) = tmp; 

       sorted = false; 
      } 
     } 

    } 


} 

マシンでこれを実行し、返すものを確認してください。出力は秒になります。