合併過程中的文件排序

我對一個主題感興趣，假設我們有8個文件，每個文件包含10億個整數，我們應該將這些文件合併成80億個整數文件，每個文件中的所有文件都進行排序。當然，如果我們做8次合併，任務很簡單，但是我的問題是，文件的重要排序是什麼，我們應該在哪個順序上進行組合？例如，在開始時，不是合併第一個和第二個文件，創建新的M文件並與第三個文件合併，也許有時候合併第二個和第三個文件，然後與第一個文件合併會更有利嗎？我想我的問題很清楚。合併過程中的文件排序問題？如果是這樣，我們如何選擇最優的？合併過程中的文件排序

來源

2012-03-28 dato datuashvili

這可能是最佳做一個8路合併排序沒有中間文件。打開8個文件句柄，找到所有8個最小的整數，將其寫入輸出文件並讀取該文件中的下一個整數。您可能可以使用插入排序來管理8個源的8個元素的數組（持有文件句柄和讀取的最後一個值）。

就排序而言，如果您一次只能合併兩個文件，我可能會先合併最小的文件。簡化你的例子，你可以看到爲什麼。

假設您有3個文件，其中有1,2和100條記錄。
如果合併1 & 2與3所記錄的臨時文件，然後合併，與100，你已經閱讀106條記錄，並書面103
如果改爲合併1 & 100轉換成101個記錄的臨時文件，然後將其與2合併，您將讀取204條記錄並寫入103.

來源

2012-03-28 20:57:41 tomlogic

合併過程中的文件排序

回答

相關問題