Discussion:
請問為什麼quick sort最快?
(时间太久无法回复)
眠月..
2005-03-31 23:57:29 UTC
Permalink
merging sort不是可以到 O(nlogn)嗎?
雖然快速排序法平均可以到O(nlogn)
而quick sort 有一個worst case 會使的時間複雜度變成 O(n^2)
所以快速排序法是最快的嗎?
好像有點奇怪..
請高手解惑..thanks
資料調動次數最少(平均來說)
--
To iterate is human, to recurse is divine. 
遞迴只應天上有, 凡人該當用迴圈.   L. Peter Deutsch
--
夫兵者不祥之器物或惡之故有道者不處君子居則貴左用兵則貴右兵者不祥之器非君子
之器不得已BBS telnet://bbs.wretch.cc 開個人板 超快 不用連署不可得志於天下
矣吉事尚左凶事尚右偏將軍居左上將軍居右言以喪禮處之殺人之眾以哀悲泣之戰勝以
喪禮處之道常無名樸雖小天下莫能臣侯王若能守之萬物將自賓天地相合以降甘露民莫
之令而自均始制有名名亦既有夫亦將知止知止 218-168-41-39.dynamic.hinet.net海
網路黑貓
2005-04-01 03:29:28 UTC
Permalink
去問你的DS教授
回這樣很鳥嗎?
資料結構多久前的事了
複習中 上來問問吧!
問這問題也蠻鳥嗎?
那是書本上有的, 很基本的東西了
看到就 動手回回吧!
--
※ Origin: SayYA 資訊站 <bbs.sayya.org> 
◆ From: palm217.nchc.org.tw
米菇小呆復活
2005-04-01 14:57:17 UTC
Permalink
是有書上說過 quick sort 在實際應用上是最快的,
但是其實也不盡然,
就我所知有一個台大學生跟教授吵過他發現 heap sort 最快,
不過他教授說那是在程式技巧上偷吃步不算數...
如果真的懷疑可以直接寫來跑跑看,
不過 input 的量最好各種都測過比較準,
理想上最好是有實際應用上的 input 可以用...
根據黃子嘉老師(離散數學名師)的說法
是因為常數 c 比較小的緣故....
--
信心失生。
人信心源生。

--
>> 台灣科大資工系 清流站 # ntust.org #
>> Author from: sw169-200-133.adsl.seed.net.tw 
一山還有一山低
2005-04-01 18:31:39 UTC
Permalink
是有書上說過 quick sort 在實際應用上是最快的,
但是其實也不盡然,
就我所知有一個台大學生跟教授吵過他發現 heap sort 最快,
不過他教授說那是在程式技巧上偷吃步不算數...
粉好奇這個heap sort是怎麼寫的?
有源碼可以列出來看看嗎? ;)
--
※ Origin: SayYA 資訊站 <bbs.sayya.org> 
◆ From: 218-164-172-23.dynamic.hinet.net
阿虎
2005-04-02 00:45:56 UTC
Permalink
Post by 一山還有一山低
是有書上說過 quick sort 在實際應用上是最快的,
但是其實也不盡然,
就我所知有一個台大學生跟教授吵過他發現 heap sort 最快,
不過他教授說那是在程式技巧上偷吃步不算數...
粉好奇這個heap sort是怎麼寫的?
有源碼可以列出來看看嗎? ;)
應該是比較 <= 或著 >= 改成 < or > 吧
也就是等於時不swap

你去看一些 原始碼, heap等於時也在交換 ,不只是heap啦
蠻多排序明明不是stable ,等於也在交換,現實中有必要嗎?
麵包小男孩
2005-04-02 06:58:36 UTC
Permalink
※ 引述《***@bbs.csie.ncu.edu.tw (rtyu)》之銘言:
: merging sort不是可以到 O(nlogn)嗎?
: 雖然快速排序法平均可以到O(nlogn)
: 而quick sort 有一個worst case 會使的時間複雜度變成 O(n^2)
: 所以快速排序法是最快的嗎?
: 好像有點奇怪..
: 請高手解惑..thanks

Quick Sort不一定最快

要看Case..

一般在Worse Case的情況下可能會產生

T(n)=T(n-1)+Cn (C,n為一常數) 的情況 也就是O(n^2)

這種情況可能發生在可能原本要Sorting的串列原本就以經排序好了的情況

--

我記得是這樣~~XD

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.170.53.165
我來也....
2005-04-02 16:00:36 UTC
Permalink
Post by 麵包小男孩
: merging sort不是可以到 O(nlogn)嗎?
: 雖然快速排序法平均可以到O(nlogn)
: 而quick sort 有一個worst case 會使的時間複雜度變成 O(n^2)
: 所以快速排序法是最快的嗎?
: 好像有點奇怪..
: 請高手解惑..thanks
Quick Sort不一定最快
要看Case..
一般在Worse Case的情況下可能會產生
T(n)=T(n-1)+Cn (C,n為一常數) 的情況 也就是O(n^2)
這種情況可能發生在可能原本要Sorting的串列原本就以經排序好了的情況
補充一下~~~~~

所謂worst case是指data反序的時候

ex:
小==>大,這次我們要的結果

所謂反序就是,大==>小
--
※ Origin: 陽‧光‧椰‧林 <alway.twbbs.org> 
◆ From: 59-113-183-207.dynamic.hinet.net(59.113.183.207)
劉育信(Liu Yu Hsin)
2005-04-02 21:05:49 UTC
Permalink
merging sort不是可以到 O(nlogn)嗎?
雖然快速排序法平均可以到O(nlogn)
而quick sort 有一個worst case 會使的時間複雜度變成 O(n^2)
所以快速排序法是最快的嗎?
好像有點奇怪..
請高手解惑..thanks
從理論上來說quick sort的worst case是n^2
quick sort只是一個名字而已

一個優秀的程式設計師,除了要會演算法和資料結構外,更要懂得硬體

這樣寫出來的程式才會好

每個sorting algorithm都有他的特性,了解他,懂得運用他,才是最重要的


了解演算法和資料結構,你就會發現quick sort對於大部分的case來說
能夠在搬動較少次數下完成排序動作,
所以雖然worst case是n^2
但是average case是nlogn


另外在n很小的時候,insertion sort是最快的

quicksort有三種寫法:
iterative Quicksort
recursive Quicksort
sophisticated Quicksort

如果排序的資料很多,記憶體不夠放,要放在second storage
像硬碟或是磁帶等等
那麼sorting algorithm也不能只看bigO

譬如早期使用磁帶的時候,就要用bubble sort

結論:其實你是對的,也不用覺得奇怪
從理論上來看,quick sort不是最快的,
但實際上來說,排序的資料並不會多到超過好幾億筆
,而且要碰到worst case的機會也不太
所以quick sort在實用上還是很快的
--
※ Origin: 楓橋驛站<bbs.cs.nthu.edu.tw> ◆ From: g924388.HSIN-A.ab.nthu.edu.tw
God bless BBS friends
2005-04-03 08:11:25 UTC
Permalink
regards:

請教一下,所謂的"硬體"是指?....

Any positive suggestion is welcome.
thank you
May goodness be with you all


--
※ Origin: 楓橋驛站<bbs.cs.nthu.edu.tw> ◆ From: 140.138.19.29
I SHALL RETURN!
2005-04-03 01:20:13 UTC
Permalink
※ 引述《***@bbs.cs.nthu.edu.tw (God bless BBS friends)》之銘言:
: regards:
: 請教一下,所謂的"硬體"是指?....
storage devices

--
  ▆ ▆▆▆▆ ▆ ▆ ▆ ▆▆▆▆
  ▆█▆▆ █▆▆█ █ █ █ █ █  ┌─【EXIT七號出口】─┐
▄▄▄▄▄█ ▆▆▆▆ ▆ █ ▆ █ █▄▄▄▄▄  telnet://exit.twbbs.org
▄▄▄▄▄█ █ ◢▆▆▆ █ █ █ █ █▄▄▄▄▄     你還在尋找出口嗎?
█▆◤ ▆▆▆◤ █ █ ◤ █▆▆◤  └──────────┘
◆ From: 61.229.35.34
劉育信(Liu Yu Hsin)
2005-04-03 10:47:28 UTC
Permalink
Post by I SHALL RETURN!
: 請教一下,所謂的"硬體"是指?....
storage devices
不只是storage devices

這裡硬體的定義是很廣的
CPU,cache,memory,I/O,......
還包括了computer architecture

簡言之就是程式是在哪個平台上跑

你除了要了解演算法和資料結構外,更要了解程式執行平台的特性

像分散式和平行式的電腦是未來的趨勢

現在一顆有HT的intel cpu應該也不貴~~~
--
※ Origin: 楓橋驛站<bbs.cs.nthu.edu.tw> ◆ From: g924388.HSIN-A.ab.nthu.edu.tw
小白
2005-04-06 05:41:08 UTC
Permalink
Post by 劉育信(Liu Yu Hsin)
Post by I SHALL RETURN!
storage devices
不只是storage devices
這裡硬體的定義是很廣的
CPU,cache,memory,I/O,......
還包括了computer architecture
簡言之就是程式是在哪個平台上跑
你除了要了解演算法和資料結構外,更要了解程式執行平台的特性
像分散式和平行式的電腦是未來的趨勢
現在一顆有HT的intel cpu應該也不貴~~~
不是設計和硬体相關的程式也要瞭解硬体?
不用吧?
compiler都幫你最佳化了
你只要focus在演算法上就好了
亂槍打鳥反而什麼都沒打到

判斷奇偶,我看過有人寫num & 01h
會比 num%2 快到哪裡去嗎?

高階程式用高階的表示法才不失一致性
用太多奇怪的東西反而失去可讀性
--
※ Origin: Yahoo!奇摩 大摩域 <telnet://bbs.kimo.com.tw> 
◆ From: 218-164-172-23.dynamic.hinet.net
2005-04-06 11:38:57 UTC
Permalink
Post by 小白
不是設計和硬体相關的程式也要瞭解硬体?
不用吧?
要,因為現在不只是在寫 PC 的程式,
在非 PC 的環境下某些 C 的寫法還是要考慮到硬體。
Post by 小白
compiler都幫你最佳化了
你只要focus在演算法上就好了
還沒有這麼理想。
Post by 小白
亂槍打鳥反而什麼都沒打到
判斷奇偶,我看過有人寫num & 01h
會比 num%2 快到哪裡去嗎?
還是差了好幾條 assembly code,
用 gcc -O2 -S 試出來的,
版本是 3.4.2。
Post by 小白
高階程式用高階的表示法才不失一致性
如果是 C 的話其實低階一點的寫法還是能讓程式快一點,
理想的情況下最好是使用者還能把意圖寫清楚幫助編譯器進行最佳化,
編譯器要做最佳化,還是需要使用者多加給予一些提示,
這些例子屢見不鮮,
像是 gcc 的 attribute,
很多編譯器都會有的 fastcall(自動幫參數標 register 修飾字),
1999 年剛進 ISO C 的 const、inline、restrict,
還有怕編譯器做過頭,叫編譯器不要做 caching,
早在 1989 年就進 ANSI C 的 volatile,
很多地方都顯示現代的 compiler 並沒有我們想的那麼聰明,
所以我是建議還是別太果斷,
多做一點實驗來驗證自己的想法比較好...

附帶一提,
目前編譯器比較難的問題還是在 pointer analysis,
因為只要出現 pointer access 的地方編譯器就得很保守的做評估,
比較爛一點的編譯器通常看到用 pointer 做間接存取就假設它會破壞所有變數了,
後面的變數再次使用都通通要從 stack 重新 load 出來,
不能直接把之前 cache 在 register 的值拿出來續用,
先進一點的編譯器會有一些理論 model 可以減少這些狀況,
不過還是有限,
ISO C99 加進去的 restrict 修飾字主要也是解決 alias analysis 的問題,
但這都是要靠使用者跟 library 設計者主動去寫出來。

--
Name: Tseng, Ling-hua E-mail Address: ***@it.muds.net
School: National Chung Cheng University
Department: Computer Science and Information Engineering
Researching: Porting GCC and Implementing VLIW instruction scheduler in GCC
Homepage: https://it.muds.net/~uranus
--
╔═══╗ ┼────────────────────────╮
║狂狷 ║ │* Origin:[ 狂 狷 年 少 ] whshs.cs.nccu.edu.tw ╰─╮
║ 年少║ ┼╮ < IP:140.119.164.16 > ╰─╮
╚╦═╦╝  ╰  * From:218-171-140-189.dynamic.hinet.net 
 ─╨─╨─ KGBBS ─ ◎ 遨翔"BBS"的狂狷不馴;屬於年少的輕狂色彩 ◎ 
劉育信(Liu Yu Hsin)
2005-04-07 05:30:38 UTC
Permalink
Post by 小白
Post by 劉育信(Liu Yu Hsin)
不只是storage devices
這裡硬體的定義是很廣的
CPU,cache,memory,I/O,......
還包括了computer architecture
簡言之就是程式是在哪個平台上跑
你除了要了解演算法和資料結構外,更要了解程式執行平台的特性
像分散式和平行式的電腦是未來的趨勢
現在一顆有HT的intel cpu應該也不貴~~~
不是設計和硬体相關的程式也要瞭解硬体?
不用吧?
compiler都幫你最佳化了
你只要focus在演算法上就好了
亂槍打鳥反而什麼都沒打到
判斷奇偶,我看過有人寫num & 01h
會比 num%2 快到哪裡去嗎?
高階程式用高階的表示法才不失一致性
用太多奇怪的東西反而失去可讀性
我寫一個程式
for i:=1 to 10000 do
for j:=1 to 10000 do
print(array[i,j]);

for j:=1 to 10000 do
for i:=1 to 10000 do
print(array[i,j]);

那如果你考慮cache memory virtual memory三者的關係
你就會發現Locality的重要性

如果array的資料大小介於cache和memory之間

和如果array的資料大小介於memory和virtual memory之間
那這兩個程式在速度上可能就有差了

其實Locality也是一般程式設計師常忽略的~~~~
比較沒經驗的程式設計師常會以為是演算法不夠好

所以了解一些硬體的特性還是很重要的~~~~
--
※ Origin: 楓橋驛站<bbs.cs.nthu.edu.tw> ◆ From: g924388.HSIN-A.ab.nthu.edu.tw
小白
2005-04-07 09:19:10 UTC
Permalink
Post by 劉育信(Liu Yu Hsin)
Post by 小白
不是設計和硬体相關的程式也要瞭解硬体?
不用吧?
compiler都幫你最佳化了
你只要focus在演算法上就好了
亂槍打鳥反而什麼都沒打到
判斷奇偶,我看過有人寫num & 01h
會比 num%2 快到哪裡去嗎?
高階程式用高階的表示法才不失一致性
用太多奇怪的東西反而失去可讀性
我寫一個程式
for i:=1 to 10000 do
for j:=1 to 10000 do
print(array[i,j]);

for j:=1 to 10000 do
for i:=1 to 10000 do
print(array[i,j]);
那如果你考慮cache memory virtual memory三者的關係
你就會發現Locality的重要性
記得locality好像只是說明一個現像?
程式不故意亂寫,還真難違返locality
Post by 劉育信(Liu Yu Hsin)
如果array的資料大小介於cache和memory之間
和如果array的資料大小介於memory和virtual memory之間
那這兩個程式在速度上可能就有差了
其實Locality也是一般程式設計師常忽略的~~~~
比較沒經驗的程式設計師常會以為是演算法不夠好
所以了解一些硬體的特性還是很重要的~~~~
array大小超過cache還不是一樣有locality ?
你要講的cache miss? 還是寫程式時不要讓array大過cache?
還是什麼之類的?

我看過有關於程設的書好像沒有一本教你說寫程式要如何遵守locality?
事實上好像是不故意違返的話就算尊守了?
看看上面的第二個loop,也好像沒人是這麼用的
故意設計來違返locality?
--
※ Origin: Yahoo!奇摩 大摩域 <telnet://bbs.kimo.com.tw> 
◆ From: 218-164-169-66.dynamic.hinet.net
飯可亂吃話不能亂說
2005-04-07 15:14:08 UTC
Permalink
Post by 小白
我看過有關於程設的書好像沒有一本教你說寫程式要如何遵守locality?
我有看過一本書 Code Optimization: Effective Memory Usage
裡面講很多Pipeline,Cache Locality,Virtual Memory的使用最佳化方式

--
╭ From: cherry.cs.nccu.edu.tw ◎──────────╮
└──◎  Origin:政大資科˙貓空行館  bbs.cs.nccu.edu.tw ┘
Loading...