【Java高级】利用fork-join框架归并排序来比较性能

本文为原创文章，转载请注明出处
查看[Java]系列内容请点击：https://www.jianshu.com/nb/45938443

fork-join框架会使用空闲线程来抢占当前线程的任务，具体实现原理这里就不说了，有兴趣的同学也可以自己实现一个。这里使用该框架进行归并排序，并对比普通的归并排序的效率：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class Test {
    private static final ForkJoinPool pool = new ForkJoinPool(4); // N 核心处理器

    private static int[] merge; // 合并用

    public static void main(String[] args) {
        int len = 1000000; // 100万个数字排序
        int sortTimes = 200; // 排序次数
        merge = new int[len];

        // 正常排序
        long t1 = System.currentTimeMillis();
        for (int t = 0; t < sortTimes; t++) {
            normalSort(prepareData(len));
        }
        long t2 = System.currentTimeMillis();
        System.out.println("正常排序共耗时：" + (t2 - t1) / 1000.0 + " 秒");

        // 多线程排序
        t1 = System.currentTimeMillis();
        for (int t = 0; t < sortTimes; t++) {
            multiThreadSort(prepareData(len));
        }
        t2 = System.currentTimeMillis();
        System.out.println("多线程排序共耗时：" + (t2 - t1) / 1000.0 + " 秒");
    }

    private static int[] prepareData(int len) {
        Random random = new Random(System.currentTimeMillis());
        int[] a = new int[len];
        for (int i = 0; i < len; i++) a[i] = random.nextInt(10000);
        return a;
    }

    // 普通排序
    private static long normalSort(int[] a) {
        long t1 = System.currentTimeMillis();
        normalSort(a, 0, a.length - 1);
        long t2 = System.currentTimeMillis();

        // 检查是否排序成功
        for (int i = 1; i < a.length; i++) {
            if (a[i] < a[i - 1]) System.out.println("error sort 2");
        }
        return t2 - t1;
    }

    private static void normalSort(int[] a, int start, int end) {
        if (end <= start) return;
        if (end - start == 1 && a[end] < a[start]) {
            int k = a[end];
            a[end] = a[start];
            a[start] = k;
            return;
        }

        int middle = (start + end) / 2;
        normalSort(a, start, middle);
        normalSort(a, middle + 1, end);

        // 合并
        merge(a, start, end, middle);
    }

    // 多线程排序
    private static long multiThreadSort(int[] a) {
        SortTask task = new SortTask(a, 0, a.length - 1);
        long t1 = System.currentTimeMillis();
        pool.invoke(task);
        long t2 = System.currentTimeMillis();

        // 检查是否排序成功
        for (int i = 1; i < a.length; i++) {
            if (a[i] < a[i - 1]) System.out.println("error sort 1");
        }

        return t2 - t1;
    }

    /**
     * fork-join 框架实现归并排序
     * 这里是分割
     */
    private static class SortTask extends RecursiveTask<int[]> {
        private int[] val;
        private int start;
        private int end;
        private int middle;

        public SortTask(int[] a, int start, int end) {
            val = a;
            this.start = start;
            this.end = end;

            middle = (start + end) / 2;

            if (merge == null) merge = new int[a.length];
        }

        @Override
        protected int[] compute() {
            List<SortTask> moreActions = getMoreActions();
            if (moreActions != null && moreActions.size() > 0) {
                // 执行所有子线程
                for (SortTask t : moreActions) t.fork();

                // 等待所有子线程完成
                for (SortTask t : moreActions) t.join();

                // 合并
                merge(val, start, end, middle);
            } else {
                if (end - start == 1 && val[start] > val[end]) swap(start, end);
            }
            return val;
        }

        // 获取需要分割的其他桶任务
        private List<SortTask> getMoreActions() {
            if (end - start <= 1) return null;

            List<SortTask> moreActions = new ArrayList<>();
            moreActions.add(new SortTask(val, start, middle));
            moreActions.add(new SortTask(val, middle + 1, end));
            return moreActions;
        }

        private void swap(int i, int j) {
            int a = val[i];
            val[i] = val[j];
            val[j] = a;
        }
    }


    // 合并，二分
    private static void merge(int[] val, int start, int end, int middle) {
        int p1 = start;
        int p2 = middle + 1;
        int p = start;
        while (p1 <= middle || p2 <= end) {
            if (p1 > middle) merge[p++] = val[p2++];
            else if (p2 > end) merge[p++] = val[p1++];
            else if (val[p1] > val[p2]) merge[p++] = val[p2++];
            else merge[p++] = val[p1++];
        }

        for (int i = start; i <= end; i++) val[i] = merge[i];
    }
}

我们分别进行100万个数字排序，对各个算法都进行200次排序，可以看到，输出结果：

正常排序共耗时：35.43 秒
多线程排序共耗时：23.898 秒

多线程的排序时间是明显少于单线程的。

但是如果我们把排序次数改为5次：

正常排序共耗时：1.616 秒
多线程排序共耗时：2.905 秒

可以看到，在少量作业的情况下，多线程会带来一些额外的开销，比如线程创建等。