原文地址：https://mp.weixin.qq.com/s/Ru-WW-KjRIloD54tApcEgw

前言

我们上小学的时候经常会遇到老师问这样的问题，就是1＋2＋……＋99＋100＝?许多年前，有个叫高斯的小朋友也遇到了这个问题并很快得出了结果，今天我们利用java的分支、合并框架来计算下，原理和高斯小朋友的类似。

一、分支/合并框架简介

分支/合并框(Fork/Join)是Java7提供的一个用于并行执行任务的框架，是一个把大任务分割成若干个小任务，最终汇总每个小任务结果后得到大任务结果的框架。它使用工作窃取（work-stealing）算法，主要用于实现“分而治之”。

二、分支/合并流程图

用一张图展示下分支、合并流程：

 

三、涉及的Java类

JDK里面与fork/join相关的主要类如下：

  1. ForkJoinPool

充当fork/join框架里面的管理者，最原始的任务都要交给它才能处理。它负责控制整个fork/join有多少个workerThread，workerThread的创建，激活都是由它来掌控。它还负责workQueue队列的创建和分配，每当创建一个workerThread，它负责分配相应的workQueue。然后它把接到的活都交给workerThread去处理，它可以说是整个frok/join的容器。

  1. ForkJoinTask

代表fork/join里面任务类型，一般用它的两个子类RecursiveTask、RecursiveAction。这两个区别在于RecursiveTask任务是有返回值，RecursiveAction没有返回值。任务的处理逻辑包括任务的切分都集中在compute()方法里面。

fork/join主要类图：

 

 

 

四、代码实战

用代码实现下1到100自然数的求和。

伪代码如下：

if(任务足够小或不可分){
顺序计算该任务
}else{
将任务分成两个子任务
递归调用本方法，拆分每个子任务，等待所有子任务完成
合并每个子任务的结果
}

完整代码如下：

/**
*@Author:Java碎碎念
*/
publicclassCountTaskextendsRecursiveTask<Integer>{

//阀值
privatestaticfinalintTHRESHOLD=2;
privateintstart;
privateintend;

publicCountTask(intstart,intend){
this.start=start;
this.end=end;
}

@Override
protectedIntegercompute(){
intsum=0;
//判断是否是拆分完毕
intlenth=end-start;
if(lenth<=THRESHOLD){
//如果拆分完毕就相加
for(inti=start;i<=end;i++){
sum+=i;
}
}else{
//没有拆分完毕就开始拆分
intmiddle=(start+end)/2;
CountTaskleftTask=newCountTask(start,middle);
CountTaskrightTask=newCountTask(middle+1,end);
//执行子任务
invokeAll(leftTask,rightTask);
//等待子任务执行完，并得到其结果
IntegerrightResult=rightTask.join();
IntegerleftResult=leftTask.join();
//合并子任务
sum=leftResult+rightResult;
}
returnsum;
}

publicstaticvoidmain(String[]args)throwsExecutionException,InterruptedException{
ForkJoinPoolforkJoinPool=newForkJoinPool();
CountTaskcountTask=newCountTask(1,100);
ForkJoinTask<Integer>forkJoinTask=forkJoinPool.submit(countTask);
System.out.println(forkJoinTask.get());
}
}

运行完成后会打印出结果：5050；

五、注意事项

  1. 对一个任务调用join方***阻塞调用方，直到该任务运行完成。因此，需要在两个子任务的计算都开始之后再调用它。否则，使用该框架计算会比原始的顺序算法更慢更复杂，因为每个子任务都必须等待另一个子任务完成才能启动。
  2. ForkJoin是通过多线程的方式进行处理任务，因此当数据量不是特别大的时候，没有必要使用ForkJoin。因为多线程会涉及到上下文的切换，当数据量不大的时候使用串行会比使用多线程快。
  3. 执行子任务时候要注意，使用invokeAll，不能分别对子任务调用fork。 
//正确代码
invokeAll(leftTask,rightTask);
//错误代码
subtask1.fork();
subtask2.fork();

java中的分支合并框架介绍完成了，有问题欢迎留言沟通哦！