java分治思想之ForkJoin详解

目录
  • 前言
  • 分治思想算法
    • 归并排序
    • 快速排序
  • Fork/Join
    • ForkJoinPool
      • 构造器
    • 工作窃取法
      • 使用

前言

  当我们面对需要同时执行多个任务的情况时,往往需要耗费大量的时间和精力来编写复杂的并发代码。但是有一种技术可以帮助我们轻松地处理这种情况。通过forkJoin,我们可以简单地实现多个任务的并行执行,从而提高应用程序的性能和响应能力。在本文中,我们将深入探讨forkJoin的工作原理和使用方法。

分治思想算法

  fork-join模式是基于分治思想的并行计算模式之一。该模式将一个大的任务分割成多个小的子任务,然后并行执行这些子任务,最后将它们的结果合并起来得到最终的结果。在这个过程中,每个子任务的执行可以进一步分解为更小的子任务,直到达到某个阈值,这时候任务将被串行执行。这种递归的分治思想使得fork-join模式可以有效地利用计算机的多核处理能力,从而提高程序的性能和效率。

归并排序

归并排序是一种基于分治思想的排序算法。其核心思想是将一个数组分成两个子数组,分别对其进行排序后再将其合并起来。具体实现过程如下:

  • 分解:将一个数组分成两个子数组,分别对其进行排序。可以使用递归来实现这一步骤。
  • 合并:将排序后的两个子数组合并成一个有序的数组。
  • 递归:对两个子数组递归进行分解和排序,直到每个子数组的长度为1。

时间复杂度为O(nlogn)。

public class Merge {
    public static void main(String[] args) {
        int[] arr = { 5, 2, 8, 4, 7, 1, 3, 6 };
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 拆分
     * @param arr 数组
     * @param left 数组第一个元素
     * @param right 数组最后一个元素
     */
    public static void mergeSort(int[] arr,int left,int right){
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    /**
     * 合并
     * @param arr 数组
     * @param left 数组第一个元素
     * @param mid 数组分割的元素
     * @param right 数组最后一个元素
     */
    public static void merge(int[] arr,int left,int mid,int right){
        //创建临时数组,用于存放合并后的数组
        int[] temp = new int[right - left + 1];
        //左面数组的起始指针
        int i = left;
        //右面数组的起始指针
        int j = mid + 1;
        //临时数组的下标
        int k = 0;
        //数组左面和数组右面都还有值就去遍历比较赋值
        while (i <= mid && j <= right) {
            //数组左面的值小于或者等于数组右面的值就把左面的值赋值到临时数组中
            //并且把左面的指针和临时数组的指针+1
            //否则相反
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                k++;
                i++;
            } else {
                temp[k] = arr[j];
                k++;
                j++;
            }
        }
        //把剩余数组塞进去
        while (i <= mid) {
            temp[k] = arr[i];
            k++;
            i++;
        }
        while (j <= right) {
            temp[k] = arr[j];
            k++;
            j++;
        }
        //讲临时数组中的元素拷贝会回原数组中
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }
}

快速排序

快速排序(Quick Sort)是一种基于分治思想的排序算法,它采用了递归的方式将一个大的数组分解成多个子数组,分别进行排序后再将它们合并起来。其基本思想是选取一个基准元素,将数组中小于该元素的值放在左边,大于该元素的值放在右边,然后递归地对左右两个子数组进行排序。具体的步骤如下:

  • 选取一个基准元素(通常是数组中的第一个元素)。
  • 将数组中小于该元素的值放在左边,大于该元素的值放在右边。
  • 对左右两个子数组分别递归进行快速排序。
  • 合并左右两个已排序的子数组。

快速排序的时间复杂度为O(nlogn),它是一种原地排序算法,不需要额外的存储空间,因此空间复杂度为O(1)。虽然快速排序的最坏时间复杂度为O(n^2),但是在实际应用中,快速排序的平均时间复杂度和最好时间复杂度均为O(nlogn),因此是一种非常高效的排序算法

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 5, 2, 8, 4, 7, 1, 3, 6 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left<right){
            int pivotIndex  = partition(arr, left, right);
            quickSort(arr,left,pivotIndex-1);
            quickSort(arr,pivotIndex+1,right);
        }
    }
    public static int partition(int[] arr,int left,int right){
        //取第一个元素为基准元素
        int pivot = arr[left];
        int i = left+1;
        int j = right;
        while (i<=j){
            //当前指针位置数小于基准元素就继续移动指针直到遇到大的
            while (i<=j && arr[i] < pivot){
                i++;
            }
            //当前指针位置数大于基准元素就继续移动指针直到遇到小的
            while (i<=j && arr[j] > pivot){
                j--;
            }
            if(i<j){
                //交换元素位置
                swap(arr,i,j);
                i++;
                j--;
            }
        }
        //跳出循环说明i和j相遇,j的值一定是大于基准元素,要和基准元素进行交换
        swap(arr,left,j);
        //返回基准元素位置
        return j;
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Fork/Join

  Fork/Join框架的主要组成部分是ForkJoinPool、ForkJoinTask。ForkJoinPool是一个线程池,它用于管理ForkJoin任务的执行。ForkJoinTask是一个抽象类,用于表示可以被分割成更小部分的任务。

ForkJoinPool

ForkJoinPool是Fork/Join框架中的线程池类,它用于管理Fork/Join任务的线程。ForkJoinPool类包括一些重要的方法,例如submit()、invoke()、shutdown()、awaitTermination()等,用于提交任务、执行任务、关闭线程池和等待任务的执行结果。ForkJoinPool类中还包括一些参数,例如线程池的大小、工作线程的优先级、任务队列的容量等,可以根据具体的应用场景进行设置。

构造器

ForkJoinPool中有四个核心参数,用于控制线程池的并行数、工作线程的创建、异常处理和模式指定等。

  • int parallelism:指定并行级别(parallelism level)。ForkJoinPool将根据这个设定,决定工作线程的数量。如果未设置的话,将使用Runtime.getRuntime().availableProcessors()来设置并行级别;
  • ForkJoinWorkerThreadFactory factory:ForkJoinPool在创建线程时,会通过factory来创建。注意,这里需要实现的是ForkJoinWorkerThreadFactory,而不是ThreadFactory。如果你不指定factory,那么将由默认的 DefaultForkJoinWorkerThreadFactory负责线程的创建工作;
  • UncaughtExceptionHandler handler:指定异常处理器,当任务在运行中出错时,将由设定的处理器处理;
  • boolean asyncMode:设置队列的工作模式。当asyncMode为true时,将使用先进先出队列,而为false时则使用后进先出的模式。

工作窃取法

在Fork-Join模式中,任务被分配给一个线程池中的工作线程来执行。当一个工作线程执行完自己分配的任务后,它可以从其他工作线程的任务队列中偷取(Steal)任务来执行,这就是所谓的工作窃取(Work Stealing)。

使用

public class SumTask extends RecursiveTask<Integer> {
    private static final int THRESHOLD = 1000;
    private int[] array;
    private int start;
    private int end;
    public SumTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }
    @Override
    protected Integer compute() {
        if (end - start <= THRESHOLD) {
            int sum = 0;
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        } else {
            int mid = (start + end) / 2;
            SumTask leftTask = new SumTask(array, start, mid);
            SumTask rightTask = new SumTask(array, mid, end);
            leftTask.fork();
            rightTask.fork();
            int leftResult = leftTask.join();
            int rightResult = rightTask.join();
            return leftResult + rightResult;
        }
    }
    public static void main(String[] args) {
        int[] array = new int[10000];
        for (int i = 0; i < array.length; i++) {
            array[i] = i + 1;
        }
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        SumTask task = new SumTask(array, 0, array.length);
        int result = forkJoinPool.invoke(task);
        System.out.println(result);
    }
}

以上就是java分治思想之ForkJoin详解的详细内容,更多关于java分治思想ForkJoin的资料请关注我们其它相关文章!

(0)

相关推荐

  • java中的forkjoin框架的使用

    fork join框架是java 7中引入框架,这个框架的引入主要是为了提升并行计算的能力. fork join主要有两个步骤,第一就是fork,将一个大任务分成很多个小任务,第二就是join,将第一个任务的结果join起来,生成最后的结果.如果第一步中并没有任何返回值,join将会等到所有的小任务都结束. 还记得之前的文章我们讲到了thread pool的基本结构吗? ExecutorService - ForkJoinPool 用来调用任务执行. workerThread - ForkJoi

  • Java 并发编程之ForkJoin框架

    目录 1.什么是ForkJoin框架 2.ForkJoinTask 3.ForkJoinPool 4.打印斐波那契数列 5.ForkJoin归并排序 总结 1.什么是ForkJoin框架 ForkJoin框架是java的JUC包里提供的,用于处理一些比较繁重的任务,会将这个大任务分为多个小任务,多个小任务处理完成后会将结果汇总给Result,体现的是一种"分而治之"的思想.第一步,拆分fork任务,将大任务分为多个小任务:第二步,归并join,会将小任务的处理结果进行归并为一个结果.

  • Java线程池ForkJoinPool(工作窃取算法)的使用

    目录 概述 工作窃取算法 工作窃取算法的优缺点 使用 ForkJoinPool 进行分叉和合并 ForkJoinPool使用 RecursiveAction RecursiveTask Fork/Join 案例Demo 概述 Fork 就是把一个大任务切分为若干个子任务并行地执行,Join 就是合并这些子任务的执行结果,最后得到这个大任务的结果.Fork/Join 框架使用的是工作窃取算法. 工作窃取算法 工作窃取算法是指某个线程从其他队列里窃取任务来执行.对于一个比较大的任务,可以把它分割为若

  • 一文带你了解Java中的ForkJoin

    目录 什么是ForkJoin? ForkJoinTask 任务 ForkJoinPool 线程池 工作窃取算法 构造方法 提交方法 创建工人(线程) 例:ForkJoinTask实现归并排序 ForkJoin计算流程 前言: ForkJoin是在Java7中新加入的特性,大家可能对其比较陌生,但是Java8中Stream的并行流parallelStream就是依赖于ForkJoin.在ForkJoin体系中最为关键的就是ForkJoinTask和ForkJoinPool,ForkJoin就是利用

  • Java线程池ForkJoinPool实例解析

    这篇文章主要介绍了Java线程池ForkJoinPool实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 背景:ForkJoinPool的优势在于,可以充分利用多cpu,多核cpu的优势,把一个任务拆分成多个"小任务",把多个"小任务"放到多个处理器核心上并行执行:当多个"小任务"执行完成之后,再将这些执行结果合并起来即可.这种思想值得学习. import java.io.IOExcept

  • Java分治归并排序算法实例详解

    本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,

  • Java的SPI机制实例详解

    Java的SPI机制实例详解 SPI的全名为Service Provider Interface.普通开发人员可能不熟悉,因为这个是针对厂商或者插件的.在java.util.ServiceLoader的文档里有比较详细的介绍.究其思想,其实是和"Callback"差不多."Callback"的思想是在我们调用API的时候,我们可以自己写一段逻辑代码,传入到API里面,API内部在合适的时候会调用它,从而实现某种程度的"定制". 典型的是Colle

  • java中变量和常量详解

    变量和常量 在程序中存在大量的数据来代表程序的状态,其中有些数据在程序的运行过程中值会发生改变,有些数据在程序运行过程中值不能发生改变,这些数据在程序中分别被叫做变量和常量. 在实际的程序中,可以根据数据在程序运行中是否发生改变,来选择应该是使用变量代表还是常量代表. 变量 变量代表程序的状态.程序通过改变变量的值来改变整个程序的状态,或者说得更大一些,也就是实现程序的功能逻辑. 为了方便的引用变量的值,在程序中需要为变量设定一个名称,这就是变量名.例如在2D游戏程序中,需要代表人物的位置,则需

  • Java接口和抽象类原理详解

    这篇文章主要介绍了Java接口和抽象类原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 对于面向对象编程来说,抽象是它的一大特征之一.在Java中,可以通过两种形式来体现OOP的抽象:接口和抽象类.这两者有太多相似的地方,又有太多不同的地方.很多人在初学的时候会以为它们可以随意互换使用,但是实际则不然.今天我们就一起来学习一下Java中的接口和抽象类.下面是本文的目录大纲: 一.抽象类 在了解抽象类之前,先来了解一下抽象方法.抽象方法是一

  • Java垃圾回收机制算法详解

    概述 Java GC(Garbage Collection,垃圾回收)机制,是Java与C++/C的主要区别之一,作为Java开发者,一般不需要专门编写内存回收和垃圾清理代码,对内存泄露和溢出的问题,也不需要像C程序员那样战战兢兢.这是因为在Java虚拟机中,存在自动内存管理和垃圾清扫机制.概括地说,该机制对JVM中的内存进行标记,并确定哪些内存需要回收,根据一定的回收策略,自动的回收内存,永不停息的保证JVM中的内存空间,防止出现内存泄露和溢出问题. 在真实工作中的项目中,时不时的会发生内存溢

  • Java设计模式之原型模式详解

    一.前言 原型模式是一种比较简单的模式,也非常容易理解,实现一个接口,重写一个方法即完成了原型模式.在实际应用中,原型模式很少单独出现.经常与其他模式混用,他的原型类Prototype也常用抽象类来替代. 该模式的思想就是将一个对象作为原型,对其进行复制.克隆,产生一个和原对象类似的新对象.在Java中,复制对象是通过clone()实现的,先创建一个原型类,通过实现Cloneable 接口 public class Prototype implements Cloneable { public

  • Java 括号匹配问题案例详解

    目录 前言 例题 算法思想 算法举例 代码 栈类 括号匹配核心算法 完整代码 运行结果 前言 括号匹配问题算是栈应用中比较经典的问题了,在数据结构的书中还有各种考试中会出现.最近刷题的时候也遇到了,就想写一篇文章整理一下. 例题 题目来自Leetcode中国 给定一个只包括 (,),{,},[,] 的字符串,判断字符串是否有效. 有效字符串需满足: 1.左括号必须用相同类型的右括号闭合. 2.左括号必须以正确的顺序闭合. 注意空字符串可被认为是有效字符串. 示例 1: 输入: "()"

  • Java之JSF框架案例详解

    这是一个分为两部分的系列,其中我介绍了JSF 2及其如何适合Java EE生态系统. 在第1部分中,我将介绍JavaServer Pages(JSF)背后的基本思想 ,在第2部分中,将介绍Facelets声明语言 . 在构建Web应用程序时,我们为最终用户提供了一种与我们的应用程序进行交互的方式,这就是JSF所提供的. 我将向您介绍MVC设计模式以及如何使用它,并且您将发现Facelets视图语言及其使用方式,如何将数据和事件绑定到上下文以及如何通过表达语言来实现. 我将通过查看替代模板框架(例

  • Java双冒号(::)运算符使用详解

    目录 1.说明 2.先来说下@FunctionalInterface 3. 下面来讲讲这个 "::"是干嘛的 4. 建立一个Person类 4:构建多个person对象,放入数组中,然后对数组中的person重新排序 5:揭秘 "::"符号 6.0 方法引用的支持如下 1.说明 之前没用过::这个东西,今天看flink的时候发现官网有个例子用到了这个符号, 本着求知欲去百度查了一番,没找到能说到我心里去的解释,本着求知欲的态度,我去了官网看了看. java :: 2

  • Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

随机推荐