作者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