So wenden Sie ForkJoin an, die Java-Divide-and-Conquer-Idee

Divide-and-Conquer-Algorithmus

Der Fork-Join-Modus ist einer der parallelen Rechenmodi, der auf der Divide-and-Conquer-Idee basiert. Dieser Modus unterteilt eine große Aufgabe in mehrere kleine Unteraufgaben, führt diese Unteraufgaben dann parallel aus und kombiniert schließlich ihre Ergebnisse, um das Endergebnis zu erhalten. In diesem Prozess kann die Ausführung jeder Unteraufgabe weiter in kleinere Unteraufgaben zerlegt werden, bis ein bestimmter Schwellenwert erreicht ist. Zu diesem Zeitpunkt werden die Aufgaben seriell ausgeführt. Diese rekursive Divide-and-Conquer-Idee ermöglicht es dem Fork-Join-Modus, die Multi-Core-Verarbeitungsfähigkeiten des Computers effektiv zu nutzen und dadurch die Programmleistung und -effizienz zu verbessern.

Merge-Sortierung

Merge-Sortierung ist ein Sortieralgorithmus, der auf der Divide-and-Conquer-Idee basiert. Die Kernidee besteht darin, ein Array in zwei Unterarrays aufzuteilen, diese separat zu sortieren und dann zusammenzuführen. Der spezifische Implementierungsprozess ist wie folgt:

• Zerlegung: Teilen Sie ein Array in zwei Unterarrays und sortieren Sie diese entsprechend. Dieser Schritt kann mithilfe einer Rekursion ausgeführt werden.

• Zusammenführen: Füge die beiden sortierten Unterarrays zu einem geordneten Array zusammen.

• Rekursiv: Zerlegen und sortieren Sie die beiden Unterarrays rekursiv, bis die Länge jedes Unterarrays 1 beträgt.

Die Zeitkomplexität ist 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 (Quick Sort) ist ein Sortieralgorithmus, der auf der Divide-and-Conquer-Idee basiert. Er verwendet eine rekursive Methode, um ein großes Array in mehrere Unterarrays zu zerlegen und diese dann separat zu sortieren. Sie verschmelzen. Die Grundidee besteht darin, ein Benchmark-Element auszuwählen, die Werte, die kleiner als das Element links sind, und die Werte, die größer als das Element rechts sind, in das Array einzufügen und dann links und rechts rekursiv zu sortieren Unterarrays. Die spezifischen Schritte sind wie folgt:

• Wählen Sie ein Referenzelement aus (normalerweise das erste Element im Array).

• Fügen Sie die Werte in das Array ein, die kleiner als das Element links sind, und die Werte, die größer als das Element rechts sind.

• Sortieren Sie die linken und rechten Unterarrays schnell rekursiv.

• Führen Sie die links und rechts sortierten Unterarrays zusammen.

Die Zeitkomplexität der Schnellsortierung beträgt O(nlogn). Es handelt sich um einen In-Place-Sortieralgorithmus, der keinen zusätzlichen Speicherplatz benötigt, daher beträgt die Platzkomplexität O(1). Obwohl die schlechteste Zeitkomplexität der Schnellsortierung O(n^2) ist, sind in praktischen Anwendungen sowohl die durchschnittliche Zeitkomplexität als auch die beste Zeitkomplexität der Schnellsortierung O(nlogn), sodass es sich um einen sehr effizienten Sortieralgorithmus handelt

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

Die Hauptkomponenten des Fork/Join-Frameworks sind ForkJoinPool und ForkJoinTask. ForkJoinPool ist ein Thread-Pool, der die Ausführung von ForkJoin-Aufgaben verwaltet. ForkJoinTask ist eine abstrakte Klasse, die zur Darstellung von Aufgaben verwendet wird, die in kleinere Teile unterteilt werden können.

ForkJoinPool

ForkJoinPool ist die Thread-Pool-Klasse im Fork/Join-Framework, die zum Verwalten der Threads der Fork/Join-Aufgabe verwendet wird. Die ForkJoinPool-Klasse enthält einige wichtige Methoden, wie zum Beispiel „submit()“, „invoke()“, „shutdown()“, „awaitTermination()“ usw., die zum Senden von Aufgaben, zum Ausführen von Aufgaben, zum Schließen des Thread-Pools und zum Warten auf die Ausführungsergebnisse von verwendet werden Aufgaben. Die ForkJoinPool-Klasse enthält auch einige Parameter, wie z. B. die Größe des Thread-Pools, die Priorität des Arbeitsthreads, die Kapazität der Aufgabenwarteschlange usw., die entsprechend bestimmten Anwendungsszenarien festgelegt werden können. Es gibt vier Kernparameter im

Konstruktor

ForkJoinPool, die zur Steuerung der Anzahl paralleler Thread-Pools, der Erstellung von Arbeitsthreads, der Ausnahmebehandlung und der Modusspezifikation verwendet werden.

• int Parallelität: Geben Sie den Parallelitätsgrad an. ForkJoinPool bestimmt die Anzahl der Arbeitsthreads basierend auf dieser Einstellung. Wenn nicht festgelegt, wird Runtime.getRuntime().availableProcessors() zum Festlegen der Parallelebene verwendet.

• ForkJoinWorkerThreadFactory-Factory: ForkJoinPool wird beim Erstellen eines Threads über die Factory erstellt. Beachten Sie, dass hier ForkJoinWorkerThreadFactory und nicht ThreadFactory implementiert werden muss. Wenn Sie keine Factory angeben, ist die Standard-DefaultForkJoinWorkerThreadFactory für die Thread-Erstellung verantwortlich.

• UncaughtExceptionHandler: Geben Sie den Ausnahmehandler an, der vom Set-Handler behandelt wird boolean asyncMode: Legt den Arbeitsmodus der Warteschlange fest. Wenn asyncMode wahr ist, wird die First-In-First-Out-Warteschlange verwendet, und wenn es falsch ist, wird der Last-In-First-Out-Modus verwendet.

• Work-Stealing-Methode
  Im Fork-Join-Modus werden Aufgaben Arbeitsthreads in einem Thread-Pool zur Ausführung zugewiesen. Wenn ein Arbeitsthread seine zugewiesenen Aufgaben abschließt, kann er Aufgaben aus den Aufgabenwarteschlangen anderer Arbeitsthreads zur Ausführung stehlen. Dies wird als Arbeitsdiebstahl bezeichnet.

Verwenden Sie

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

Das obige ist der detaillierte Inhalt vonSo wenden Sie ForkJoin an, die Java-Divide-and-Conquer-Idee. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!