자바 배열 정렬(Java Array Sort) - 정렬(Arrays.sort), 병렬 정렬(Arrays.parallelSort) 비교

Arrays.parallelSort()

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

• 특정 조건이 충족 될 때만 병렬 처리를 사용한다.
  • 배열 크기가 8192보다 작거나 같거나 프로세서에 코어가 하나만 있는 경우 Arrays.sort()와 같은 Dual-Pivot Quicksort 알고리즘을 사용한다.
  • 위의 조건이 아니라면 병렬 정렬을 사용

 

병렬 정렬 알고리즘

• 배열을 둘로 계속 쪼갠다.

• 합치면서 정렬한다.

 

sort()와 parallelSort() 비교

public class Main {
	public static void main(String[] args) {
        int size = 1500;
        int[] numbers = new int[size];
        Random random = new Random();
        IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());
        //일반 정렬 시간 측정(쓰레드 1개 사용)
        long start = System.nanoTime();
        Arrays.sort(numbers); // Dual-Pivot Quicksort 사용
        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); //배열을 쪼개면서 하위 배열 길이가 최소 단위에 도달하면 합치면서 정렬(Arrays.sort 사용)
        System.out.println("parallel sorting took " + (System.nanoTime() - start));
    }
}

• 일반 정렬(sort())
  • 더 작은 데이터 세트에서 빠르게 작동
  • 대용량 데이터 세트의 성능 저하
  • 시스템의 다중 코어 미활용

• 병렬 정렬(parallelSort())
  • 더 작은 크기 배열의 경우 더 느림
  • 대규모 데이터 세트에 대해 더 나은 성능 제공
  • 시스템의 다중 코어 활용

• 대규모 데이터 정렬에서는 병렬 정렬이 좋은 선택이 될 수 있고 작은 크기의 배열에서는 오히려 일반 정렬이 성능이 좋을 수 있다.
  • serial sorting took 548957
  • parallel sorting took 364074

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

---

[참고자료]

더 자바, Java 8, 백기선

Arrays.sort vs Arrays.parallelSort