배열 병렬 정렬

목차

• 배열 병렬 정렬
  • 1. Arrays.parallelSort()
  • 2. 병렬 정렬 알고리즘
  • 3. sort()와 parallelSort() 비교

1. Arrays.parallelSort()

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

2. 병렬 정렬 알고리즘

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

3. sort()와 parallelSort() 비교

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

단, 정렬하는 배열의 크기에따라 속도가 차이날 수 있다.

public class App {
	public static void main(@Chicken String[] args) {
		int size = 1500;
		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);
		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));
	}
}

serial sorting took 1127801
parallel sorting took 612500

참고

size가 15000일 때 나오는 속도

serial sorting took 5023800
parallel sorting took 14654200

Arrays.sort()

• Arrays.sort() 알고리즘은 기본적으로 DualPivotQuicksort를 사용한다.

이 알고리즘은 기본적으로

1. Insertion Sort
2. Merge Sort
3. Quick Sort

위 3개의 알고리즘을 사용하는데 보통 1,2, 1,3을 섞어서 사용한다.

Arrays.parallelSort()

• 반면 Arrays.parallelSort() 는 Merge Sort를 사용함.

• in-place 정렬이 아니기 때문에 배열이 커지면 느려질 수 밖에 없다.
• 자세한 내용은 여길 참고하자 (opens new window)

Meta space

JVM의 여러 메모리 영역 중에 PermGen 메모리 영역이 없어지고 Metaspace 영역이 생겼다.

1. PermGen

• 메모리 구조

  

🔼출처 (opens new window)

• permanent generation**, 클래스 메타데이터**를 담는 곳.
• Heap 영역에 속함.
• 기본값으로 제한된 크기를 가지고 있음.
  • 동적으로 클래스를 생성하는 경우 PermGen 영역이 가득 차는 경우가 발생할 수 있다. 메모리 에러 발생.
  • 위의 문제를 근본적으로 해결하려면 PermGen 사이즈를 늘리는 것이아니라 클래스를 동적으로 생성하는 코드를 수정해야한다.
• XX:PermSize=N, PermGen 초기 사이즈 설정
• XX:MaxPermSize=N, PermGen 최대 사이즈 설정