ForkJoin模式优化大型递归任务

拿快排举例

传统的快排

    private static void quickSort(int begin, int end) {
        if (begin < end) {
            int mid = partition(begin, end);
            quickSort(begin, mid - 1);
            quickSort(mid + 1, end);
        }
    }

    private static int partition(int p, int q) {
        int i = p - 1;
        int pivot = arr[q];
        for (int j = p; j < q; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i+1, q);
        return i + 1;
    }
    private static void swap(int[] arr, int a, int b) {
        if (arr[a] == arr[b]) {
            return;
        }
        arr[a] = arr[a] ^ arr[b];
        arr[b] = arr[a] ^ arr[b];
        arr[a] = arr[a] ^ arr[b];
    }

构造个长度为一千万的随机数组, 测试排序所用时间

    private static final int[] arr = new int[10000000];
    static {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100000);
        }
    }
		public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        quickSort(0, arr.length - 1);
        System.out.println(System.currentTimeMillis() - t1);
    }

多次测试, 时间分别为:

818
Process finished with exit code 0
808
Process finished with exit code 0
792
Process finished with exit code 0
789
Process finished with exit code 0
790
Process finished with exit code 0

使用 ForkJoinTask

public class ForkJoinPoolTest extends RecursiveAction {

    private final int start;
    private final int end;
    public ForkJoinPoolTest(int start, int end) {
        this.start = start;
        this.end = end;
    }
  
    @Override
    protected void compute() {
        if (start < end) {
            int mid = partition(start, end);
            ForkJoinPoolTest left = new ForkJoinPoolTest(start, mid - 1);
            ForkJoinPoolTest right = new ForkJoinPoolTest(mid + 1, end);
            left.fork();
            right.fork();
            left.join();
            right.join();
        }
    }
  
    private static int partition(int p, int q) {
        int i = p - 1;
        int pivot = arr[q];
        for (int j = p; j < q; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i+1, q);
        return i + 1;
    }
    private static void swap(int[] arr, int a, int b) {
        if (arr[a] == arr[b]) {
            return;
        }
        arr[a] = arr[a] ^ arr[b];
        arr[b] = arr[a] ^ arr[b];
        arr[a] = arr[a] ^ arr[b];
    }
}

同样构造一个长度为一千万的随机数组, 测试排序时间:

    private static final int[] arr = new int[10000000];
    static {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 10000000);
        }
    }

    public static void main(String[] args) {
        ForkJoinPool pool = ForkJoinPool.commonPool();
      
        long t1 = System.currentTimeMillis();
        pool.invoke(new ForkJoinPoolTest(0, arr.length - 1));
        System.out.println(System.currentTimeMillis() - t1);

        pool.shutdown();
    }

多次测试, 时间分别为:

577
Process finished with exit code 0
476
Process finished with exit code 0
629
Process finished with exit code 0
579
Process finished with exit code 0
552
Process finished with exit code 0