배열 병렬 정렬

자바 8 이전에 사용했던 배열 정렬 클래스

알고리즘 문제를 풀 때 정렬하는 문제는 빈번하게 출제된다.

배열 정렬 문제를 풀 때는 항상 Arrays.sort()를 이용했다.

너무 간단했기 때문에 사용했다. 하지만 Arrays.sort()가 어떤식으로 동작하는지 모르는데 쓰는 것이 내 마음에 걸렸다.

그래서 Arrays.sort() 내부를 보았다.

Arrays.sort()의 내부

Implementation note에 제작자, 알고리즘 설명, 시간복잡도 등 알려 준다.

• 제작자 : Vladimir Yaroslavskiy, Jon Bentley, Joshua Bloch
• 알고리즘 : Dual-Pivot Quicksort (두 개의 피폿으로 퀵정렬)
• 간략한 설명 : 이 알고리즘은 다른 퀵소트가 2차 성능으로 저하되도록 하는 많은 데이터 세트에 대해 O(n log(n)) 성능을 제공하며 일반적으로 기존(1피벗) 퀵소트 구현보다 빠릅니다.
• 시간복잡도 : O(n log(n))

Dual-Pivot Quicksort 예시 간략히 이렇게 된다고 한다.

그렇다면….

자바8 에서는 어떤 배열 정렬이 나왔을까 ??

Arrays.parallelSort() 라는 것이 나왔다!!

이것은

• Fork/Join 프레임워크를 사용해서 배열을 병렬로 정렬하는 기능을 제공한다고 한다.

병렬 정렬 알고리즘

• 배열을 둘로 계속 쪼갠다.
• 합치면서 정렬한다.

Arrays.parallelSort() 의 내부

이런식의 알고리즘이라고한다.

Arrays.sort() vs Arrays.parallelSort()

nanoTime()을 이용해서

public class배열_병렬_정렬{

publicstaticvoidmain(String[]args) {
intsize = 5000;
int[] numbers =new int[size];

Randomrandom =newRandom();
IntStream.range(0, size).forEach(i-> numbers[i] = random.nextInt());

longstart =System.nanoTime();
Arrays.sort(numbers);

System.out.println("serial sorting took :" + (System.nanoTime() - start));

IntStream.range(0,size).forEach(i->numbers[i] = random.nextInt());
        start =System.nanoTime();
Arrays.parallelSort(numbers);
System.out.println("parallel sorting took :" + (System.nanoTime() - start));

    }
}

배열의 size가 5000

• 결과

serial sorting took :2446833
parallel sorting took :1830958

배열의 size가 100

-결과

serial sorting took :197583
parallel sorting took :49167

성능 차이가 좀 많이난다.

참고 : 백기선 - The Java8

참고 : Java 8 | Arrays parallelSort() method with Examples

참고 : Dual pivot Quicksort