c++ - 在 C++ 中使用合并排序算法合并文件

Question

我编写了一个程序来对包含 100,000 个 double 值的文件执行外部归并排序。我无法快速找到 C++ 的外部存储库，因为谷歌搜索只会导致一堆关于 extern 关键字的页面，所以我决定自己写一个，我认为这就是问题所在。

除了几个细节之外，该程序确实有效。输出填充将按排序顺序排列所有 double ，但在文件末尾是 30 行

-9.2559631349317831e+061

不在输入文件中。我在输出文件和输入文件中还有 21 个值，这还不算我刚才提到的单个数字的 30 行。

程序是如何运行的，它一次读取 100,000 个 double ~4000 行并对它们进行排序，然后将它们存储到 26 个文本文件中，然后将这 26 个文件合并为 13 个文件，将 13 个合并为 7 个，依此类推。 .. 直到只有一个文件。

如果代码真的很丑，我很抱歉，我通过铅笔、纸、试验和错误自己弄清楚了所有外部存储的东西。该程序不会用于任何用途。我还没有清理它。除了调用这些方法之外，驱动程序不会做太多事情。

//读取 ifstream 文件并将数据存储在双端队列中。返回一个 bool 值，指示文件是否未达到 EOF

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 为真，数据将被追加到文件中，否则将被覆盖

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();
}
}

//合并排序文件直到剩下一个文件

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 次，所以我想我有 11 个单独的最后一个数字被复制了。

Answer 1

我不知道这是否是全部问题，但您的输入循环中有一个经典错误。 file.good() 不保证下一次读取会成功，它只是告诉您上一次读取成功了。尝试像这样重组它:

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

表达式 file >> d 返回对 file 的引用，当您尝试将其评估为 bool 值时，它会调用 good。