本文共 6795 字，大约阅读时间需要 22 分钟。
总结概括：
1.数据结构 归并排序 （也是后续排序 LRD）
2.多线程 ForkJoin框架 繁重任务的并行计算框架，map-reduce思想
计算代码
/*** *@author dongsheng *@date 2019/1/18 22:58 *@Description: *@version 1.0.0 */public class ArrayMergerSortTask extends RecursiveAction { // implementation details follow: static final int THRESHOLD = 1000; final int[] array; final int lo, hi; ArrayMergerSortTask(int[] array, int lo, int hi) { this.array = array; this.lo = lo; this.hi = hi; } ArrayMergerSortTask(int[] array) { this(array, 0, array.length); } protected void compute() { if (hi - lo < THRESHOLD) //小于1000，就排序 sortSequentially(lo, hi); else { int mid = (lo + hi) >>> 1; //大于1000，拆分 invokeAll(new ArrayMergerSortTask(array, lo, mid), new ArrayMergerSortTask(array, mid, hi)); merge(lo, mid, hi); } } void sortSequentially(int lo, int hi) { Arrays.sort(array, lo, hi); //利用JDK自带的排序进行 } void merge(int lo, int mid, int hi) { int[] buf = Arrays.copyOfRange(array, lo, mid); for (int i = 0, j = lo, k = mid; i < buf.length; j++) array[j] = (k == hi || buf[i] < array[k]) ? buf[i++] : array[k++]; } public static void main(String[] args) throws Exception { // 这里以一个长度为2千的数组做示例 int length = 2_000; int[] array = new int[length]; // 填充数值 Random random = new Random(); for (int i = 0; i < length; i++) { array[i] = random.nextInt(); System.out.println(array[i]); } // 利用forkjoinpool来完成多线程快速归并排序 ArrayMergerSortTask stask = new ArrayMergerSortTask(array); ForkJoinPool pool = new ForkJoinPool(); pool.submit(stask); // 等待任务完成 stask.get(); System.out.println("----------排序后的结果:"); for (int d : array) { System.out.println(d); } }} RecursiveAction
ForkJoinTask 的子类， 是 ForkJoinTask 的一个子类，它代表了一类最简单的 ForkJoinTask：不需要返回值，当子任务都执行完毕之后，不需要进行中间结果的组合。如果我们从 RecursiveAction 开始继承，那么我们只需要重载 protected void compute() 方法。源码代码
/* * * * * * * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/publicdomain/zero/1.0/ */package java.util.concurrent;/** * A recursive resultless {@link ForkJoinTask}. This class * establishes conventions to parameterize resultless actions as * {@code Void} {@code ForkJoinTask}s. Because {@code null} is the * only valid value of type {@code Void}, methods such as {@code join} * always return {@code null} upon completion. * * Sample Usages. Here is a simple but complete ForkJoin * sort that sorts a given {@code long[]} array: * *
{@code * static class SortTask extends RecursiveAction { * final long[] array; final int lo, hi; * SortTask(long[] array, int lo, int hi) { * this.array = array; this.lo = lo; this.hi = hi; * } * SortTask(long[] array) { this(array, 0, array.length); } * protected void compute() { * if (hi - lo < THRESHOLD) * sortSequentially(lo, hi); * else { * int mid = (lo + hi) >>> 1; * invokeAll(new SortTask(array, lo, mid), * new SortTask(array, mid, hi)); * merge(lo, mid, hi); * } * } * // implementation details follow: * static final int THRESHOLD = 1000; * void sortSequentially(int lo, int hi) { * Arrays.sort(array, lo, hi); * } * void merge(int lo, int mid, int hi) { * long[] buf = Arrays.copyOfRange(array, lo, mid); * for (int i = 0, j = lo, k = mid; i < buf.length; j++) * array[j] = (k == hi || buf[i] < array[k]) ? * buf[i++] : array[k++]; * } * }} * * You could then sort {@code anArray} by creating {@code new * SortTask(anArray)} and invoking it in a ForkJoinPool. As a more * concrete simple example, the following task increments each element * of an array: * {@code * class IncrementTask extends RecursiveAction { * final long[] array; final int lo, hi; * IncrementTask(long[] array, int lo, int hi) { * this.array = array; this.lo = lo; this.hi = hi; * } * protected void compute() { * if (hi - lo < THRESHOLD) { * for (int i = lo; i < hi; ++i) * array[i]++; * } * else { * int mid = (lo + hi) >>> 1; * invokeAll(new IncrementTask(array, lo, mid), * new IncrementTask(array, mid, hi)); * } * } * }} * * The following example illustrates some refinements and idioms * that may lead to better performance: RecursiveActions need not be * fully recursive, so long as they maintain the basic * divide-and-conquer approach. Here is a class that sums the squares * of each element of a double array, by subdividing out only the * right-hand-sides of repeated divisions by two, and keeping track of * them with a chain of {@code next} references. It uses a dynamic * threshold based on method {@code getSurplusQueuedTaskCount}, but * counterbalances potential excess partitioning by directly * performing leaf actions on unstolen tasks rather than further * subdividing. * *
{@code * double sumOfSquares(ForkJoinPool pool, double[] array) { * int n = array.length; * Applyer a = new Applyer(array, 0, n, null); * pool.invoke(a); * return a.result; * } * * class Applyer extends RecursiveAction { * final double[] array; * final int lo, hi; * double result; * Applyer next; // keeps track of right-hand-side tasks * Applyer(double[] array, int lo, int hi, Applyer next) { * this.array = array; this.lo = lo; this.hi = hi; * this.next = next; * } * * double atLeaf(int l, int h) { * double sum = 0; * for (int i = l; i < h; ++i) // perform leftmost base step * sum += array[i] * array[i]; * return sum; * } * * protected void compute() { * int l = lo; * int h = hi; * Applyer right = null; * while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) { * int mid = (l + h) >>> 1; * right = new Applyer(array, mid, h, right); * right.fork(); * h = mid; * } * double sum = atLeaf(l, h); * while (right != null) { * if (right.tryUnfork()) // directly calculate if not stolen * sum += right.atLeaf(right.lo, right.hi); * else { * right.join(); * sum += right.result; * } * right = right.next; * } * result = sum; * } * }} * * @since 1.7 * @author Doug Lea */public abstract class RecursiveAction extends ForkJoinTask { private static final long serialVersionUID = 5232453952276485070L; /** * The main computation performed by this task. */ protected abstract void compute(); /** * Always returns {@code null}. * * @return {@code null} always */ public final Void getRawResult() { return null; } /** * Requires null completion value. */ protected final void setRawResult(Void mustBeNull) { } /** * Implements execution conventions for RecursiveActions. */ protected final boolean exec() { compute(); return true; }}
转载地址：http://fujdi.baihongyu.com/