How to apply ForkJoin, the java divide and conquer idea

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).

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

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

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

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<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);
    }
}

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!