Re: [問題] 請問已經有很多radix sort這類O(N)的排 …

[poga (波卡)]

※ 引述《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)
推 worldxxi:原來是這樣啊，我了了，其實我是想到CountingSort之後，
→ worldxxi:後才發現有radixsort，所以對於有人說不好，有點小不服氣
→ worldxxi:看來知識和才能都要在加油才行，謝謝所有推文和回文的大
→ irix2007:我曾用 c 的 qsort 和 radix sort 來比較, radix sort
→ irix2007:的確比較快. 不管在linux上用gcc 或windows 用vc