作者poga (波卡)
看板Prob_Solve
標題Re: [問題] 請問已經有很多radix sort這類O(N)的排 …
時間Tue Oct 7 18:36:13 2008
※ 引述《worldxxi (風)》之銘言：
: 有人能花個時間指導我一下嗎？我很疑惑，
: 問題是這樣的，現在的硬體空間都很大，而radix sort只要稍微改一下就可以
: 排小數和整數，為何還需要其他O(n)＝n（log n）的排序方式，而且有人說實際
: 上很少人用radix sort，為甚麼啊？
其實演算法的效能除了數學上的複雜度之外，還要考慮真實電腦架構的問題
像現在的電腦一定有cache的機制，有學過OS/計組的話就知道
cache hit跟cache miss的效能可能差了幾百萬倍
（以下資料都是從白算盤上抄來的，三版p.508）
如果光看instruction數的話，n一大，radix sort的確比quicksort來的少
可是看clock cycle的話，radix sort卻一直沒辦法壓的比quicksort低，為甚麼呢？
這個問題只要觀察cache miss的數量就可以發現
隨著n的增長，radixsort遇到的cache miss數量也爆增
帶來的penalty就蓋過了複雜度上的優勢
至於為甚麼quicksort比較能善用cache
我想是因為整個quicksort很大一部份的計算都是對pivot做比較，
自然cache可以一直生效。
而radixsort就沒有明顯的可以cache住的部份，自然效能比較低
這是我從書上看來的理解... 有錯請指正 <(_ _)>
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.170.66.233
※ 編輯: poga 來自: 118.170.66.233 (10/07 18:37)
1F：推 worldxxi:原來是這樣啊，我了了，其實我是想到CountingSort之後， 10/08 22:19
2F：→ worldxxi:後才發現有radixsort，所以對於有人說不好，有點小不服氣 10/08 22:20
3F：→ worldxxi:看來知識和才能都要在加油才行，謝謝所有推文和回文的大 10/08 22:21
4F：→ irix2007:我曾用 c 的 qsort 和 radix sort 來比較, radix sort 10/09 23:15
5F：→ irix2007:的確比較快. 不管在linux上用gcc 或windows 用vc 10/09 23:16