在C++中使用mergesort算法合併文件

Question

我編寫了一個程序，對100,000個雙打文件執行外部合併。我無法快速找到用於C++的外部存儲庫，因爲使用googling只會導致一堆關於extern關鍵字的頁面，所以我決定只寫自己的，我認爲這就是問題所在。

該方案實際工作，除了一對夫婦的細節。輸出填充將所有的排序順序雙打，但在文件的結尾是

-9.2559631349317831e+061 

這是不是在輸入文件30行。我在輸出文件和輸入文件中還有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(); 
} 

//打開與指定的文件名的文件和打印雙端隊列的內容吧。如果追加爲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(); 
} 
} 

//合併的sortfiles直到有一個文件留下

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

我整理26號（0 - 25）的文件，如ThePosey建議，和這裏的結果：

-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，當你嘗試將其評價爲布爾這就要求good。

Answer 2

是不是有一個原因，你不能使用一些內存大小一次讀入RAM並整理所有內容？它會大大簡化你的程序。如果你試圖把這個作爲一個挑戰，我會開始縮小問題的範圍，比如說100個雙打的文件，把它分成4個，25個雙讀段，然後應該很容易追蹤並看到附加的位置線來自。

Answer 3

假設您的文件是文本格式，您可以使用std::merge通過使用std::istream_iterator s來完成與內部合併一樣的外部合併。

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"));