分而治之Fork/Join

在多核处理器时代，

使用

public class ForkJoinPoolMain {
    public static void main(String[] args) {
        var forkJoinPool = new ForkJoinPool();
        var sumTask = new SumTask(0, 100000000);
        forkJoinPool.submit(sumTask);
        
        System.out.println(sumTask.join());
    }
}

class SumTask extends RecursiveTask<Long> {
    private final static int TASK_THRESHOLD = 10000;
    private final int start;
    private final int end;

    public SumTask(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    protected Long compute() {
        if (end - start < TASK_THRESHOLD) {
            return LongStream.range(start, end).sum();
        } else {
            int middle = start + (end - start) / 2;
            var sumTask1 = new SumTask(start, middle);
            var sumTask2 = new SumTask(middle, end);

            return sumTask1.fork().join() + sumTask2.fork().join();
        }
    }
}

分析

FAQ

总结

• Fork/Join是一种基于分治的算法：通过分解任务，并行执行，最后合并结果得到最终结果
• ForkJoinPool线程池可以把一个大任务分拆成小任务并行执行，任务类必须继承自RecursiveTask(有返回值)或RecursiveAction(无返回值)
• 使用Fork/Join模式可以进行并行计算以提高效率

参考