Google+ Followers

2009年3月20日 星期五

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


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


沒有留言:

張貼留言