0

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

该程序实际上有效，除了一些细节。输出填充将按排序顺序包含所有双打，但在文件末尾是 30 行

-9.2559631349317831e+061

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

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

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

//读取一个ifstream文件并将数据存储在一个双端队列中。返回一个布尔值，指示文件是否未达到 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 个单独的最后一个数字被重复。

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 并一次全部排序？它会大大简化你的程序。如果您尝试将此作为一项挑战，我会首先将问题缩小为 1 个包含 100 个双打的文件，将其拆分为 4、25 个双读，然后应该很容易追踪并查看额外的线来自。

于 2013-03-02T03:53:10.643 回答
1

假设您的文件是文本格式，您可以使用s.std::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 回答