編寫使用多線程的希爾排序（shell sort）

前幾日翻看各種排序演算法時，對希爾排序印象深刻：僅僅是將數組分成多份分別排序，就比普通的插入排序快上很多，感慨之餘，想到能否用多線程的方式並行的計算希爾排序中不同的分組，如果可行，效率豈不是提升很多，於是花了些時間，寫了個多線程的實現，記錄在這裡。

原版的Shell排序，來源於《演算法（第4版）》

public class ShellSort {

public static void sort(Comparable[] a){
int key = 1;
int length = a.length;

while(key < length/3){
key = key*3 + 1;
}
while(key != 1) {
key = key/3;

for(int i = 1 ; i<=key; i++){
for(int j = i; j<length ;j=j+key){
for(int m =j ; m>=0 && m-key >= 0 && SortingTool.less(a[m], a[m-key]); m= m-key)
SortingTool.exch(a,m,m-key);
}
}
}
}

}

工具類

import java.security.SecureRandom;

public class SortingTool {

private static final SecureRandom RANDOM = new SecureRandom;

public static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}

public static void exch(Comparable[] a, int i , int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}

public static Integer geneIntArr(int size) {
Integer result = new Integer[size];
for(int i = 0; i<result.length; i++){
result[i] = RANDOM.nextInt;
}
return result;
}

public static boolean isSort(Comparable[] a){
for(int i = 0 ; i<a.length - 1 ;i++){
if(less(a[i+1], a[i]))
return false;
}
return true;
}
}

使用多線程的版本

public class ParallelShellSort {

public static void sort(Comparable[] a) {

ExecutorService service = Executors.newWorkStealingPool;
int k = 1;
int length = a.length;

while (k < length / 3) {
k = k * 3 + 1;
}
while (k != 1) {
k = k / 3;
/**
* 對於同一個k值來說，k個線程同時操作數組的不同部分，且沒有任何交集，所以不會出現讀寫不一致的問題，
* 但是對於不同的k值來說，數組的同一個位置有可能被多個線程同時操作，會出現讀寫不一致的問題，
* 例如k=333，某個線程尚未處理完成，這時如果進入下輪迭代k=111，另一個線程就可能和之前沒有完成的線程之間出現問題。
* 所以對於每個k，使用CountDownLatch，保證k個線程都操作完成之後，在進入下一輪迭代。
*/
CountDownLatch latch = new CountDownLatch(k);
for (int i = 1; i <= k; i++) {
service.submit(new ParallelShellSortRunnable(a, i, k, latch));
}
try {
latch.await;
} catch (InterruptedException e) {
System.out.println("err.." + e.getMessage);
}
}
service.shutdown;
try {
service.awaitTermination(Integer.MAX_VALUE, TimeUnit.MILLISECONDS);
} catch (InterruptedException e) {
System.out.println("error...");
}
}
}

public class ParallelShellSortRunnable implements Runnable{

private Comparable a;
private int start;
private int k;
private CountDownLatch latch;
public ParallelShellSortRunnable(Comparable[] a , int start, int k, CountDownLatch latch){
this.a = a;
this.start = start;
this.k = k;
this.latch = latch;
}
@Override
public void run {
int length = a.length;

for(int j = start; j<length ;j=j+ k){
for(int m = j; m>=0 && m- k >= 0 && SortingTool.less(a[m], a[m- k]); m= m- k)
SortingTool.exch(a,m,m- k);
}
latch.countDown;
}
}

測試和分析

在i7 8核CPU，JDK 1.8的環境上，使用Integer數組測試（bin下有個comparison.sh，運行這個腳本或者使用SortingComparison可以進行測試）。

從結果上看，多線程的的版本比原版的希爾演算法好很多，比Arrays.sort也好一些，比較意外的是，在幾十萬到幾百萬的數量級上，似乎和Arrays.parallelSort這個JDK提供的多線程版本排序方法不分伯仲，甚至有時候還能更快些，不過數量更大的時候，JDK的多線程版本就勝出不少了。

部分測試數據：

arrayParallelSort，500000數據,耗時200毫秒

arrayParallelSort，500000數據,耗時218毫秒

arrayParallelSort，500000數據,耗時213毫秒

arrayParallelSort，500000數據,耗時231毫秒

arrayParallelSort，500000數據,耗時224毫秒

arrayParallelSort，2000000數據,耗時674毫秒

arrayParallelSort，2000000數據,耗時780毫秒

arrayParallelSort，2000000數據,耗時732毫秒

arrayParallelSort，2000000數據,耗時739毫秒

arrayParallelSort，2000000數據,耗時764毫秒

parallelShell，500000數據,耗時287毫秒

parallelShell，500000數據,耗時310毫秒

parallelShell，500000數據,耗時313毫秒

parallelShell，500000數據,耗時278毫秒

parallelShell，500000數據,耗時369毫秒

parallelShell，2000000數據,耗時705毫秒

parallelShell，2000000數據,耗時663毫秒

parallelShell，2000000數據,耗時785毫秒

parallelShell，2000000數據,耗時746毫秒

parallelShell，2000000數據,耗時755毫秒

然而不用為這點成績沾沾自喜，因為更多的測試發現事情並非這麼簡單。

運行 mvn test -Dtest=TestArraysParalleSort

結果

300萬數據,耗時906毫秒

300萬數據,耗時242毫秒

300萬數據,耗時256毫秒

300萬數據,耗時236毫秒

300萬數據,耗時265毫秒

運行 mvn test -Dtest=TestParallelShell

結果

300萬數據,耗時1189毫秒

300萬數據,耗時1131毫秒

300萬數據,耗時1086毫秒

300萬數據,耗時1076毫秒

300萬數據,耗時1133毫秒

在JIT的優化下，Array.parallelSort有了近乎妖孽般的提升，而本人的代碼，似乎得不到JIT的幫助。。。

本文到這裡基本就結束了，至於如何寫出更容易被JIT優化的程序，已經超出了本人的能力範圍，JDK這種API，確實不是誰都能寫出來的。。

本文中的代碼在這裡可以找到。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！