[JAVA8] 배열 Parallel 정렬

인프런 강의 "더 자바, JAVA8"(백기선님)의 강의를 듣고 정리한 글 입니다.
JAVA8에 추가된 핵심 기능들을 이해하기 쉽게 설명해 주시니 한번씩 들어보시는 것을 추천드립니다.

"더 자바, JAVA8 바로가기"

---

배열 Parallel 정렬

알고리즘의 효율이 바뀌지 않았지만, 여러 쓰레드가 분산해서 처리하기 때문에 조금 더 빠르게 정렬이 가능합니다.

Arrays.parallelSort()

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

병렬 알고리즘

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

sort() 와 parallelSort() 비교

• 알고리즘 효율성은 같다. 시간 O(n logN) 공간 O(n)

public class App {
    public static void main(String[] args) {
        int size = 200;
        System.out.println("size = " + size);
        int[] numbers = new int[size];
        Random random = new Random();
        IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());

        long start = System.nanoTime();
        Arrays.sort(numbers);
        long sort = System.nanoTime() - start;
        System.out.println("serial sorting took " + sort);

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

        if (sort > parallelSort) {
            System.out.println("parallelSort가 빠릅니다.");
        } else {
            System.out.println("sort가 빠릅니다.");
        }

    }
}

SIZE가 작으면 Arrays.sort() 가 더 빠르고 SIZE가 커지면 Arrays.parallelSort()가 더 빠르다고 합니다. 테스트를 해보겠습니다.

size = 200
serial sorting took 274500
parallel sorting took 413500
sort가 빠릅니다.

size = 2000
serial sorting took 1068300
parallel sorting took 1287000
sort가 빠릅니다.

size = 20000
serial sorting took 8228100
parallel sorting took 6857600
parallelSort가 빠릅니다.

size = 8000
serial sorting took 4376000
parallel sorting took 2936700
parallelSort가 빠릅니다.

size = 8000
serial sorting took 2624900
parallel sorting took 2626800
sort가 빠릅니다.

size가 8000을 넘어가면서 sort가 빠르기도 하고 parallel sort가 더 빨라지기도 하는 것을 확인할 수 있다.

결론

size가 작면 Arrays.sort()가 더 빠르고 size가 크면 Arrays.parallelSort()가 더 빠르다.