演算法 - 合併若干有序檔案
摘要：
極客時間 - 資料結構與演算法之美 - 12 | 排序（下）
問題描述：現在你有 10 個介面訪問日誌檔案，每個日誌檔案大小約 300MB，每個檔案裡的日誌都是按照時間戳從小到大排序的。你希望將這 10 個較小的日誌檔案，合併為 1 個日誌檔案，合併...
問題描述：現在你有 10 個介面訪問日誌檔案，每個日誌檔案大小約 300MB，每個檔案裡的日誌都是按照時間戳從小到大排序的。你希望將這 10 個較小的日誌檔案，合併為 1 個日誌檔案，合併之後的日誌仍然按照時間戳從小到大排列。如果處理上述排序任務的機器記憶體只有 1GB，你有什麼好的解決思路，能“快速”地將這 10 個日誌檔案合併嗎？
思路：其實就是歸併排序的裡的歸併步驟，只不過從歸併兩個陣列變成了歸併多個數組。PS. 看這類問題的時候一定仔細看看空間限制條件，不要被嚇到也不要隨意做判斷。
程式碼：
public class MergeSortedFiles {
public static void merge(List<FileIterator> fileIteratorList) {
FileWriter fileWriter = null;
// 記錄還沒有遍歷結束的檔案
List<FileIterator> notEndingFileIterators = new ArrayList<>(fileIteratorList);
while (!notEndingFileIterators.isEmpty()) {
FileIterator min = getMin(notEndingFileIterators);
fileWriter.writeLine(min.getLine());
if (!min.nextLine()) {
// 該檔案已經遍歷到尾了，將其移除
notEndingFileIterators.remove(min);
}
}
}
private static FileIterator getMin(List<FileIterator> notEndingFileIterators) {
FileIterator min = null;
for (FileIterator fi : notEndingFileIterators) {
if (min == null) {
min = fi;
continue;
}
if (fi.getLine().compareTo(min.getLine()) < 0) {
min = fi;
}
}
return min;
}
}
/**
* 這裡不做實現，只表達意思
*/
interface FileIterator {
/**
* 返回當前行
*
* @return
*/
String getLine();
/**
* 前進到下一行
*
* @return 如果已經是最後一行了，返回false。否則返回true。
*/
boolean nextLine();
}
/**
* 這裡不做實現，只表達意思
*/
interface FileWriter {
/**
* 寫一行到檔案中
*
* @param line
*/
void writeLine(String line);
}
演算法複雜度分析：
- 不存在最好最壞情況，因為遍歷次數是固定的。
-
總行數n、檔案數k、每個檔案行數m，如果資料特徵正好能夠達成每次把一個檔案遍歷完再遍歷其餘都，那麼遍歷次數是
m*k + m*(k-1) + m*(k-2) + ... + m*1 = m*(k*(k+1)/2)，把m=n/k代入得到，n(k+1)/2，為O(n)。