java分治思想之ForkJoin怎么應用

本文小編為大家詳細介紹“java分治思想之ForkJoin怎么應用”，內容詳細，步驟清晰，細節處理妥當，希望這篇“java分治思想之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怎么應用”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。