如何優化合並排序？

Question

我有兩個1 GB的文件，每個文件只包含排序順序的數字。現在我知道如何讀取文件的內容並使用合併排序算法對其進行排序並將其輸出到另一個文件中，但我感興趣的是如何使用100MB緩衝區大小（我不擔心劃痕空間）。例如，一種方法是從兩個文件中讀取50 MB的塊並對其進行排序，並在排序後，我可以讀取一個新元素並繼續這個過程，直到兩個文件結束（任何人都可以給我任何想法如何實現這個）。

Answer 1

聽起來像你只需要合併你的文件中的數字，而不是排序它們，因爲它們已經在每個文件中排序。的merge sort的merge部分是這樣的：

function merge(left,right) 
    var list result 
    while length(left) > 0 or length(right) > 0 
     if length(left) > 0 and length(right) > 0 
      if first(left) ≤ first(right) 
       append first(left) to result 
       left = rest(left) 
      else 
       append first(right) to result 
       right = rest(right) 
     else if length(left) > 0 
      append left to result 
      break    
     else if length(right) > 0 
      append right to result 
      break 
    end while 
    return result 

現在，你可以從兩個文件讀取的第一個50 MB編號的兩個緩衝區，應用合併算法，那麼當已用完緩衝區（其所有分析數字），從所需文件中讀取另一個50 MB。沒有必要排序任何東西。

您只需要一個條件來檢查您的某個緩衝區是否爲空。如果是，則從緩衝區關聯的文件中讀取更多內容。

Answer 2

您可能想要以合理的塊讀/寫以避免I/O開銷。因此可能使用〜30M，input1，input2和output三個緩衝區。

繼續下去，直到任一輸入緩衝區爲空或輸出緩衝區已滿，然後讀/寫以填充/清空空/滿緩衝區。

這樣你就可以從磁盤寫入/讀取大塊數據。

除此之外，在進行排序時，您需要異步I/O來讀取/寫入數據。但這可能是矯枉過正。

Answer 3

由於您只進行合併，而不是完整的排序，它只是基本的合併循環。純粹的順序I/O。無需擔心緩衝區。在夾克上畫一個拉鍊。就這麼簡單。 （注意：如果文件中的數字是二進制格式，這可能會快很多，不僅文件會更小，而且程序將受到I/O限制，並且數字將會非常準確。）

double GetNumberFromFile(FILE file){ 
    if (feof(file)){ 
    return BIGBIGNUMBER; 
    } 
    else { 
    return ReadADouble(file); 
    } 
} 

double A = GetNumberFromFile(AFILE); 
double B = GetNumberFromFile(BFILE); 
while (A < BIGBIGNUMBER && B < BIGBIGNUMBER){ 
    if (A < B){ 
    write A; 
    A = GetNumberFromFile(AFILE); 
    } 
    else if (B < A){ 
    write B; 
    B = GetNumberFromFile(BFILE); 
    } 
    else { 
    write A; 
    write B; // or not, if you want to eliminate duplicates 
    A = GetNumberFromFile(AFILE); 
    B = GetNumberFromFile(BFILE); 
    } 
} 
while (A < BIGBIGNUMBER){ 
    write A; 
    A = GetNumberFromFile(AFILE); 
} 
while (B < BIGBIGNUMBER){ 
    write B; 
    B = GetNumberFromFile(BFILE); 
} 

---

迴應你的問題，考慮一個更簡單的問題，將一個文件複製到另一個。你只做順序I/O，這是文件系統非常擅長的。你寫一個簡單的循環來從文件中讀取像byte或int這樣的小單元，然後將它寫入另一個單元。只要你試圖讀取一個字節，系統就會分配一個漂亮的大緩衝區，將一大塊文件劃入緩衝區，然後將字節從緩衝區中送出。它會一直這樣做，直到你需要另一個緩衝區，當它無形地爲你另一個緩衝區時。您正在編寫的文件會發生同樣的事情。現在CPU非常快，所以它可以遍歷輸入字節，將它們複製到輸出中，只需要讀取或寫入緩衝區的一小部分時間，因爲讀取或寫入速度不會快於外部硬件。更大的緩衝區可以提供幫助的唯一原因是，讀/寫時間的一部分就是所謂的「延遲」，基本上是將磁頭移動到所需磁道所需的時間，並等待所需的扇區出現。大多數文件系統將文件分解爲散佈在磁盤周圍的塊，所以頭部仍在跳動。你可以聽到它。

複製和像你這樣的合併算法之間的唯一區別是它讀取兩個文件，而不是一個。無論哪種方式，基本時間序列是一系列緩衝區讀寫，散佈少量的CPU動作。 （有可能做重疊 I/O，所以CPU動作發生而的I/O發生，所以基本上有沒有緩衝區讀寫延遲，但它是一個更大的交易時， CPU的是慢1000倍。）

當然，如果你可以安排它，以便讀取和寫入的文件都是在單獨的物理磁盤驅動器和驅動器不分段多，那麼頭部運動的量能被最小化，更大的緩衝區可能會有所幫助。但基本上，通過一個簡單的程序，您幾乎可以期待簡單的代碼像磁盤可以移動數據一樣快，而巨大的緩衝區可能會有所幫助，但不是很多。

Answer 4

爲什麼不使用標準庫？

#include <fstream> 
#include <iterator> 
#include <algorithm> 

int main() 
{ 
    std::ifstream in1("in1.txt"); 
    std::ifstream in2("in2.txt"); 
    std::ofstream ut("ut.txt"); 
    std::istream_iterator<int> in1_it(in1); 
    std::istream_iterator<int> in2_it(in2); 
    std::istream_iterator<int> in_end; 
    std::ostream_iterator<int> ut_it(ut, "\n"); 

    std::merge(in1_it, in_end, in2_it, in_end, ut_it); 
} 

Answer 5

基準。按值讀取並塊讀取。感到不同！ =）