什麼是 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 到!更加確認自己犯的最大的錯。

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


changyy 發表在 痞客邦 PIXNET 留言(0) 人氣()