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