Home> Java> javaTutorial> body text

How to apply ForkJoin, the java divide and conquer idea

PHPz
Release: 2023-05-12 21:16:04
forward
797 people have browsed it

Divide and Conquer Algorithm

The fork-join mode is one of the parallel computing modes based on the divide and conquer idea. This mode divides a large task into multiple small subtasks, then executes these subtasks in parallel, and finally merges their results to get the final result. In this process, the execution of each subtask can be further decomposed into smaller subtasks until a certain threshold is reached, at which time the tasks will be executed serially. This recursive divide-and-conquer idea allows the fork-join mode to effectively utilize the computer's multi-core processing capabilities, thereby improving program performance and efficiency.

Merge sort

Merge sort is a sorting algorithm based on the divide and conquer idea. The core idea is to divide an array into two sub-arrays, sort them separately and then merge them. The specific implementation process is as follows:

  • Decomposition: Divide an array into two sub-arrays and sort them respectively. This step can be accomplished using recursion.

  • Merge: Merge the two sorted subarrays into an ordered array.

  • Recursion: Decompose and sort the two subarrays recursively until each subarray has length 1.

The time complexity is O(nlogn).

How to apply ForkJoin, the java divide and conquer idea

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]; } } }
Copy after login

Quick Sort

Quick Sort is a sorting algorithm based on the divide and conquer idea. It uses a recursive method to sort a large The array is decomposed into multiple sub-arrays, sorted separately and then merged. The basic idea is to select a benchmark element, put the values in the array that are smaller than the element on the left, the values that are larger than the element on the right, and then recursively sort the left and right sub-arrays. The specific steps are as follows:

  • Select a reference element (usually the first element in the array).

  • Put the values in the array that are smaller than the element on the left, and the values that are larger than the element on the right.

  • Quickly sort the left and right sub-arrays recursively.

  • Merge the left and right sorted subarrays.

The time complexity of quick sort is O(nlogn). It is an in-place sorting algorithm and does not require additional storage space, so the space complexity is O(1). Although the worst time complexity of quick sort is O(n^2), in practical applications, the average time complexity and the best time complexity of quick sort are both O(nlogn), so it is a very efficient method. Sorting algorithm

How to apply ForkJoin, the java divide and conquer idea

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 pivot){ j--; } if(i
        
Copy after login

Fork/Join

The main components of the Fork/Join framework are ForkJoinPool and ForkJoinTask. ForkJoinPool is a thread pool that manages the execution of ForkJoin tasks. ForkJoinTask is an abstract class used to represent tasks that can be divided into smaller parts.

ForkJoinPool

ForkJoinPool is the thread pool class in the Fork/Join framework, which is used to manage the threads of the Fork/Join task. The ForkJoinPool class includes some important methods, such as submit(), invoke(), shutdown(), awaitTermination(), etc., which are used to submit tasks, execute tasks, close the thread pool and wait for the execution results of tasks. The ForkJoinPool class also includes some parameters, such as the size of the thread pool, the priority of the worker thread, the capacity of the task queue, etc., which can be set according to specific application scenarios.

Constructor

There are four core parameters in ForkJoinPool, which are used to control the number of parallel thread pools, creation of worker threads, exception handling, and mode specification.

  • int parallelism: Specify the parallelism level. ForkJoinPool will determine the number of worker threads based on this setting. If not set, Runtime.getRuntime().availableProcessors() will be used to set the parallel level;

  • ForkJoinWorkerThreadFactory factory: ForkJoinPool will be created through the factory when creating a thread. Note that what needs to be implemented here is ForkJoinWorkerThreadFactory, not ThreadFactory. If you do not specify factory, the default DefaultForkJoinWorkerThreadFactory will be responsible for thread creation;

  • UncaughtExceptionHandler handler: Specify the exception handler. When an error occurs during the task, it will be handled by the set handler. Processor;

  • boolean asyncMode: Set the working mode of the queue. When asyncMode is true, the first-in-first-out queue will be used, and when it is false, the last-in-first-out mode will be used.

Work stealing method

In Fork-Join mode, tasks are assigned to worker threads in a thread pool for execution. When a worker thread completes its assigned tasks, it can steal (Steal) tasks from the task queues of other worker threads for execution. This is called work stealing (Work Stealing).

Use
public class SumTask extends RecursiveTask { 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); } }
Copy after login

The above is the detailed content of How to apply ForkJoin, the java divide and conquer idea. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:yisu.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!