我是如何擊敗Java自帶排序算法的
Java 8 對(duì)自帶的排序算法進(jìn)行了很好的優(yōu)化。對(duì)于整形和其他的基本類型， Arrays.sort() 綜合利用了雙樞軸快速排序、歸并排序和啟發(fā)式插入排序。這個(gè)算法是很強(qiáng)大的，可以在很多情況下通用。針對(duì)大規(guī)模的數(shù)組還支持更多變種。我拿自己倉(cāng)促寫(xiě)的排 序算法跟Java自帶的算法進(jìn)行了對(duì)比，看看能不能一較高下。這些實(shí)驗(yàn)包含了對(duì)特殊情況的處理。
首先，我編寫(xiě)了一個(gè)經(jīng)典的快速排序算法。這個(gè)算法通過(guò)計(jì)算樣本的平均值來(lái)估計(jì)整個(gè)數(shù)組的中心點(diǎn)，然后用作初始樞軸。
我借鑒了一些Java的思路來(lái)適當(dāng)改進(jìn)我的快速排序，修改后的算法在對(duì)小數(shù)組進(jìn)行排序的時(shí)候直接調(diào)用了插入排序。在這種情況下，我的排序算法和Java的排序算法可以達(dá)到相同的運(yùn)行時(shí)間量級(jí)。Wild & al 指出，如果排序數(shù)組有很多的重復(fù)數(shù)據(jù)，標(biāo)準(zhǔn)的快速排序會(huì)比雙樞軸的快速排序要快。我沒(méi)有嘗試任何字節(jié)或匯編級(jí)別的分析和優(yōu)化。在大部分的問(wèn)題中，我的版本的優(yōu)化程序都遠(yuǎn)遠(yuǎn)不能跟Java系統(tǒng)程序相提并論。
我一直都想測(cè)試腦海里的一個(gè)簡(jiǎn)單的排序算法，我稱之為Bleedsort。這是一個(gè)分布式算法，它通過(guò)樣本抽樣方法對(duì)要排序的數(shù)組進(jìn)行分布估計(jì)，根 據(jù)估計(jì)結(jié)果把數(shù)據(jù)分配到相應(yīng)的一個(gè)臨時(shí)的數(shù)組里（如圖 1 所示），并重寫(xiě)這個(gè)初始的數(shù)組。這是一個(gè)預(yù)處理過(guò)程，然后再應(yīng)用其他的排序算法分別進(jìn)行排序。在我的測(cè)試中，我使用了我編寫(xiě)的快速排序版本。如果使用合并 排序應(yīng)該會(huì)有更好的結(jié)果，因?yàn)楹喜⑴判虮粡V泛應(yīng)用在高度結(jié)構(gòu)化的數(shù)組中。為了計(jì)算簡(jiǎn)單，我只測(cè)試了分布均勻的數(shù)據(jù)。
Bleedsort在遇到相同的數(shù)據(jù)的時(shí)候都會(huì)放到右邊，所以此算法在排序相對(duì)一致（譯者注：會(huì)有很多重復(fù)數(shù)據(jù)）的數(shù)組的時(shí)候表現(xiàn)很差。所以我需要對(duì)排序的數(shù)組進(jìn)行樣本估計(jì)，當(dāng)重復(fù)數(shù)很多的情況下應(yīng)避免使用Bleedsort算法。
我很清楚，Bleedsort算法在內(nèi)存空間使用方面沒(méi)辦法跟歸并排序（快速排序）相提并論，臨時(shí)數(shù)組也比原來(lái)的數(shù)組要大四倍左右。同時(shí)其他的一些分布排序算法，比如Flashsort，在這方面也表現(xiàn)得要好很多。
圖1 Bleedsort舉例說(shuō)明
我運(yùn)用JMH來(lái)作為測(cè)試基準(zhǔn)。 為了簡(jiǎn)單起見(jiàn)，我就用整形數(shù)組進(jìn)行測(cè)試。在1000.000 到10.000.0000 數(shù)量級(jí)的均勻分布的數(shù)組中，我的算法表現(xiàn)的最好。盡管我寫(xiě)的快速排序算法在一定程度上比不過(guò)Java自帶的算法，但是我的預(yù)處理過(guò)程很好的彌補(bǔ)了這些不足 （調(diào)用了我的快速排序的Bleedsort 87ms vs Java 自帶算法105ms; 938ms vs 1.144s）
Benchmark Mode Cnt Score Error Units Corrected
MyBenchmark._1e6U sample 8512 0.024 ± 0.001 s/op
MyBenchmark._1e7U sample 985 0.236 ± 0.001 s/op
我生成了下面這些正確的基準(zhǔn)數(shù)組
MyBench.int1e6UQuickSort sample 1641 0.131 ± 0.001 s/op 0.107 ± 0.002
MyBench.int1e6UBleedSort sample 2410 0.087 ± 0.001 s/op 0.063 ± 0.002
MyBench.int1e6UJavaSort sample 1978 0.105 ± 0.001 s/op 0.081 ± 0.002
MyBench.int1e7UQuickSort sample 200 1.483 ± 0.014 s/op 1.459 ± 0.015
MyBench.int1e7UBleedSort sample 373 0.938 ± 0.009 s/op 0.914 ± 0.010
MyBench.int1e7UJavaSort sample 200 1.144 ± 0.009 s/op 1.120 ± 0.010
所以，我的這個(gè)沒(méi)有特殊優(yōu)化的算法程序在這些數(shù)據(jù)集上要比Java自帶算法快大概 10-15% 。
在1000.000數(shù)據(jù)級(jí)，包含 10% 或者 1% 的隨機(jī)重復(fù)數(shù)據(jù)的均勻增加數(shù)據(jù)集上，我的算法表現(xiàn)的也不差。
Benchmark Mode Cnt Score Error Units Corrected
._1e6Iwf010 sample 20705 9.701 ± 0.033 ms/op
._1e6Iwf001 sample 148693 1.344 ± 0.003 ms/op
生成正確的基準(zhǔn)數(shù)組
.int1e6Iw010BleedSort sample 4159 49.377 ± 0.571 ms/op 39.68 ± 0.60
.int1e6Iw010JavaSort sample 3937 52.139 ± 0.229 ms/op 42.44 ± 0.25
.int1e6Iw010QuickSort sample 3899 52.457 ± 0.210 ms/op 42.76 ± 0.23
10% 重復(fù)數(shù)據(jù)
.int1e6Iw001BleedSort sample 6190 32.821 ± 0.219 ms/op 31.48 ± 0.22
.int1e6Iw001JavaSort sample 8113 24.910 ± 0.079 ms/op 23.57 ± 0.08
.int1e6Iw001QuickSort sample 8653 23.367 ± 0.056 ms/op 22.02 ± 0.06
^^ 1%
但是，這個(gè)算法在只有10.000左右的小二項(xiàng)分布的數(shù)據(jù)集 （~bin(100,0.5)）（譯者加：考慮到括號(hào)里面是公式代碼，并沒(méi)有修改內(nèi)部英文括號(hào)符號(hào)成中文符號(hào)）上表現(xiàn)的很差。 在這些數(shù)組中，平均下來(lái)，出現(xiàn)50這個(gè)數(shù)字的次數(shù)是795.5，而出現(xiàn)40組重復(fù)數(shù)組的次數(shù)是108.4。
同時(shí)，在排序1000.0000量級(jí)的大數(shù)組的時(shí)候，這個(gè)算法要比 Arrays.sort() 慢兩倍左右。這些數(shù)組都有很多的重復(fù)數(shù)據(jù)（比如有的大小為1e6的數(shù)組里只有450個(gè)不同的數(shù)值）。
Benchmark Mode Cnt Score Error Units Corrected
._1e4bin100 sample 152004 1.316 ± 0.001 ms/op
^^ for correction
.int1e4bin100BleedSort sample 148681 1.345 ± 0.001 ms/op 0.029 ± 0.002
.int1e4bin100JavaSort sample 150864 1.326 ± 0.001 ms/op 0.010 ± 0.002
.int1e4bin100QuickSort sample 146852 1.362 ± 0.001 ms/op 0.046 ± 0.002
.int1e6bin1e4BleedSort sample 75344 2.654 ± 0.005 ms/op -
.int1e6bin1e4JavaSort sample 146801 1.361 ± 0.002 ms/op -
.int1e6bin1e4QuickSort sample 76467 2.615 ± 0.005 ms/op -
在排序小型的（10.000, 100.000）均勻隨機(jī)數(shù)組下，這個(gè)算法表現(xiàn)尚可，但是并不比系統(tǒng)算法更好。
MyBench.int1e4UBleedSort sample 216492 0.924 ± 0.001 ms/op 0.683 ± 0.002
MyBench.int1e4UJavaSort sample 253489 0.789 ± 0.001 ms/op 0.548 ± 0.002
MyBench.int1e4UQuickSort sample 217394 0.920 ± 0.001 ms/op 0.679 ± 0.002
MyBench.int1e5UBleedSort sample 18752 0.011 ± 0.001 s/op 0.009 ± 0.002
MyBench.int1e5UJavaSort sample 22335 0.009 ± 0.001 s/op 0.007 ± 0.002
MyBench.int1e5UQuickSort sample 18748 0.011 ± 0.001 s/op 0.009 ± 0.002
總而言之，在內(nèi)存不是很緊張的情況下，針對(duì)適當(dāng)?shù)拇髷?shù)據(jù)集，我會(huì)建議把分布搜索算法做為一個(gè)有效的補(bǔ)充選項(xiàng)。
最后，讓大家來(lái)認(rèn)識(shí)一下二項(xiàng)分布的一些數(shù)據(jù)集 bin(100, 0.5) 和 bin(1000, 0.5)，
這里是兩個(gè)隨機(jī)抽樣了100個(gè)數(shù)據(jù)的數(shù)據(jù)集（使用R語(yǔ)言生成）。
> rbinom(100, 100, 0.5)
[1] 43 49 51 47 49 59 40 46 46 51 50 49 49 45 50 51 50 49 53 52 45 53 48 56 45
[26] 47 55 47 53 53 56 41 47 42 51 51 46 49 49 52 46 48 49 50 48 56 54 49 53 52
[51] 54 48 45 45 50 48 54 49 52 50 48 48 49 45 54 54 50 41 53 45 51 48 53 52 52
[76] 50 53 47 55 47 60 54 52 56 45 46 54 46 38 43 53 45 62 48 52 52 52 49 52 56
> rbinom(100, 1000, 0.5)
[1] 515 481 523 519 524 516 498 473 523 514 483 496 458 506 507 491 514 489
[19] 475 489 485 507 486 523 521 492 502 500 503 501 504 482 518 506 498 525
[37] 498 491 492 479 506 499 505 497 510 479 504 510 485 488 495 519 522 490
[55] 517 511 511 488 519 508 475 521 505 493 480 498 490 492 492 476 490 506
[73] 496 505 521 518 506 509 477 483 509 493 497 501 483 502 470 515 519 509
[91] 510 496 477 508 506 481 490 511 498 476
