fork join框架使用

此項(xiàng)的目的是顯示一個(gè)Fork / Join RecursiveAction的簡單示例，而不是過多地探討合并排序的可能優(yōu)化方法，或者比使用Exkutor / Join Pool優(yōu)于現(xiàn)有的基于Java 6的現(xiàn)有實(shí)現(xiàn)（如ExecutorService）的相對優(yōu)勢。

以下是使用Java的自上而下合并排序算法的典型實(shí)現(xiàn)：

import java.lang.reflect.Array;public class MergeSort {public static <T extends Comparable<? super T>> void sort(T[] a) {@SuppressWarnings('unchecked')T[] helper = (T[])Array.newInstance(a[0].getClass() , a.length);mergesort(a, helper, 0, a.length-1);}private static <T extends Comparable<? super T>> void mergesort(T[] a, T[] helper, int lo, int hi){if (lo>=hi) return;int mid = lo + (hi-lo)/2;mergesort(a, helper, lo, mid);mergesort(a, helper, mid+1, hi);merge(a, helper, lo, mid, hi); }private static <T extends Comparable<? super T>> void merge(T[] a, T[] helper, int lo, int mid, int hi){for (int i=lo;i<=hi;i++){helper[i]=a[i];}int i=lo,j=mid+1;for(int k=lo;k<=hi;k++){if (i>mid){a[k]=helper[j++];}else if (j>hi){a[k]=helper[i++];}else if(isLess(helper[i], helper[j])){a[k]=helper[i++];}else{a[k]=helper[j++];}}}private static <T extends Comparable<? super T>> boolean isLess(T a, T b) {return a.compareTo(b) < 0;} }

為了快速描述算法-
遞歸執(zhí)行以下步驟：

輸入數(shù)據(jù)分為兩半

每一半都被排序

然后將排序的數(shù)據(jù)合并

合并排序是使用Java Fork / Join池實(shí)現(xiàn)的一個(gè)典型示例 ，以下是使用Fork / Join框架進(jìn)行合并排序的盲目實(shí)現(xiàn)：

合并排序中的遞歸任務(wù)可以簡單地表示為RecursiveAction的實(shí)現(xiàn)–

private static class MergeSortTask<T extends Comparable<? super T>> extends RecursiveAction{private static final long serialVersionUID = -749935388568367268L;private final T[] a;private final T[] helper;private final int lo;private final int hi;public MergeSortTask(T[] a, T[] helper, int lo, int hi){this.a = a;this.helper = helper;this.lo = lo;this.hi = hi;}@Overrideprotected void compute() {if (lo>=hi) return;int mid = lo + (hi-lo)/2;MergeSortTask<T> left = new MergeSortTask<>(a, helper, lo, mid);MergeSortTask<T> right = new MergeSortTask<>(a, helper, mid+1, hi);invokeAll(left, right);merge(this.a, this.helper, this.lo, mid, this.hi);}private void merge(T[] a, T[] helper, int lo, int mid, int hi){for (int i=lo;i<=hi;i++){helper[i]=a[i];}int i=lo,j=mid+1;for(int k=lo;k<=hi;k++){if (i>mid){a[k]=helper[j++];}else if (j>hi){a[k]=helper[i++];}else if(isLess(helper[i], helper[j])){a[k]=helper[i++];}else{a[k]=helper[j++];}}}private boolean isLess(T a, T b) {return a.compareTo(b) < 0;}}

上面的MergeSortTask實(shí)現(xiàn)了一個(gè)計(jì)算方法，該方法接受一個(gè)值數(shù)組，將其分成兩個(gè)部分，從每個(gè)部分中創(chuàng)建一個(gè)MergeSortTask并分叉另外兩個(gè)任務(wù)（因此稱為RecursiveAction！）。 此處用于生成任務(wù)的特定API是invokeAll ，僅當(dāng)已提交的子任務(wù)標(biāo)記為已完成時(shí)才返回。 因此，左右子任務(wù)返回后，結(jié)果將合并到合并例程中。

鑒于此，剩下的唯一工作就是使用ForkJoinPool提交此任務(wù)。 ForkJoinPool與用于在線程池中分發(fā)任務(wù)的ExecutorService類似，不同之處在于引用了ForkJoinPool的API文檔：

ForkJoinPool與其他類型的ExecutorService的不同之處主要在于采用了工作竊取：池中的所有線程都試圖查找并執(zhí)行由其他活動(dòng)任務(wù)創(chuàng)建的子任務(wù)（如果不存在，則最終阻塞等待工作）

這是將任務(wù)提交到Fork / Join Pool的任務(wù)的樣子：

public static <T extends Comparable<? super T>> void sort(T[] a) {@SuppressWarnings('unchecked')T[] helper = (T[])Array.newInstance(a[0].getClass() , a.length);ForkJoinPool forkJoinPool = new ForkJoinPool(10);forkJoinPool.invoke(new MergeSortTask<T>(a, helper, 0, a.length-1));}

完整的示例也可以在這里找到： https : //github.com/bijukunjummen/algos/blob/master/src/main/java/org/bk/algo/sort/algo04/merge/MergeSortForkJoin.java

參考： all和其他博客中的Mergesort 使用我們JCG合作伙伴 Biju Kunjummen的Fork / Join Framework 。

翻譯自: https://www.javacodegeeks.com/2012/08/java-mergesort-using-forkjoin-framework.html

fork join框架使用

總結(jié)

以上是生活随笔為你收集整理的fork join框架使用_Java：使用Fork / Join框架的Mergesort的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。