Java 분할 정복 아이디어 ForkJoin 적용 방법
- PHPz앞으로
- 2023-05-12 21:16:04873검색
분할 정복 알고리즘
포크 조인 모드는 분할 정복 아이디어를 기반으로 한 병렬 컴퓨팅 모드 중 하나입니다. 이 모드는 큰 작업을 여러 개의 작은 하위 작업으로 나눈 다음 이러한 하위 작업을 병렬로 실행하고 마지막으로 결과를 병합하여 최종 결과를 얻습니다. 이 프로세스에서 각 하위 작업의 실행은 특정 임계값에 도달할 때까지 더 작은 하위 작업으로 분해될 수 있으며, 이때 작업은 순차적으로 실행됩니다. 이러한 재귀적인 분할 정복 아이디어를 통해 포크 조인 모드는 컴퓨터의 멀티 코어 처리 기능을 효과적으로 활용하여 프로그램 성능과 효율성을 향상시킬 수 있습니다.
Merge sort
Merge sort는 분할 정복 아이디어를 기반으로 한 정렬 알고리즘입니다. 핵심 아이디어는 배열을 두 개의 하위 배열로 나누고 별도로 정렬한 다음 병합하는 것입니다. 구체적인 구현 과정은 다음과 같습니다.
분해: 배열을 두 개의 하위 배열로 나누고 각각 정렬합니다. 이 단계는 재귀를 사용하여 수행할 수 있습니다.
병합: 두 개의 정렬된 하위 배열을 정렬된 배열로 병합합니다.
재귀: 각 하위 배열의 길이가 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
빠른 정렬(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(), waitTermination() 등과 같은 몇 가지 중요한 메서드가 포함되어 있습니다. 작업. ForkJoinPool 클래스에는 스레드 풀의 크기, 작업자 스레드의 우선 순위, 작업 대기열의 용량 등과 같은 일부 매개 변수도 포함되어 있으며 특정 응용 프로그램 시나리오에 따라 설정할 수 있습니다.
constructor
ForkJoinPool에는 네 가지 핵심 매개변수가 있는데, 이는 병렬 스레드 풀 수, 작업자 스레드 생성, 예외 처리 및 모드 지정을 제어하는 데 사용됩니다.
int 병렬성: 병렬성 수준을 지정합니다. ForkJoinPool은 이 설정에 따라 작업자 스레드 수를 결정합니다. 설정하지 않으면 Runtime.getRuntime().availableProcessors()를 사용하여 병렬 수준을 설정합니다.
ForkJoinWorkerThreadFactory 팩토리: ForkJoinPool은 스레드 생성 시 팩토리를 통해 생성됩니다. 여기서 구현해야 할 것은 ThreadFactory가 아닌 ForkJoinWorkerThreadFactory입니다. 팩토리를 지정하지 않으면 기본 DefaultForkJoinWorkerThreadFactory가 스레드 생성을 담당합니다.
UncaughtExceptionHandler 핸들러: 작업 중에 오류가 발생하면
예외 핸들러를 지정합니다. boolean asyncMode: 대기열의 작업 모드를 설정합니다. asyncMode가 true이면 선입선출(FIFO) 큐가 사용되고, false이면 후입선출(Last In First Out) 모드가 사용됩니다.
Work Stealing Method
Fork-Join 모드에서는 작업을 스레드 풀의 작업자 스레드에 할당하여 실행합니다. 작업자 스레드가 할당된 작업을 완료하면 실행을 위해 다른 작업자 스레드의 작업 큐에서 작업을 훔칠 수 있습니다. 이를 작업 훔치기(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 적용 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!