자바 병렬 프로 그래 밍-병렬 병합 정렬
34242 단어 Java
정렬 을 합치 면 모두 가 낯 설 지 않 을 것 이다.이것 은 우리 가 정렬 알고리즘 과 분 치 법 을 배 우 는 좋 은 예 이다.이것 은 안정 적 인 정렬 이 고 안정 적 인 O(n l o g n)O(nlogn)O(nlogn)시간 복잡 도 를 가 지 며 데이터 혼란 도 에 영향 을 받 지 않 습 니 다.유일한 부족 은 O(n)O(n)O(n)의 보조 공간 이 필요 하 다 는 것 이다.따라서 병합 정렬 은 종합 성능 이 가장 좋 은 정렬 알고리즘 으로 여 겨 진다.
우선 배열 을 반 으로 나 누 자.그 다음 에 이 두 부분 을 각각 재 귀적 으로 정리 하고 순 서 를 매 긴 다.마지막 으로 이 두 배열 의 배열 을 질서 있 게 합 쳤 다.그래서 대체로 이렇게 쓸 수 있다.(자바 로)
public void mergeSort(int[] arr, int l, int r) {
final int len = r - l;
if (len <= 0) {
return;
} else if (len == 1) {
if (arr[l] > arr[r]) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
return;
} //
final int mid = l + (len >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, mid + 1, r);
}
그 중에서 merge 는 합병 함수 로 두 개의 질서 있 는 배열(여기 서 하나의 배열 에서 서로 겹 치지 않 는 두 단락 으로 표시)을 질서 있 는 배열 로 합 친다.코드 는 다음 과 같 습 니 다:
private void merge(int[] arr, int l1, int r1, int l2, int r2) {
int i = l1, j = l2, k = left;
while (i <= r1 && j <= r2) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (j <= r2) {
tmp[k++] = arr[j++];
}
while (i <= r1) {
tmp[k++] = arr[i++];
}
for (i = 0; i < k - left; i++) {
arr[i + l1] = tmp[i + left];
}
}
우 리 는 병합 정렬 에 두 개의 재 귀 호출 이 있 는 것 을 보 았 다.이 두 개의 재 귀 호출 은'중첩 자 문제'가 없다.즉,서로 간섭 하지 않 고 진행 할 수 있다 는 것 이다.그래서 우 리 는 자 연 스 럽 게 병행 프레임 워 크 로 두 개의 문 제 를 병행 하여 해결 하면 속 도 를 더욱 높 일 수 있다 고 생각한다.
2.자바 병렬 프로 그래 밍 프레임 워 크
자바 에서 병행 프로 그래 밍 은 두 가지 방법 이 있 는데 하 나 는 스 레 드 와 스 레 드 풀 을 빌 리 는 것 이 고 다른 하 나 는 병렬 프레임 워 크
ForkJoinTask를 빌 리 는 것 이다.우리 각자 생각해 보 자.스 레 드 를 빌 리 면 두 개의 배열 이 정렬 되 는 병행 과 두 개의 배열 이 정렬 된 후에 합 쳐 지 는 문 제 를 처리 해 야 합 니 다.전 자 는 결코 어렵 지 않 고,중점 은 후자 에 있다.어떤 하위 배열 이 정렬 이 끝나 지 않 고 merge 작업 을 시작 하면 정확 한 결 과 를 얻 지 못 합 니 다.merge 는 두 개의 키 배열 이 모두 질서 있 는 큰 전제 에서 세 워 졌 기 때문이다.동기 화 문 제 를 고려 해 야 합 니 다.이것 은 신 호 량 등의 조작 을 빌려 야 하기 때문에 비교적 번거롭다.
한편,병합 정렬 과 같은 문제 에 대해 자바 는 두 개의 매우 적합 한 프레임 워 크 를 제공 했다.각각
ForkJoinTask과ForkJoinPool이다.전 자 는 병행 이 필요 한 작업 을 정의 하 는 데 사용 되 고 후 자 는 병행 에 필요 한 스 레 드 풀 을 제공 합 니 다.ForkJoinTask는 병행 문 제 를 처리 하 는 인터페이스 로 두 가지 추상 적 인 유형 이 이 를 실현 했다.하 나 는RecursiveTask이 고 하 나 는RecursiveAction이 며 각각 결과(결과 유형 은 T)와 결과 가 없 는 병행 문 제 를 처리 했다.우리 의 병합 정렬 은 결 과 를 되 돌려 줄 필요 가 없고 제자리 정렬 이 므 로RecursiveAction을 사용 합 니 다.3.
RecursiveAction상세 한 설명RecursiveAction를 사용 하려 면 하나의 클래스 로 계승 해 야 합 니 다.이 클래스 는 구체 적 인 병행 임 무 를 정의 합 니 다.우리 의 병행 임 무 는ParallelMergeSort이 라 고 한다.주의RecursiveAction는 추상 적 인 유형 으로 추상 적 인 방법compute이 있 는데 이 를 계승 하 는 유형 은 반드시 이 추상 적 인 방법 을 실현 해 야 한다.이compute방법 은 바로 병행 작업 의 실행 코드 입 니 다.우 리 는 먼저 병렬 작업 을 호출 하 는 방법 을 봅 니 다.호출 할 때 start 나 fork 등 방법 을 직접 사용 할 수 없습니다.병렬 작업 의 실행 은 메 인 스 레 드 가 아니 라 온라인 스 레 드 에서 제공 하 는 스 레 드 이기 때문에 작업 이 완료 되 었 는 지 알 수 없습니다.
걱정 하지 마 세 요.자바 는 또 다른 차단 식 작 동 방법 을 제공 합 니 다.
invoke라 고 합 니 다.이것 은ForkJoinPool의 한 구성원 방법 으로 병렬 작업 을 시작 하고 메 인 스 레 드 를 막 으 며 모든 작업 이 끝 난 후에 메 인 스 레 드 를 깨 우 는 것 을 나타 낸다.그래서 우 리 는 이렇게 쓸 수 있다.ParallelMergeSort task = new ParallelMergeSort(...); //
ForkJoinPool pool = new ForkJoinPool(); //
pool.invoke(task); //
그리고 병렬 작업
ParallelMergeSort의 정 의 를 봅 니 다.우선,질서 있 는 배열 의 합병 함 수 는 완전히 같다.두 개의 하위 배열 의 정렬 을 어떻게 병행 하 느 냐 가 중요 하 다.그래서 우 리 는 배열 의 정렬 구간 을 제공 해 야 한다.import java.util.concurrent.RecursiveAction;
public class ParallelMergeSort extends RecursiveAction {
private final int[] arr; //
private final int left; //
private final int right; // 。 。
private final int min; // min max
private final int max;
private final int[] tmp; // tmp ，
public ParallelMergeSort(int[] arr, int left, int right,
int min, int max, int[] tmp) {
this.min = min;
this.max = max;
this.tmp = tmp;
if (arr == null) {
throw new NullPointerException();
} else if (left > right) {
throw new IndexOutOfBoundsException();
}
this.arr = arr;
this.left = left;
this.right = right;
}
private void merge(int[] arr, int l1, int r1, int l2, int r2) {
int i = l1, j = l2, k = left; // 1： k left 0？
while (i <= r1 && j <= r2) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (j <= r2) {
tmp[k++] = arr[j++];
}
while (i <= r1) {
tmp[k++] = arr[i++];
}
for (i = 0; i < k - left; i++) {
arr[i + l1] = tmp[i + left];
}
}
public void mergeSort(int[] arr, int l, int r) {
// 2：
final int len = r - l;
if (len <= 0) {
return;
} else if (len == 1) {
if (arr[l] > arr[r]) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
return;
}
final int mid = l + (len >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, mid + 1, r);
}
@Override
protected void compute() { //
final int len = right - left;
if (len < 50 || (len + 1) << 4 <= max - min + 1) {
mergeSort(arr, left, right);
return;
} // ，
final int mid = left + (len >> 1);
ParallelMergeSort leftTask =
new ParallelMergeSort(arr, left, mid, min, max, tmp);
ParallelMergeSort rightTask =
new ParallelMergeSort(arr, mid + 1, right, min, max, tmp);
invokeAll(leftTask, rightTask); // ，
merge(arr, left, mid, mid + 1, right);
}
}
이 코드 는 이해 하기 어렵 지 않 지만 코드 에 주석 이 있 는 것 처럼 두 가지 의문 이 있 습 니 다.하 나 는 왜 일반 병합 정렬 함 수 를 유지 해 야 하 는 지,하 나 는 merge 함수 에서 tmp 배열 이 왜 left 부터 저장 해 야 하 는 지 입 니 다.
사실은 결국 병행 하기 때문이다.누가 쓸데없는 소리 아니 라 고 했 어,에이,정말 쓸데없는 소리 아니 야.
나 는 compute 함수 의 주석 에 배열 의 규모 가 너무 작 거나 스 레 드 가 너무 많이 열 리 면 일반 병합 정렬 으로 바 꾸 기 때문에 일반 병합 정렬 함 수 를 유지 해 야 한다 고 썼 다.
그리고 merge 함수 에서 left 부터 시작 하 는 문제 입 니 다.우 리 는 공간 을 절약 하기 위해 항상 같은 tmp 배열 을 사용 하고 그의 진정한 내용 은 구조 적 방법 으로 들 어 옵 니 다.작업 중,모든 하위 작업 은 tmp 배열 을 사용 해 야 합 니 다.병합 작업 이 0 에서 시작 되면 하위 작업 의 병행 으로 인해 tmp 와 같은 위치 에 있 는 요 소 는 서로 다른 스 레 드 에 의 해 공유 되 어 병합 작업 이 혼 란 스 러 울 수 있 습 니 다(스 레 드 안전 문제).따라서 하위 작업 에 사용 되 는 tmp 배열 구간 이 서로 겹 치지 않도록 해 야 합 니 다.left 를 사용 하면 tmp 와 원래 배열 의 위치 가 일일이 대응 하도록 확보 하여 스 레 드 안전 문 제 를 피 할 수 있 습 니 다.
이 두 가 지 는 가장 이해 하기 어 려 운 것 이다.이 두 가 지 를 이해 하면 남 은 일 은 도랑 에 이 르 는 것 이다.
마지막 으로 병행 정도 의 문 제 를 고려 해 보 자.스 레 드 가 많 을 수록 운행 속도 가 빠 르 지 않 습 니까?아 닙 니 다.스 레 드 는 사용자 스 레 드 와 하드웨어 스 레 드 두 가지 로 나 뉘 기 때문이다.전 자 는 논리 적 인 스 레 드 일 뿐 후 자 는 CPU 에서 병행 을 진정 으로 지원 하 는 것 이다.우리 의 CPU 는 항상'4 핵 8 스 레 드'라 고 말 하 는데 이것 은 네 개의 독립 된 계산 단원 과 8 개의 진정한 병행 을 지원 하 는 임 무 를 말한다.다른 논리 스 레 드 는 병행 이 아니 라 병행 일 뿐이다.그리고 일반 운영 체 제 는 두 개의 스 레 드 를 장기 적 으로 점용 해 야 하고 나머지 6 개의 스 레 드 가 야 말로 프로그램 에서 사용 할 수 있다.프로그램 표면 에 몇 개의 스 레 드 를 열 었 든 지 간 에 최대 6 개의 스 레 드 만 이 진정 으로 병행 한다.
또한 스 레 드 를 열 려 면 대량의 운영 체제 자원 을 점용 해 야 한다.만약 에 스 레 드 가 너무 많이 열 리 면 시간 공간 소 모 는 매우 상당 하 다.만약 에 스 레 드 자체 의 부정적인 영향 이 상쇄 되 고 심지어 병행 이 가 져 온 장점 을 초과 하면 병행 을 사용 하 는 것 은 의미 가 없다.
그리고 우리 위의 코드 에 따 르 면 병렬 작업 수량 은 대체적으로 재 귀 층수 와 지수 관계(k 층 으로 재 귀 하면 약 2k 2^k 2k 개의 병렬 작업)가 있 습 니 다.따라서 우 리 는 3-5 층 으로 돌아 가 일반 병합 정렬 으로 바 꿔 야 한다.그래서 compute 함수 에 이런 특 판 이 있 습 니 다.
if (len < 50 || (len + 1) << 4 <= max - min + 1) {
mergeSort(arr, left, right);
return;
}
테스트 에 따 르 면 8-32 개의 병렬 작업 을 유지 할 때 가장 빨리 실 행 됩 니 다.
4.테스트 와 효율 분석
시간 단 위 는 모두 밀리초 이다.CPU corei5-7200,쿼 드 8 스 레 드,운영 체제 win 10 64bit,jdk 1.8
정렬 규모
MergeSort 시간
병렬 MergeSort 시간
가속 비
1000
2
2
1.000
5000
2
10
0.200
10000
4
15
0.267
50000
18
18
1.000
100000
32
16
2.000
500000
108
50
2.160
1000000
218
90
2.422
5000000
960
550
1.745
10000000
2100
950
2.211
30000000
6200
2520
2.460
이 를 통 해 알 수 있 듯 이 규모 가 시간 에 비해 병행 여부 의 영향 이 크 지 않 고 스 레 드 를 열 려 면 시간 공간 을 소모 해 야 하기 때문에 일반 병합 보다 정렬 이 느리다.그러나 규모 가 크 면 차이 가 나 고 병행 버 전의 속 도 는 일반 버 전의 2~3 배 에 이른다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
