아래 내용들은 저의 개인적인 경험에 따른 가정과 추측에 대한 내용입니다.
틀린 내용이 당연히 있을 수 있으며 어떠한 피드백이라도 감사히 잘 받겠습니다.
개요
전체 정렬은 알고리즘으로 분류되고 우선순위 큐는 자료구조로 분류됩니다.
이 둘을 직접적으로 비교하면 와닿지 않을 수 있으니 상황을 예로 들겠습니다.
n 은 i 조건을 따르는 임의의 수 50개로 이루어져 있습니다. (0 < i < 100)
그리고 n 에서 내림차순으로 10 개의 수를 뽑아내야합니다.
정렬 알고리즘 접근법
전체 정렬 알고리즘으로 이 문제를 접근한다면 n 의 전체 원소를 정렬한 뒤에 내림차순으로 원소를 접근할 것입니다.
우선순위 큐
우선순위 큐로 이 문제를 접근한다면 n 의 전체 원소를 우선순위 큐라는 자료구조에 다시 담은 뒤 peek 값을 원하는 수만큼 추출해낼 것입니다.
정렬 알고리즘 시간복잡도
모든 원소를 정렬하게 되니 O(|n| * lg|n|) 의 시간복잡도로 정렬을 수행하고 내림차순으로 원소에 접근할 땐 O(1) 의 시간복잡도로 수행할 것입니다.
우선순위 큐 시간복잡도
모든 원소에 접근해 우선순위 큐를 새롭게 형성하니 O(|n| * lg|n|) 의 시간복잡도가 소요될 것입니다. 그리고 내림차순으로 원소에 접근할 땐 O(lg|n|) 의 시간복잡도가 소요될 것입니다.
정리 표
| 정렬 | 우선순위 큐 | |
|---|---|---|
| 형성 비용 | O(lg|N|) | O(lg|N|) |
| 최고값 접근 비용 | O(1) | O(lg|N|) |
착각
이렇게 시간복잡도로만 보면 해당 문제를 해결할 땐 정렬을 사용하는게
늘 합리적여 보입니다. 형성 비용은 정렬, 우선순위 큐가 동일하며 접근할 땐 정렬이 더 뛰어난 성능을 보이니 말이죠.
이게 오늘 새벽까지 제가 가지고 있던 착각과 오해였습니다.
PS 에 빠져살다보니 로직의 성능 평가에 있어 Big O notation 이 절대적인 평가수치라고 생각했습니다.
이런 저의 기대를 져버리고 우선순위 큐가 훨씬 높은 성능을 보여준 문제가 있었습니다.
이 문제는 전체적으로 봤을땐 제가 위에서 가정한 문제와 같은 흐름이지만
입력 조건에서 차이가 발생합니다.
n의 개수가 최대 10^6 이며 뽑아내는 수의 개수는 최대 10^4 입니다.
n의 크기가 10^6 으로 상당히 큽니다.
처음에 이 문제를 해결할 땐 정렬을 이용해서 해결하려 했습니다만 최적화 문제에서 실패했습니다. 저는 무엇이 문제인지 갈피를 잡기 힘들었습니다.
-
첫 해결 시도
Collections 클래스의 클래스 자료구조 (List) 에서 Native Array (int[]) 로 변경하며 오버헤드를 줄여 재시도 해봤지만 메모리 사용량만 감소하고 시간 성능에선 오히려 나쁜 경향을 보였습니다. (이것도 참 의외였습니다.) -
두 번째 해결 시도
처음 Collections 클래스의 클래스 자료구조를 다시 사용하며 sort 의 custom Comparator 로 커스텀 비교함수가 아닌 Comparator 에서 제공되는 비교 메소드의 레퍼런스를 통해 처리했습니다.
이렇게 하니 문제가 아슬아슬하게 통과 했습니다.
하지만 일반적으로 PS 문제에서 이러한 컴파일러 최적화 수준의 요소를 다루진 않습니다.
좀 더 근본적인 문제를 해결할 필요가 있었습니다.
그러던 중 이 문제를 우선순위 큐로 해결해보면 어떨까 하는 생각이 들었습니다.
그렇게 우선순위 큐로 대체해봤는데 정말 확연한 성능차이를 보였습니다.
이러한 결과를 보고 몇몇 가설을 세우며 접근했습니다.
그 결과 Big O Notation 의 시간복잡도 만으로는 다 나타나지 않는 무언가가 존재한다는 것입니다.
-
첫 번째 가설
그 첫 번째가 정렬의 경우 접근할지 안할지에 대한 모든 원소들을 정렬한다는 점입니다. 그리고 우선순위 큐의 경우 형성 시에 매번 모든 원소들을 다루지 않고 국소적으로 일부의 원소에 접근한다는 점입니다. 이러한 성향 때문에 우선순위 큐가 상대적으로 더 적은 작업을 한다 추측합니다. -
두 번째 가설
두 번째는 이러한 국소적인 성향 때문에 캐시 지역성의 혜택을 더 누릴 수 있다는 추측입니다.
이게 어디까지나 추측이고 시각적으로 풀어내지도 않아 설득력이 많이 낮을 것 같습니다만 저에게 n 이 주어졌을 때 이걸 배열로 해결하는 과정을 그려내라 할 때와 이걸 우선순위 큐로 해결하는 과정을 그려내라 할 때 후자를 좀 더 수월히 그리고 빠르게 해결할 수 있지 않을까 생각합니다.
중간 결론을 내리자면 우선순위 큐는 전체 정렬 보다 최대, 최소값을 구한다는 점에서 Lazy 한 성향을 가진 자료구조라 생각합니다.
결론
시간 복잡도 만으로 다 드러나지 않는 무언가가 있다는건 잘 알았습니다.
그럼 언제 우선순위 큐를 써야하고 언제 전체 정렬을 써야할까요?
다음과 같이 정리했습니다.
근거 없는 수치이지만 |n| <= 10^4 수준이라면 뭘 써도 상관이 없을 것 같습니다. 이러한 조건이라면 언어적으로 지원을 더 잘 받는 배열계 자료구조와 정렬을 사용할 것입니다.
하지만 |n| 이 그 이상이라면 문제의 성향에 따라 달라질 것입니다.
이번 문제처럼 매번 최대값을 추출해내는 문제라면 저는 우선순위 큐를 선택할 것 같습니다. 반드시 모든 원소에 접근한다는 가정이 있다면 정렬을 택할 듯 하지만 경우에 따라 몇 개의 원소에만 접근한다면 Lazy 하게 최대, 최소값에 접근하는 우선순위 큐를 택할 것 입니다.
그 외의 상황이라면 배열계 자료구조와 정렬을 택할 것 같습니다.
Two Pointer 와 Binary Search 등을 활용해야하는 문제라면 더욱 더 말입니다.
그 외
TreeMap 으로도 시도해보고 싶네요.
다른 해결책으론 10^4 만큼 정수형 배열을 만든 다음
가격을 인덱스로 무게들을 더해 최종적으로는 내림차순으로 인덱스를 접근해 최적의 값을 구할 수도 있을 것 같습니다. 이 경우 O(|n|) 으로 문제를 해결할 수 있을 것 같아 정해가 아닐까 생각합니다.
