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