0

100,000 個の double のファイルに対して外部マージソートを実行するプログラムを作成しました。C ++の外部ストレージライブラリをすばやく見つけることができませんでした。これをグーグルで検索するとexternキーワードに関するページがたくさん表示されるだけなので、自分で書くことにしました。そこに問題があると思います。

いくつかの詳細を除いて、プログラムは実際に機能します。出力の塗りつぶしには、すべての double がソートされた順序で含まれますが、ファイルの最後には 30 行の

-9.2559631349317831e+061

これは入力ファイルにありません。また、出力ファイルと入力ファイルにはさらに 21 個の値がありますが、先ほど述べた単一の数値の 30 行は数えません。

プログラムの実行方法は、一度に 100,000 個の double 〜 4000 行を読み取り、それらを並べ替えて、26 個のテキスト ファイルに保存し、次にそれらの 26 個のファイルを 13 個のファイルにマージし、それらの 13 個を 7 個にマージするなど...までファイルは 1 つだけです。

コードが本当に醜い場合は申し訳ありませんが、私は鉛筆、紙、試行錯誤によって自分ですべての外部ストレージを見つけ出しました。プログラムは何にも使用されません。私はまだそれをきれいにしていません。ドライバーは、これらのメソッドを呼び出す以外には何もしません。

// ifstream ファイルを読み取り、データを両端キューに格納します。ファイルが EOF に達していないかどうかを示す bool を返します

bool readFile(ifstream &file, deque<DEQUE_TYPE> &data){
double d;
for(int i = 0; i < DEQUE_SIZE && file.good(); i++){
    file >> d;
    data.push_back(d);
}

return file.good();
}

//指定されたファイル名でファイルを開き、両端キューの内容を出力します。append が true の場合、データはファイルに追加され、それ以外の場合は上書きされます

void printFile(string fileName, deque<DEQUE_TYPE> &data, bool append){

ofstream outputFile;

if(append)
    outputFile.open(fileName, ios::app);
else
    outputFile.open(fileName);

outputFile.precision(23);   

while(data.size() > 0){
    outputFile << data.front() << endl;
    data.pop_front();
}
}

//ファイルが 1 つになるまでソートファイルをマージします

void mergeFiles(){
ifstream inFile1, inFile2;
ofstream outFile;
string fileName1, fileName2;
int i, k, max;
deque<DEQUE_TYPE> data1;
deque<DEQUE_TYPE> data2;
bool fileGood1, fileGood2;

i = 0;
k = 0;
max = 25;
while(max > 1){

    fileName1 = ""; fileName1 += "sortfile_"; fileName1 += to_string(i); fileName1 += ".txt";
    fileName2 = ""; fileName2 += "sortfile_"; fileName2 += to_string(i+1); fileName2 += ".txt";

    try{
        inFile1.open(fileName1);
        inFile2.open(fileName2);
    } catch(int e){
        cout << "Could not open the open the files!\nError " << e;
    }

    fileGood1 = true;
    fileGood2 = true;

    while(fileGood1 || fileGood2){
        fileGood1 = readFile(inFile1, data1);
        fileGood2 = readFile(inFile2, data2);

        data1 = merge(data1, data2);

        printFile("temp", data1, true);

        data1.clear();
    }

    inFile1.close();
    inFile2.close();
    remove(fileName1.c_str());
    remove(fileName2.c_str());


    fileName1 = ""; fileName1 += "sortfile_"; fileName1 += to_string(k); fileName1 += ".txt";
    rename("temp", fileName1.c_str());

    i = i + 2;
    k++;

    if(i >= max){ 
        max = max / 2 + max % 2;
        i = 0;
        k = 0;
    }
}
}

//マージ関数

deque<double> merge(deque<double> &left, deque<double> &right){
deque<double> result;

while(left.size() > 0 || right.size() > 0){
    if (left.size() > 0 && right.size() > 0){
        if (left.front() <= right.front()){
            result.push_back(left.front());
            left.pop_front();
        }
        else{
            result.push_back(right.front());
            right.pop_front();
        }
    }

    else if(left.size() > 0){
        result.push_back(left.front());
        left.pop_front();
    }
    else if(right.size() > 0){
        result.push_back(right.front());
        right.pop_front();
    }
}

return result;
}

ThePosey が提案したように、26 個の数字 (0 ～ 25) のファイルを並べ替えました。結果は次のとおりです。

-9.2559631349317831e+061 (47 lines of this)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
25
25
25
25
25

したがって、ファイルの最後の番号が複製されていることは確かですが、ランダムな大きな番号が47回発生する原因はまだわかりません。私がチェックしたところ、100,000 の数字の単語の最後の数字は、出力ファイルに 22 回ではなく 2 回しかないため、11 個の最後の数字が重複していると思います。

4

3 に答える 3

4

これが全体の問題かどうかはわかりませんが、入力ループに古典的なエラーがあります。file.good()次の読み取りが成功することを保証するものではなく、前の読み取りが成功したことを示すだけです。次のように再構築してみてください。

for(int i = 0; i < DEQUE_SIZE && (file >> d); i++){
    data.push_back(d);
}

式file >> dは への参照を返します。これは、ブール値として評価しようとするとfile呼び出されます。good

于 2013-03-02T05:39:14.507 に答える
1

数メガのメモリを使用してリスト全体を一度にRAMに読み込み、すべてを一度に並べ替えることができない理由はありますか？それはあなたのプログラムを大いに単純化するでしょう。これを課題として実行しようとしている場合は、問題を縮小して、100個のdoubleの1つのファイルのように、それを4、25個のdouble読み取りに分割することから始めます。そうすれば、非常に簡単にトレースして、追加の場所を確認できます。線はから来ています。

于 2013-03-02T03:53:10.643 に答える
1

ファイルがテキスト形式であると仮定すると、 sstd::mergeを使用して、内部マージと同様に外部マージを実行するために使用できますstd::istream_iterator。

std::ifstream in1("temp1.txt");
std::ifstream in2("temp2.txt");
std::ofstream out("output.txt");

std::merge(std::istream_iterator<double>(in1),
           std::istream_iterator<double>(),
           std::istream_iterator<double>(in2),
           std::istream_iteraror<double>(),
           std::ostream_iterator<double>(out, "\n"));
于 2013-03-02T03:56:39.800 に答える