5

1行で構成されるファイルがあります：

 1 , 1 2 , 1 3 6 , 4 ,...

この表現では、スペースが整数とコンマを区切ります。この文字列は非常に大きいため、RandomAccessFile.readLine() で読み取ることができません (ほぼ 4 Gb が必要です)。そのため、10 個の整数を格納できるバッファーを作成しました。私の仕事は、文字列内のすべての整数をソートすることです。

助けてくれませんか？

編集

@オスカー・レイエス

いくつかの整数シーケンスをファイルに書き込み、それから読み取る必要があります。実際、私はそれを行う方法を知りません。私は初心者です。そこで、文字を使用して整数を書き込むことにしました。整数間の区切り文字は「,」であり、シーケンス間の区切り文字は「\n\r」です。だから私はそれを読むモンスターを作成しました：

public BinaryRow getFilledBuffer(String filePath, long offset) throws IOException{
    mainFile = new RandomAccessFile(filePath, "r");

    if (mainFile.length() == 0){
        return new BinaryRow();
    }

    StringBuilder str = new StringBuilder();

    mainFile.seek(mainFile.length()-4); //that is "\n" symbol
    char chN = mainFile.readChar();

    mainFile.seek(offset);
    int i = 0;
    char nextChar = mainFile.readChar();
    while (i < 11 && nextChar != chN){
        str.append(nextChar);
        if (nextChar == ','){
            i++;
            if (i == 10){
                break;
            }
        }
        nextChar = mainFile.readChar();
    }

    if (nextChar == chN){
        position = -1;
    }else{
        position = mainFile.getFilePointer();
    }

    BinaryRow br = new BinaryRow();

    StringBuilder temp = new StringBuilder();

    for (int j = 0; j < str.length(); j++){
        if ((str.charAt(j) != ',')){
            temp.append(str.charAt(j));
            if (j == str.length() - 1){
                br.add(Integer.parseInt(temp.toString()));
            }   
        }else{
            br.add(Integer.parseInt(temp.toString()));
            temp.delete(0, temp.length());
        }
    }


    mainFile.close();
    return br;

}

あなたがそれを行う方法をアドバイスできるなら、それをしてください=）

4

2 に答える 2

15

これはまさに元のQuickSortであり、メモリ内でソートするのに十分な RAM がなかったので、手順は部分的な結果をディスクに保存することです。

だからあなたができることは次のとおりです。

  1. ピボットを選択します。
  2. ファイルを順番に読み取り、ピボットより低いデータを temp_file_1 に格納し、ピボット以上のデータを temp_file_2 に格納します
  3. temp_file_1 で手順を繰り返し、結果を result_file に追加します。
  4. temp_file_2 に対して手順を繰り返し、結果を result_file に追加します。

パーツが十分に小さい場合 ( 2 つのように直接スワップするだけで、メモリ内でソートするのに十分です)

このようにして、チャンクでソートし、部分的な結果を一時ファイルに保存することができ、結果がソートされた最終ファイルが得られます。

編集クイックソートが可能だと言いました。

結局、一時ファイル用に余分なスペースが必要になるようです。

これが私がしたことです。

コンマで区切られた数字で 40 MB のファイルを作成します。

私はそれに名前を付けますinput：

入力 http://img200.imageshack.us/img200/5129/capturadepantalla201003t.png

入力は40MB

ソート中に、「より大きい」、「より小さい」値のバケットを持つ tmp ファイルが作成され、ソートが終了すると、値は (何を推測する) というファイルに送信されます。output

処理 http://img200.imageshack.us/img200/1672/capturadepantalla201003y.png

一時ファイルは部分的な結果で作成されます

最後に、すべての tmp ファイルが削除され、結果が正しくソートされた番号の順序で「出力」ファイルに保持されます。

出力 http://img203.imageshack.us/img203/5950/capturadepantalla201003w.png

最後に、ファイル「出力」が作成されます。これも 40 MB であることに注意してください。

これが完全なプログラムです。

import java.io.*;
import java.util.*;

public class FileQuickSort {

    static final int MAX_SIZE = 1024*1024*16; // 16 megabytes in this sample, the more memory your program has, less disk writing will be used. 
    public static void main( String [] args ) throws IOException {
        fileQuickSort( new File("input"), new File("output"));
        System.out.println();
    }

    //
    static void fileQuickSort( File inputFile, File outputFile ) throws IOException {
        Scanner scanner = new Scanner( new BufferedInputStream( new FileInputStream( inputFile ), MAX_SIZE));
        scanner.useDelimiter(",");

        if( inputFile.length() > MAX_SIZE && scanner.hasNextInt()) {
            System.out.print("-");

            // put them in two buckets... 
            File lowerFile = File.createTempFile("quicksort-","-lower.tmp",new File("."));
            File greaterFile = File.createTempFile("quicksort-","-greater.tmp", new File("."));
            PrintStream  lower   = createPrintStream(lowerFile);
            PrintStream greater  = createPrintStream(greaterFile);
            PrintStream target = null;
            int pivot = scanner.nextInt();

            // Read the file and put the values greater than in a file 
            // and the values lower than in other 
            while( scanner.hasNextInt() ){
                int current = scanner.nextInt();

                if( current < pivot ){
                    target = lower;
                } else {
                    target = greater;
                }
                target.printf("%d,",current);
            }
            // avoid dropping the pivot
            greater.printf("%d,",pivot);
            // close the stream before reading them again
            scanner.close();
            lower.close();
            greater.close();
            // sort each part
            fileQuickSort( lowerFile , outputFile );
            lowerFile.delete();
            fileQuickSort( greaterFile   , outputFile);
            greaterFile.delete();

            // And you're done.
        } else {

            // Else , if you have enough RAM to process it
            // 
            System.out.print(".");
            List<Integer> smallFileIntegers = new ArrayList<Integer>();
            // Read it
            while( scanner.hasNextInt() ){
                smallFileIntegers.add( scanner.nextInt() );
            }
            scanner.close();

            // Sort them in memory 
            Collections.sort( smallFileIntegers );

            PrintStream out = createPrintStream( outputFile);
            for( int i : smallFileIntegers ) {
                out.printf("%d,",i);
            }
            out.close();
            // And your're done
        }
    }
    private static PrintStream createPrintStream( File file ) throws IOException {
        boolean append = true;
        return new PrintStream(  new BufferedOutputStream( new FileOutputStream( file, append )));
    }
}

ファイルの形式は次のとおりです。number,number,number,number

現在の形式は次のとおりです。n u m b e r , n u m b , b e r

それを修正するには、すべてを読んで空白をスキップするだけです。

そのために別の質問を追加します。

于 2010-03-04T21:35:39.937 に答える
1

一度に1チャンクずつ、チャンク（各100 MB？）でメモリに読み込み、並べ替えてディスクに保存します。

次に、順序付けられたすべてのチャンクを開き、それぞれの最初の要素を読み取り、出力に最も低いものを追加します。次に、読み取ったばかりのチャンクの次の要素を読み取り、繰り返します。

マージするときは、各チ​​ャンクから読み取られた最後のintの配列を保持し、それを反復処理して最小値を取得できます。次に、使用した値を、それが取得されたチャンク内の次の要素に置き換えます。

example with chunks [1, 5, 16] [2, 9, 14] [3, 8, 10]
array [(1), 2, 3], lowest 1 --> to output
      [5, (2), 3], lowest 2 --> to output
      [5, 9, (3)], lowest 3 -->
      [(5), 9, 8],        5
      [16, 9, (8)],       8
      [16, (9), 10],      9 
...
于 2010-03-04T21:30:02.197 に答える