优化分治解决方案:Fork/Join框架

92 阅读 0 评论 61 点赞

我是靠谱客的博主紧张哑铃，最近开发中收集的这篇文章主要介绍优化分治解决方案:Fork/Join框架，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

设计目的

该框架设计目的是针对那些可以使用分治设计范式来解决的问题,实现最优的并发解决方案
本章将介绍以下主题

Fork/Join框架简介
第一个例子: k-means聚类算法
第二个例子:数据筛选算法
第三个例子: 归并排序算法

Fork框架简介

执行器是在Java5中引入的,它提供了一种执行并发任务的机制,而无需创建,启动和结束线程.该框架采用了一个线程池,该线程池可以执行你发送给执行器的任务,并且针对多个任务重用这些线程.这种机制为程序设计人员提供了一下便利

并发程序编程更加简单,无需担心线程的创建
控制执行器和应用程序所使用的资源更加简单.你可以创建一个仅使用预定数目线程的执行器.如果发送较多的任务,则执行器会将他们先存放金一个队列中,直到线程可用为止.
执行器通过重用线程缩短了创建线程所引入的开销.从内部来讲,他管理一个线程池,重用线程来执行多个任务.
分治算法是一种十分流行的设计方法.为了采用这种方法解决问题,要将方法划分为较小的问题.可以采用递归重复这一过程,直到需要解决的问题变得很小,可以直接解决.必须很小心的选择可以直接解决的基本用例,问题规模选择不当会导致糟糕的性能.这种问题可以使用执行器解决,但是为了更高效的解决问题,Java7并发API引入了Fork/Join框架.
该框架基于ForkJoinPool类,该类是一种特殊的执行器,具有fork()和join()两个操作(以及他们的不同变体),以及一个杯称为工作窃取算法的内部算法.

Fork/Join框架的基本特征

如前所述,FOrk/Join框架必须用于解决基于分治方法的问题.必须将原始问题划分为较小的问题,直到问题很小,可以直接解决,有了这个框架,待实现任务的主方法便如下所示:

if(problem.size() > DEFAULT_SIZE){
	divideTasks();
	executeTask();
	taskResults = joinTasksResult();
	return taskResults;
}else{
	taskResults = solveBasicProblem();
	return taskResults;
}

该任务最大的好处是可以高效分割和执行子任务,并且获取任务的结果以计算父任务的结果.该功能由ForkJoinTask类提供的如下两个方法支持

fork()方法: 该方法可以将一个子任务发送给Fork/Join执行器
join()方法:该方法可以等待一个子任务执行结束后返回其结果

Fork/join框架还有一个关键特性,就是工作窃取算法.该算法确定要执行的任务.当一个任务使用join()方法等待某个子任务结束的时候,执行该任务的线程会从任务池中选取另一个等待执行的任务并开始执行.通过这种方式,Fork/Join执行器的线程总是会通过改进应用程序的性能来执行任务.
Java8在Fork/Join框架中提供了一种新特性.现在每个Java应用程序都有一个默认的ForkJoinPool,称作公用池.可以通过调用静态方法ForkJoinPool.commonPool()获取这样的公用池,而不需要采用显式方法创建.这种默认的Fork/Join框架会自动使用计算机可用处理器确定线程数.可以通过更改系统属性来需改这一默认行为

Fork/Join框架的组件

Fork/Join框架包含四个基本类

ForkJoinPool类:该类实现了Executor接口和ExecutorService接口,而执行Fork/Join任务时将用到Executor接口.Java提供了一个默认的ForkJoinPool对象(称作公用池)
ForkJoinTask类: 这是所有Fork/Join任务的基本抽象类.该类是一个抽象类,提供了fork()方法和join()方法,以及这些方法的一些变体.该类还实现了future接口,提供了一些方法来判断任务是否是正常结束,他是否会被撤销,或者是否抛出了一个未校验异常.RecursiveTask类,recusiveAction类和CountedCompleter类提供了compute()抽象方法.为了执行实际计算任务,该方法应该在子类中实现
RecursiveTask类: 该类扩展了ForkJoinTask类. RecursiveTask也是一个抽象类,而且应该作为实现返回结果的Fork/Join任务的起点
RecursiveAction类: 该类扩展了ForkJoinTask类. RecursiveAction类也是一个抽象类,而且应该作为实现不返回结果的Fork/Join任务的起点
CountedCompleter类: 该类扩展了ForkJoinTask类.该类作为实现任务完成时触发另一个任务的起点