2

非常に大きなデータセットに I/O 集約型のクイックソート (C++ qsort) を実装しようとしています。速度のために、一度にデータのチャンクをバッファーに読み込み、qsort を使用してバッファー内で並べ替えたいと思います。(私は現在テキスト ファイルで作業していますが、すぐにバイナリに移行したいと考えています。)ただし、私のデータは可変長レコードで構成されており、ソートするにはレコードの長さを qsort に伝える必要があります。これを標準化する方法はありますか?私が考えることができた唯一のことはかなり複雑でした: 私のプログラムは現在、改行文字 (ascii の '10') に達するまでバッファーから読み取り、各文字を別の配列に転送します。改行(入力ファイルの区切り文字)を見つけると、そのレコード (レコード サイズが 30 に設定されている) のバッファーに残っているスペースの数を null 文字で埋めます。このようにして、qsort を実行するための固定サイズのレコードでいっぱいのバッファを作成する必要があります。

私のアプローチにはいくつかの問題があることを私は知っています.1つはそれが不器用であること、もう1つはレコードサイズがおそらく30を超える可能性があることですが、一般的にははるかに小さいことです。これを行うより良い方法はありますか?

同様に、私の現在のコードは機能しません。デバッグすると、あるバッファから別のバッファに文字を転送しているように見えますが、バッファを印刷しようとすると、最初のレコードしか含まれていません。

これが私のコードです:

FILE *fp;
unsigned char *buff;
unsigned char *realbuff;
FILE *inputFiles[NUM_INPUT_FILES];
buff = (unsigned char *) malloc(2048);
realbuff = (unsigned char *) malloc(NUM_RECORDS * RECORD_SIZE);

fp = fopen("postings0.txt", "r");
if(fp)
{
    fread(buff, 1, 2048, fp);


    /*for(int i=0; i <30; i++)
     cout << buff[i] <<endl;*/

    int y=0;
    int recordcounter = 0;

    //cout << buff;
    for(int i=0;i <100; i++)
    {
        if(buff[i] != char(10))
        {
            realbuff[y] = buff[i];
            y++;
            recordcounter++;
        }        
        else
        {
            if(recordcounter < RECORD_SIZE)
                for(int j=recordcounter; j < RECORD_SIZE;j++)
                {
                    realbuff[y] = char(0);
                    y++;
                }
            recordcounter = 0;
        }
    } 

    cout << realbuff <<endl;   
    cout << buff;
}
else 
    cout << "sorry";

どうもありがとう、bsg

4

2 に答える 2

1

qsort 関数は、固定長レコードでのみ機能します(あなたが言うように)。可変長レコードをソートするには、それらへのポインターの配列が必要であり、qsort でポインターの配列をソートします。ポインターはデータの大きなチャンクよりもはるかに高速に移動できるため、これもより効率的です。

同じことが std::sort にも当てはまります。これはタイプ セーフであるため推奨されます。3 番目のパラメーターとしてポインターを引数として取る比較述語 (より小さい関数) を必ず指定してください。

于 2010-03-03T06:37:08.170 に答える
0

ファイルの解析にC++ ファイル ストリームを使用するのはどうですか?

レコードをSTL ベクトルとして返すこの(Web サイト名は奇妙ですが、違反ではありません!!) をチェックしてから、 STL ソート アルゴリズム を使用できます。

于 2010-03-03T06:47:18.220 に答える