moea_joint_essay
105年
[統計資訊] 資料庫及資料探勘、程式設計
第 六 題
處理巨量資料時，分析人員常需面對龐大資料，且資料量遠大於記憶體容量。今有一循序檔 data.txt，內含 9 筆資料如下，欲對該檔進行排序。惟受限於記憶體容量，讀入 data.txt 資料時，每次最多只能 6 筆。在考量磁碟處理速度遠低於記憶體情況下，請以敘述表示法，設計一可兼顧減少磁碟存取次數及提高排序效率之排序演算法。（11 分）
data.txt
6000 | 800000 | 500 | 2 | 40 | 9000000 | 3 | 1.5 | 70000
data.txt
6000 | 800000 | 500 | 2 | 40 | 9000000 | 3 | 1.5 | 70000
📝 此題為申論題
思路引導 VIP
題目要求處理大於記憶體容量的資料排序，也就是「外部排序」(External Sorting)。由於記憶體只能容納6筆，總資料有9筆，可採用 2-Way (或多路) 外部合併排序演算法 (External Merge Sort)。分為 Run 生成與 Merge 兩個階段敘述。
🤖
AI 詳解
AI 專屬家教
本題情境適用「外部排序法 (External Sorting)」，尤其是「外部合併排序 (External Merge Sort)」。演算法設計重點在於將資料分段讀入記憶體做內部排序以形成排序段 (Run)，再透過緩衝區分配合併這些 Run，以達到最小化磁碟存取次數的目標。 詳細演算法步驟敘述如下： 【階段一：生成初始排序段 (Run Generation)】
▼ 還有更多解析內容