Doug Lea教授写了一个并行处理的框架,最近偶然看见他的论文。拜读了一下感觉很好。这个框架佳作Fork/Join框架,顾名思义就是先进行fork再join组合结果的意思。下面是这篇论文的地址,英文好的同志可以好好看一下:http://gee.cs.oswego.edu/dl/papers/fj.pdf
如果觉得英文论文有点难懂,我按照我自己的理解写在下面帮助大家理解一下:
首先,关于Fork/Join的大篇幅的介绍就不在这里写了,大家可以百度了解一下。我主要介绍一下用法。
分治的思想在我们计算机圈是很有名的,分治分治,分而治之。这个Fork/Join有点并行分治的意思。
要想使用这个框架必须继承RecursiveTask<T>或者RecursiveAction<T>,我从两个例子解释一下这两个的不同。
问题1:高斯定理可以很快的计算等差序列的加法,我们就用Fork/Join框架实现一下等差序列的加法:
package com.wjy.enumstudy; import java.util.concurrent.ExecutionException; import java.util.concurrent.ForkJoinPool; import java.util.concurrent.Future; import java.util.concurrent.RecursiveTask; public class PlusPlus extends RecursiveTask<Integer>{ private static final int THRESHOLE=100; private int start; private int end; public PlusPlus(int start,int end){ this.start=start; this.end=end; } @Override protected Integer compute() { // TODO Auto-generated method stub int sum=0; if(end-start<THRESHOLE){ for(int i=start;i<=end;i++){ sum+=i; } }else{ int middle=(start+end)/2; PlusPlus left=new PlusPlus(start, middle); PlusPlus right=new PlusPlus(middle+1, end); left.fork(); right.fork(); sum=left.join()+right.join(); } return sum; } public static void main(String args[]) throws InterruptedException, ExecutionException{ ForkJoinPool pool=new ForkJoinPool(); Future<Integer> result=pool.submit(new PlusPlus(1, 10000)); System.out.println(result.get()); System.err.println(10001*5000); } }
算法很简单,在100个数以内的我们直接迭代计算和值。否则采用Fork/Join框架分治计算。
注:System.err.println(10001*5000);是高斯定理计算的答案。做对比用。
运行结果:
50005000
50005000
通过上面的例子可以看出来RecursiveTask是有返回值的。而RecursiveAction是没有的,比如说排序就不需要有返回值。所以第二个例子就是排序,使用RecursiveAction。
问题2:给数组排序:
package com.wjy.enumstudy; import java.util.Arrays; import java.util.concurrent.ExecutionException; import java.util.concurrent.ForkJoinPool; import java.util.concurrent.Future; import java.util.concurrent.RecursiveAction; import java.util.concurrent.RecursiveTask; import java.util.concurrent.TimeUnit; public class SortSort extends RecursiveAction{ private static final int THRESHOLE=10; private int[] array; private int start; private int end; public SortSort(int[] array,int start,int end){ this.array=array; this.start=start; this.end=end; } private void sampleSort(int[] array,int start,int end){ Arrays.sort(array, start, end+1); //看这里toIndex是end+1!!! } private void swap(int[] array,int numA,int numB){ array[numA]=array[numA]+array[numB]; array[numB]=array[numA]-array[numB]; array[numA]=array[numA]-array[numB]; } /** * 像快排一样每次保证最后一个数处在最终的正确位置上 * 比他小的在他左边,比他大的在他右边 * @param array * @param start * @param end * @return */ private int partion(int[] array,int start,int end){ int small=start; int count=0; int value=array[end]; int length=end-start+1; for(int i=start;i<end;i++){ if(array[i]<value){ if(i!=small) { swap(array, i, small); } small++; count++; } } if((start+count)!=end){ swap(array, start+count, end); } return start+count; } @Override protected void compute() { // TODO Auto-generated method stub if(end-start<THRESHOLE){ sampleSort(array,start,end); }else{ int tag=partion(array,start,end); new SortSort(array, start, tag-1).fork(); new SortSort(array, tag+1, end).fork(); } } public static void main(String args[]) throws InterruptedException, ExecutionException{ int array[]={3,7,2,1,5,4,3,8,9,4,6}; ForkJoinPool pool=new ForkJoinPool(); pool.submit(new SortSort(array,0,array.length-1)); pool.shutdown(); pool.awaitTermination(1000, TimeUnit.SECONDS); System.out.println(Arrays.toString(array)); } }
运行结果:
[1, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9]
对于Arrays.sort(array,fromIndex,toIndex);这个函数,其中的toIndex要给的比预想的大一。举个例子:
对于int[] array={3,2,1};
要是Arrays.sort(array,0,2);的话运行结果是{2,3,1}。
所以必须是Arrays.sort(array,0,3);
相关推荐
Fork/Join框架Package jsr166y是Java 7并行编程类的的初步版本(Preliminary versions of classes targeted for Java 7.)
fork/join框架是ExecutorService接口的一个实现,可以帮助开发人员充分利用多核处理器的优势,编写出并行执行的程序,提高应用程序的性能;设计的目的是为了处理那些可以被递归拆分的任务。 fork/join框架与...
java Fork Join框架及使用,java自带的多线程框架,来处理多线程的问题
Fork/Join框架是Java7中新增的一项特性,也是Java7平台的其中一项主要改进。下面我们就来简单探讨下Java的Fork/Join框架
Fork/Join框架的测试demo,含源代码。 Fork/Join框架是Java7提供了的一个用于并行执行任务的框架, 是一个把大任务分割成若干个小任务,最终汇总每个小任务结果后得到大任务结果的框架。 我们再通过Fork和Join这两个...
全网第一篇通过图文介绍Fork/Join框架与CompleteableFuture的PPT
fork join 框架 生产使用实例,可以直接修改配置,实现业务。
fork/join框架是ExecutorService接口的一个实现,可以帮助开发人员充分利用多核处理器的优势,编写出并行执行的程序,提高应用程序的性能;设计的目的是为了处理那些可以被递归拆分的任务。
Java提供Fork/Join框架用于并行执行任务,核心的思想就是将一个大任务切分成多个小任务,然后汇总每个小任务的执行结果得到这个大任务的最终结果。 这种机制策略在分布式数据库中非常常见,数据分布在不同的数据库的...
一、 Fork/Join框架的介绍 21 1、实现步骤: 22 2、工作窃取算法 22 3、分而治之 23 4、Fork/Join使用的标准范式 24 5、Fork/Join框架的异常处理 26 6、Fork/Join框架的实现原理 26 二、闭锁CountDownLatch 28 1、...
主要介绍了浅谈Java Fork/Join并行框架,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
主要介绍了Java ForkJoin框架的原理及用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
Java Fork-Join 论文 排序
全书分为9章,涵盖了线程管理、线程同步、线程执行器、Fork/Join框架、并发集合、定制并发类、测试并发应用等内容。全书通过60多个简单而非常有效的实例,帮助读者快速掌握Java 7多线程应用程序的开发技术。学习完...
与ExecutorService其他实现不同,Fork / Join框架使用工作窃取算法( ),该算法可最大程度地利用线程,并提供了一种更简单的方式来处理产生其他任务的任务(称为子任务)。 以下列出的所有代码都可以在以下位置...
Java并发Fork-Join框架原理
● 分割迭代器、fork/join框架与异常 ● 使用微基准测试检查流的性能 ● 使用默认方法演化API 目录 第1章 走进新生代的Java 1 第2章 Java lambda表达式的基础知识 23 第3章 流与管道介绍 55 第4章 终止流:收集...
算法中的并行使用java的Fork / Join框架实现,他会将进程使用ForkJoinPool进行管理,并自动分配到空闲的CPU核心上来运算。由于个人PC的CPU核心数量较少,所以预期至多能产生常数倍的加速 效果。 本次实验使用的实验...
聊聊并发系列文章 1. 聊聊并发(一)深入分析Volatile的实现原理 2. 聊聊并发(二)Java SE1.6中...8. 聊聊并发(八)Fork/Join框架介绍 9. 聊聊并发(九)Java中的CopyOnWrite容器 10. 聊聊并发(十)生产者消费者模式
介绍了ForkJoin并发框架,供有java基础者学习,工作配合使用,附件带有PPT,介绍并发与并行区别,和ForkJoin代码范例,资源来自网络,分享分享!