瞎忙的 External Sorting 經驗

什麼是 External Sorting 呢？一般寫程式會用到的 Sorting 不免是 Quick Sort、Merge Sort、Heap Sort 等，除了自己使用外，連同各大學出的作業，多是 Internal Sorting 。

簡單地說，就是把資料都紀錄在記憶體中，然後進行 sorting 的方式，都叫作 Internal Sorting 。至於什麼是 External Sorting 呢？就是當所有資料量大到全部無法同時擺在記憶體中，這時又想 sorting 時，就會用到的處理，便是 External Sorting 。

至於怎樣實作，很簡單，三個概念：

1. 取部分資料進記憶體中


2. 將記憶體中的資料進行排序，把結果輸出至檔案


3. 不斷地進行 1~ 2 直到資料全部弄完。最後，將上述產生的多筆排序好的資料，進行合併的處理

假設現在有 1000 萬筆資料，且記憶體容量一次僅能處理 100 萬筆的排序工作，那就會分 10 次做排序，每次從原始資料拿出 100 萬筆出來，將之排序好後，輸出至檔案。經過上述的部分，最後會產生 10 個檔案，其各個檔案就是子部分已排序好的資料，最後，將這 10 個檔案內的資料進行合併。合併的方式，最簡單的是每次取兩個檔案，依序把資料排序與輸出。經由上述的步驟，直到檔案只剩一個。最後的檔案，就會是 1000 萬筆已排序好的資料。

這邊會用到的技巧就是使用 heap tree 。當然，效率上的追求，更可以 10 個檔案一起合併囉。這邊就是常說的 k-way merge 的技巧，也不難。

原先預定用 C 語言，三天解決它。結果前三天都在偷懶，每天大概寫 2~3 小時，結果最後開始要 merge 時，犯了一個錯！最後多花了三天進行 debug 。我犯的錯就是忘了簡單化以及過急著最佳化。這三天寫了三個版本，因為寫得過程中發現速度很慢，然後處於存在 bug 的情況下進行架構的調整，使得各個單元皆可能存在 bug ，導致 debug 時間成指數成長。彷彿從大學至今，還沒有 debug 這麼久的！最後直到最後一天，我才完成了一個沒有錯誤的版本，真的很累。

至於效能上，依週遭同學的實作經驗，基本上 sort 部分跟 merge 時間差不多才是好的結果，當然，可不行都很慢！當初，我的 merge 時間已經是 sort 時間得幾十倍，然而，我開始質疑自己的架構不夠快，因此重構，儘管重構兩次，結果仍一樣。直到最後一天所有的 bug 都解決後，洗澡時我才想到，原來我真正慢的地方是切資料的動作。後來，同學以 VS2008 的工具觀察，的確有百分之六十以上的時間會花在切資料，完全跟我想的 match 到！更加確認自己犯的最大的錯。

這次實作經驗，反而沒有替自己掙些自信，倒是重重地在自己的腳上砸了個大石頭，真痛！經過此次經驗，順道消消自己銳氣。過去還滿自信自己工作的實作效率以及成果效率的，但這一步退後又看得更遠，收穫也挺不少的。未來啊，又得回歸個人工作囉，時間得擺放在最重要的事物上了！