如何进行JDK7新特性中fork/join框架的原理分析(fork,jdk7,join,编程语言)

原理解析：fork分解，join结合。这个框架的本质是将一个任务分解成多个子任务，每个子任务用单独的线程去处理。这里用到了递归的思想。框架的结构图可以参考

使用fork/join 框架很简单，

1.实现子问题的一般求解算法

2.如何分解问题

3.继承 RecursiveAction ，实现compute()方法

伪代码代码

Resultsolve(Problemproblem){if(problemissmall)directlysolveproblemelse{splitproblemintoindependentpartsforknewsubtaskstosolveeachpartjoinallsubtaskscomposeresultfromsubresults}

这里我通过一个改进的二分查找来讲解fork/join的使用。(后面才发现，选用这个案例是非常失败的，因为二分查找的时间是logn,而创建线程的开销更大，这样并不能体现多线程二分查找的优势，所以这个代码不具有实用性，只是为了说明如何使用框架：)

代码如下：

BinarySearchProblem.java

Java代码

packagetestjdk7;importjava.util.Arrays;/***@authorkencs@foxmail.com*/publicclassBinarySearchProblem{privatefinalint[]numbers;privatefinalintstart;privatefinalintend;publicfinalintsize;publicBinarySearchProblem(int[]numbers,intstart,intend){this.numbers=numbers;this.start=start;this.end=end;this.size=end-start;}publicintsearchSequentially(intnumberToSearch){//偷懒，不自己写二分查找了returnArrays.binarySearch(numbers,start,end,numberToSearch);}publicBinarySearchProblemsubProblem(intsubStart,intsubEnd){returnnewBinarySearchProblem(numbers,start+subStart,start+subEnd);}}

BiSearchWithForkJoin.java

Java代码

packagetestjdk7;importjava.util.concurrent.ForkJoinPool;importjava.util.concurrent.RecursiveAction;/***@authorkencs@foxmail.com*/publicclassBiSearchWithForkJoinextendsRecursiveAction{privatefinalintthreshold;privatefinalBinarySearchProblemproblem;publicintresult;privatefinalintnumberToSearch;publicBiSearchWithForkJoin(BinarySearchProblemproblem,intthreshold,intnumberToSearch){this.problem=problem;this.threshold=threshold;this.numberToSearch=numberToSearch;}@Overrideprotectedvoidcompute(){if(problem.size<threshold){//小于阀值，就直接用普通的二分查找result=problem.searchSequentially(numberToSearch);}else{//分解子任务intmidPoint=problem.size/2;BiSearchWithForkJoinleft=newBiSearchWithForkJoin(problem.subProblem(0,midPoint),threshold,numberToSearch);BiSearchWithForkJoinright=newBiSearchWithForkJoin(problem.subProblem(midPoint+1,problem.size),threshold,numberToSearch);invokeAll(left,right);result=Math.max(left.result,right.result);}}//构造数据privatestaticfinalint[]data=newint[1000_0000];static{for(inti=0;i<1000_0000;i++){data[i]=i;}}publicstaticvoidmain(String[]args){BinarySearchProblemproblem=newBinarySearchProblem(data,0,data.length);intthreshold=100;intnThreads=10;//查找100_0000所在的下标BiSearchWithForkJoinbswfj=newBiSearchWithForkJoin(problem,threshold,100_0000);ForkJoinPoolfjPool=newForkJoinPool(nThreads);fjPool.invoke(bswfj);System.out.printf("Resultis:%d%n",bswfj.result);}}

RecursiveTask 还可以带返回值，这里给出一段代码作为参考(斐波那契函数)

(来自http://www.ibm.com/developerworks/cn/java/j-lo-forkjoin/index.html)

Java代码

classFibonacciextendsRecursiveTask{finalintn;Fibonacci(intn){this.n=n;}privateintcompute(intsmall){finalint[]results={1,1,2,3,5,8,13,21,34,55,89};returnresults[small];}publicIntegercompute(){if(n<=10){returncompute(n);}Fibonaccif1=newFibonacci(n-1);Fibonaccif2=newFibonacci(n-2);System.out.println("forknewthreadfor"+(n-1));f1.fork();System.out.println("forknewthreadfor"+(n-2));f2.fork();returnf1.join()+f2.join();}}

用途

只要问题能够分解成类似子问题的，都可以使用这个框架。对于大批量的数据尤其合适。