Re: [問題] 請問已經有很多radix sort這類O(N)的排 …
看板Prob_Solve (計算數學 Problem Solving)作者poga (波卡)時間16年前 (2008/10/07 18:36)推噓1(1推 0噓 4→)留言5則, 2人參與討論串2/3 (看更多)
※ 引述《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)
推
10/08 22:19, , 1F
10/08 22:19, 1F
→
10/08 22:20, , 2F
10/08 22:20, 2F
→
10/08 22:21, , 3F
10/08 22:21, 3F
→
10/09 23:15, , 4F
10/09 23:15, 4F
→
10/09 23:16, , 5F
10/09 23:16, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
