Re: [問題] 關於 qsort
※ 引述《ccpz (....)》之銘言：
: 先恭喜一下開版 :)
: 一般來說呼叫函數時不會慢一些
: 所以在C/C++ 中才會有蠻多人在用 #define/inline 宣告函數
: 不過 qsort 函數會不斷呼叫使用者傳入的 compare function
: 這樣不會讓效率比較差嗎?
: 還是說函數內部都是以位元在處理,所以可以彌補一些
: 呼叫函數時的 delay?
不是這樣的，而是較好的演算法本身所能產生的效益，已經不小了，
所以適當好用的 framework, 反而比較重要。
以 qsort() 而言，一般比較會多做注意的地方，則是每一個紀錄的
大小，如果太大了，有時就會另外建立 indirect reference, 全用
指標或註標值代替，以節省記憶體搬移的時間。
若是對效能的需求很高，其實也很少有人去重寫一個專用的 qsort,
而是儘量減少即時的排序需求，儘量預先排序完成，例如使用其他
資料結構，使資料一直保持已排序的狀態。
純以技術面而言，則可另外寫一個採用 __fastcall 的比較函數的
qsort(), 也會有一些幫助。
效能的追求是相當精細複雜的事情，可以做的事情其實非常多，而
即使是演算法本身，也還可以再加強。
qsort() 採用的就是號稱最快的 quicksort, 然而這個最快，僅是
單一演算法的最快，還有合併多種演算法，特別是在小區間範圍做
加強的 fast quicksort, 實作上可以比單純的 quicksort 還快。
而即使是 quicksort 本身，也還有非遞迴法的做法，用些許空間
換取更高的效能。此外中間值的取法，也有取陣列的左中右三值，
將它們排序再取中間值，而不單取某一個值的做法。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.222.173.26
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
-2
11
