PriorityQueue에 대한 탐험 - Comparator, sort

필자의 블로그 [커리어리 글을 작성하는 것이 다소 익숙하지 않기에, 아래 블로그로 가면 가독성이 더욱 좋을 것 입니다.] https://blog.naver.com/PostView.naver?blogId=gomets_journey&logNo=223382682854&parentCategoryNo=&categoryNo=28&viewDate=&isShowPopularPosts=false&from=postList 백준(11286번, [절댓값 힙]) 문제를 풀기위해서 Heap(PriorityQueue) 자료구조와, Comparator를 이용하여야 했다. 그러면서 한 번 이들에 내부 코드가 궁금해졌기에 포스팅해보려고 한다. 그 전에 우선 Heap 자료구조가 무엇인지부터 알아보자. Heap은 특정한 형태의 이진트리로 구현된 자료구조이다. 이진트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조를 의미한다. Heap은 주로 우선순위 큐(PriorityQueue)를 구현하는 데 사용되며, 최댓값 또는 최솟값을 빠르게 찾을 수 있도록 도와준다. Heap은 보통 최대 힙(max heap) 또는 최소 힙(min heap)으로 구성된다. * 최대 힙 * 각 노드의 값이 해당 자식 노드들의 값보다 크거나 같은 조건을 만족하는 트리 * 최소 힙 * 각 노드의 값이 해당 자식 노드들의 값보다 작거나 같은 조건을 만족하는 트리 Heap의 주요 연산은 다음과 같다. 1. 삽입 : 새로운 요소를 힙에 추가한다. 일반적으로 Heap의 끝에 요소를 추가하고, 추가된 요소를 Heap의 특성에 맞게 재조정한다. 2. 삭제 : 최대값 또는 최솟값을 제거한다. 삭제 후 Heap의 구조를 유지하기 위해 Heap을 재조정한다. 3. 최댓값 또는 최솟값 검색 : 최대 Heap에서는 루트 노드에 있는 값이 최대값이고, 최소 Heap에서는 최솟값이다. Heap은 일반적으로 배열을 이용하여 구현한다. 이진 Heap에서 각 노드는 배열의 Index와 일치하도록 저장된다. 루트 노드는 항상 배열의 첫 번째 요소에 위치하며, 자식 노드의 Index는 특정한 규칙에 따라 계산된다. (왼쪽 자식노드의 Index는 부모 노드의 Index*2+1 / 오른쪽 자식 노드의 Index는 부모 노드의 Index*2+2) Heap은 삽입, 삭제, 검색 연산이 모두 O(log n)의 시간 복잡도를 가지며, 정렬은 O(n log ㅜ)의 시간 복잡도를 가진다. 자 이제 Heap이 무엇인지에 대해서 개념을 알아보았다. 하지만 글로만으로는 이해가 힘들 것이다. 개발자는 역시 코드를 통해 살펴보아야 한다. 자 이제 내부코드를 탐방해보자 내부 코드를 들어가보면 위 문서가 우리를 반겨준다. 이 문서 중에서 우리에게 필요한 부분만을 뽑아보자 1. 우선순위 큐의 요소들은 자연 순서에 따라 정렬되거나, 큐 생성 시 제공된 Comparator에 따라 정렬된다. 이때 null 요소의 삽입을 허용하지 않는다. 2. 여러 요소가 동일한 값을 가질 경우 무작위로 선택한다. 큐의 검색 연산인 poll, remove, peek 및 element는 큐의 head에 있는 요소에 접근한다. 3. 우선순위 큐는 크기에 제한이 없지만, 요소를 저장하는 데 사용되는 배열의 크기를 제한한다. 이 배열은 항상 큐의 크기보다 크거나 같다. 요소가 우선순위 큐에 추가됨에 따라, 내부 용량은 자동으로 증가한다. 4. 메서드 interator()에서 제공된 iterator 및 메서드 spliterator()에서 제공된 Spliterator는 우선순위 큐의 요소를 특정한 순서로 순회할 것을 보장하지 않는다. 순서화된 순회가 필요할 경우 Arrays.sort(pq.toArray())를 사용할 수 있다. 5. 이 구현은 동기화되지 않았다. 여러 스레드가 큐를 수정할 경우, PriorityQueue 인스턴스에 동시에 액세스해서는 안 된다. 즉 멀티스레딩 환경에서 사용에 주의를 해야한다. 6. 멀티스레딩 환경에서는 스레드 안전한 java.util.concurrent.PriorityBlockingQueue 클래스를 사용하라. 자 이제 이 문서에 따라 우리가 알아보아야 할 메서드가 정해진 것 같다. Comparator부터 알아보도록 하자. Comparator의 메서드를 보면 크게 3가지로 나타낼 수 있을 것 같다. 1. compare 메서드 2. reversed 메서드 3. thenComparing 메서드 우선 compare 메서드 부터 살펴보자 Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. The implementor must ensure that signum(compare(x, y)) == -signum(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.) The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0. Finally, the implementor must ensure that compare(x, y)==0 implies that signum(compare(x, z))==signum(compare(y, z)) for all z. Params: o1 – the first object to be compared. o2 – the second object to be compared. Returns: a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. Throws: NullPointerException – if an argument is null and this comparator does not permit null arguments ClassCastException – if the arguments' types prevent them from being compared by this comparator. API Note: It is generally the case, but not strictly required that (compare(x, y)==0) == (x.equals(y)). Generally speaking, any comparator that violates this condition should clearly indicate this fact. The recommended language is "Note: this comparator imposes orderings that are inconsistent with equals." 들어가면 위의 문서만 볼 수 있고 compare의 내부코드는 볼 수가 없었다. 우선 위 문서부터 중요한 내용을 뽑아보자. 1. 이 메서드는 두 인자를 순서대로 비교한다. 2. 매개변수 = o1 : 비교할 첫 번째 객체이다. / o2 : 비교할 두 번째 객체이다. 3. 반환값 = 첫 번째 인자가 두 번째 인자보다 작으면 음수, 같으면 0, 크면 양수를 반환한다. 그래서 아마 내 개인적인 견해로는 단순하게 아래와 같이 구현되었을 것 같다. public class IntegerComparator implements Comparator { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; } } 하지만 한 가지 흥미로운 점을 알게되었는데, List.sort 메서드는 Comparator 객체를 사용하여 리스트의 요소를 정렬한다는 것이다. List.sort의 내부 코드 default void sort(Comparator c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ListIterator i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } } 이 코드들을 살펴봐보자 1. 리스트의 요소들을 배열로 변환한다. (앞서 설명한 toArray 메서드를 호출하여 배열로 변환) 2. 'Arrays.sort' 메서드를 사용하여 배열을 주어진 'Comparator' 객체('c')를 사용하여 정렬 3. 정렬된 배열의 요소들을 다시 리스트에 설정한다. 이때, 'ListIterator'를 사용하여 리스트의 요소를 반복하면서 배열의 각 요소를 대응하는 리스트 요소로 설정 우리는 앞서 toArray 메서드와 Iterator 메서드에 대해서 살펴보았다. 이제 한 번 sort 메서드를 살펴봐보자 Arrays.sort의 내부 코드 public static void sort(T[] a, Comparator c) { if (c == null) { sort(a); } else { if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else TimSort.sort(a, 0, a.length, c, null, 0, 0); } } 1. 'c'가 null인지 확인한다. 만약 null이라면, 기본 정렬 기준에 따라 배열을 정렬한다. ('sort(T[ ] a)'를 호출하여 기본 정렬을 수행) 2. 그렇지 않은 경우, 'LegacyMergeSort.userRequested' 값이 'true'인지 확인한다. 이 값이 true라면, 'legacyMergeSort' 메서드를 사용하여 배열을 정렬한다. 3. 만약 LegacyMergeSort.userRequested' 값이 'false'라면, 'TimeSort.sort' 메서드를 사용하여 배열을 정렬한다. 우선 먼저 기본 정렬 기준이 무엇인지 부터 알아봐보자 Java의 기본 정렬 기준 Java의 기본 정렬 기준은 객체의 자연 순서에 따라 정렬된다. 이 자연 순서는 객체가 'Comparable' 인터페이스를 구현하고 'compareTo' 메서드를 제공하는 경우에 사용된다. public int compareTo(T o); 1. 현재의 객체가 'o'보다 작으면 음수를 반환 2. 현재 객체가 'o'와 같으면 0을 반환 3. 현재 객체가 'o'보다 크면 양수를 반환 우리는 이를 통해 한 가지 사실을 알게되었다. 'Arrays.sort()' 또는 'Collections.sort()' 메서드를 사용할 때 Comparator가 null인 경우 즉, Comparator 기준이 없을 때 기본적으로 객체의 'compareTo' 메서드에 따라 정렬된다. LegacyMergeSort.userRequested 우리는 앞서 'LegacyMergeSort.userRequested' 값이 'true'일 경우 MergeSort 즉 병합정렬을 한다는 것을 알았는데 그렇다면 userRequested는 무엇일까? LegacyMergeSort의 내부코드 static final class LegacyMergeSort { @SuppressWarnings("removal") private static final boolean userRequested = java.security.AccessController.doPrivileged( new sun.security.action.GetBooleanAction( "java.util.Arrays.useLegacyMergeSort")).booleanValue(); } 'userRequested'라는 정적 필드는 'java.security.AccessController.doPrivileged' 메서드를 사용하여 시스템 속성 "java.util.Arrays.useLegacyMergeSort"의 값을 읽어와 초기화한다. 이 속성은 레거시 머지 소트 알고리즘을 사용할 것인지 여부를 결정한다. 이때 'doPrivileged' 메서드는 시스템 속성을 읽기 위해 특권 작업을 수행하는 데 사용한다. 이렇게 하면 보안 정책의 제한을 우회할 수 있다. 여기서는 "java.util.Arrays.useLegacyMergeSort" 시스템 속성의 값을 읽어올 때 이 특권을 사용한다. 이를 통해 우리는 이렇게 유추해 볼 수 있을 것 같다. LegacyMergeSort는 이전 버전의 Java에서 사용되던 알고리즘이고, 지금은 더욱 향상된 알고리즘이 사용되는구나, 다만 Java의 특성상 이전 버전과의 호환성을 유지하기 위해 이 레거시 알고리즘을 사용하고 있구나. 그렇다면 향상된 알고리즘은 'TimeSort.sort' 메서드이고 이것이 주로 사용되는구나. 자 이제 마지막으로 sort 메서드에서 'Comparator.compare'가 null이 아닐 때, 즉 compare 기준이 정해질 때 주로 사용되는 TimeSort 알고리즘에 대해서 살펴보자 TimeSort.sort TimeSort 'TimeSort'는 Java의 정렬 알고리즘 중 하나로 2009년 자바 7부터 기본 정렬 알고리즘으로 사용되었다. 이 알고리즘은 삽입 정렬과 적응형 병합 정렬의 조합으로 구현되어 있다. * 최악의 경우에도 'TimeSort'는 O(n log n)의 시간 복잡도를 보장한다. * 'TimeSort'는 입력 배열을 작은 조각으로 나누어 삽입 정렬을 수행한 다음, 이러한 조각들을 병합 정렬을 사용하여 병합한다. * 'TimeSort'에서는 배열을 여러 개의 작은 블록으로 나누는데, 이러한 블록을 run이라고 한다. 보통 run의 크기는 32 ~ 64 사이의 값이 사용되나, 입력 배열의 크기와 같은 다양한 요인에 따라 결정된다. static void sort(T[] a, int lo, int hi, Comparator c, T[] work, int workBase, int workLen) { assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted // If array is small, do a "mini-TimSort" with no merges if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi, c); binarySort(a, lo, hi, lo + initRunLen, c); return; } 위 코드는 TimeSort.sort 메서드의 내부 코드이다. 한 번 살펴보도록 하자 1. 먼저 입력이 유효한지 확인하기 위해 assert 문을 사용한다. c가 null이 아니고, a가 null이 아니며, lo가 0보다 크거나 같고, hi가 배열의 길이보다 작거나 같아야 한다. 2. nRemaining 변수를 사용하여 정렬해야 할 배열의 요소 수를 계산한다. 3. 만약 정렬해야 할 요소의 수가 MIN_MERGE보다 작다면, 'mini-TimeSort'를 수행한다. 이는 배열의 작은 부분에 대해 삽입 정렬을 수행하는 것으로, 병합 단계는 생략된다. 이는 일종의 최적화 기법으로, 작은 크기의 배열에 대해 불필요한 병합 단계를 피하기 위함이다. 4. MIN_MERGE는 상수로 정의 되어 있다. 즉 작은 크기의 배열에 대해 삽입 정렬을 사용하고 큰 크기의 배열에 대해서는 TimeSort 알고리즘을 적용한다. 이를 통해 우리는 우리는 왜 Heap 자료구조의 (PriorityQueue를 포함하여) 정렬 시간 복잡도가 O(n log n)인지를 알 수 있게 되었다. 또한 어떤 정렬 알고리즘이 이용되는지도 알 수 있었다.