编写使用多线程的希尔排序（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，确实不是谁都能写出来的。。

 

本文中的代码在这里可以找到。