查看完整版本 : 最快的Sort係邊款?

ncream 2017-11-3 04:02 PM

最快的Sort係邊款?

[align=left]根據呢個[url=https://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html]site[/url]既資料,最快的sort係radix sort。[/align]

[align=left][url=https://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html]https://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html[/url][/align]

[align=left]佢地用C++及java,對不同類型sort做了比較。發覺quick sort 唔係最quick。radix sort先至係皇者。但只限整數。[/align]

[align=left]radix sort([b]基數排序[/b])1887年已經有,係最古老排序之一。複雜度係O(k*n),效能比quick sort 好一大截。[/align]
[align=left][attach]7523688[/attach][/align]

[align=left][attach]7523689[/attach][/align]

[align=left]下次想排序,除了用鴿巢呢D有限集排序外,不妨考慮下Radix sort。:smile_o15:[/align]

[align=left]P.S. 個網有radix 及Radix兩種sort。係咁既:[/align]

[i][align=left][i]Radix.sort and Arrays.sort is implemented in Java, while std::sort, qsort and radix_sort in C++.[/i][/align]
[/i]

xianrenb 2017-11-4 10:16 AM

[quote]原帖由 [i]ncream[/i] 於 2017-11-3 04:02 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470328632&ptid=27034213][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
根據呢個site既資料,最快的sort係radix sort。

[url=https://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html]https://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html[/url]

佢地用C++及java,對不同類型sort做了比較。發覺quick sort 唔係最quick。radix so ... [/quote]

平行運算之下,又唔同講法。

可以看看:
[url=https://www.shadertoy.com/view/XlcGD8]https://www.shadertoy.com/view/XlcGD8[/url]
是一個 post shader / WebGL code 的網站。
段 code 是 bitonic sort 的 demo 。
我大概看得明五成,但都見到 Buf A 中“frame <= 136”這段。
以我的理解,即是平行同時運算 136 “步”,就可算完 256 * 256 = 65536 個數的 sorting !
應該是超快了吧?

ncream 2017-11-4 04:09 PM

[quote]原帖由 [i]xianrenb[/i] 於 2017-11-4 10:16 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470359159&ptid=27034213][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


平行運算之下,又唔同講法。

可以看看:
[url=https://www.shadertoy.com/view/XlcGD8]https://www.shadertoy.com/view/XlcGD8[/url]
是一個 post shader / WebGL code 的網站。
段 code 是 bitonic sort 的 demo 。
我大概看得明五成,但都見到 Buf A 中“ ... [/quote]

多謝師兄分享。:smile_o12:

Quick sort。radix sort 等等其實好難實現平行運算。bitonic sort的確提供非常優良的多機解決方案。:smile_o06:

sswroom 2017-11-4 10:33 PM

[quote]原帖由 [i]ncream[/i] 於 2017-11-4 04:09 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470372953&ptid=27034213][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]


多謝師兄分享。:smile_o12:

Quick sort。radix sort 等等其實好難實現平行運算。bitonic sort的確提供非常優良的多機解決方案。:smile_o06: [/quote]Quick Sort可以平行運算....... Radix Sort未用過, 不肯定能不能平行運算

ncream 2017-11-4 10:45 PM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-4 10:33 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470388779&ptid=27034213][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
Quick Sort可以平行運算....... Radix Sort未用過, 不肯定能不能平行運算 [/quote]

Ching, 多謝指點。

我諗緊quick sort點運作。佢sort完之後分左右兩set。跟住每次都分到左右。我地要唔要建立array去記低每set要sort 範圍呢?

[[i] 本帖最後由 ncream 於 2017-11-4 10:46 PM 編輯 [/i]]

煙民母親生賤種 2017-11-5 04:50 AM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-4 10:33 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470388779&ptid=27034213][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
Quick Sort可以平行運算....... Radix Sort未用過, 不肯定能不能平行運算 [/quote]應該唔係, 因為 gpu frameworks , 太多使用 radixsort / mergesort。反而 radixsort 係幾款 lib 的 sorting algorithm 主力。:fst_008:

ncream 2017-11-5 08:29 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-11-5 04:50 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470398344&ptid=27034213][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
應該唔係, 因為 gpu frameworks , 太多使用 radixsort / mergesort。反而 radixsort 係幾款 lib 的 sorting algorithm 主力。:fst_008: [/quote]

我google睇左幾十個radix sort 既code。radix sort好多時做平行運算。所以若果ching 你用GPU run quick sort,反而會比GPU Library 慢。

另外radix sort 都有in place。但只能逐個bit做。變相慢8倍兼同quicksort無分別。因為都係靠swap。

Radix sort 所謂in place都要開一個做index既array。多數10個。深到係n(data)。即係要sort既總數。

不過我睇晒幾十個自稱快過quick sort既code。都寫得好差。我好懷疑質素咁差既code是否可以快過quick sort。可能佢地用來對照既quick sort code 重差都未定。

[[i] 本帖最後由 ncream 於 2017-11-5 08:31 AM 編輯 [/i]]

Susan﹏汪汪 2017-11-5 11:25 AM

[quote]原帖由 [i]ncream[/i] 於 2017-11-5 08:29 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=470400282&ptid=27034213][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


我google睇左幾十個radix sort 既code。radix sort好多時做平行運算。所以若果ching 你用GPU run quick sort,反而會比GPU Library 慢。

另外radix sort 都有in place。但只能逐個bit做。變相慢8倍兼同quicks ... [/quote]
你睇果D係咪類似學術論文

好多都係強調大O複雜度之下嘅比較
並唔會真係做足晒optimize 黎對比

好多時就咁比較大O並唔代表真實係速度快幾多
因為大O只係講同一個算法係不同的sample size下的速度比

本來兩個不同算法的大O其實係未必能夠做對比
分分鐘有時候O(n^2)跑出來的速度會快過O(n log n)

Susan﹏汪汪 2017-11-5 11:28 AM

[quote]原帖由 [i]xianrenb[/i] 於 2017-11-4 10:16 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=470359159&ptid=27034213][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]


平行運算之下,又唔同講法。

可以看看:
https://www.shadertoy.com/view/XlcGD8
是一個 post shader / WebGL code 的網站。
段 code 是 bitonic sort 的 demo 。
我大概看得明五成,但都見到 Buf A 中“ ... [/quote]
bitonic sort汪汪睇過下

佢個butterfly network有D似Cooley–Tukey

比起quick sort
bitonic sort完全係針對平衡化設計、所有線路都固定好
GPU處理呢個方便過quick sort好多

反而quick sort汪汪一向都覺得好難用GPU去寫
data之間的依賴性太高

[[i] 本帖最後由 Susan﹏汪汪 於 2017-11-5 11:33 AM 編輯 [/i]]

ncream 2017-11-5 11:58 AM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-5 11:25 AM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=470406004&ptid=27034213][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

你睇果D係咪類似學術論文

好多都係強調大O複雜度之下嘅比較
並唔會真係做足晒optimize 黎對比

好多時就咁比較大O並唔代表真實係速度快幾多
因為大O只係講同一個算法係不同的sample size下的速度比

本來兩個 ... [/quote]

學術論文反而有d比較好。咩教學網站先寫得差。

不過總體都係不可用。

有時間寫返過睇下幾快先。
頁: [1]
查看完整版本: 最快的Sort係邊款?