코딩테스트/알고리즘 정리
PriorityQueue(PQ) vs ArrayList(Collections.sort())
까루카라
2024. 10. 22. 11:57
PriorityQueue(PQ)는 내부적으로 힙 정렬을 사용 vs Collections.sort()는 내부적으로 TimeSort 사용
- 시간 복잡도:
- 힙 정렬: 항상 O(n log n)
- Timsort: 최선 O(n), 평균 및 최악 O(n log n)
- 공간 복잡도:
- 힙 정렬: O(1) (제자리 정렬 가능)
- Timsort: O(n) (병합 과정에서 추가 공간 필요)
- 안정성:
- 힙 정렬: 불안정 정렬
- Timsort: 안정 정렬
- 실제 성능:
- 힙 정렬: 이론적으로는 빠르지만, 캐시 지역성이 좋지 않아 실제 성능이 떨어질 수 있음
- Timsort: 실제 데이터에서 자주 발견되는 패턴을 잘 활용하여 평균적으로 더 빠른 성능을 보임
Java에서 Timsort를 사용하는 이유:
적응성
- Timsort는 이미 정렬된 데이터나 부분적으로 정렬된 데이터에 대해 매우 효율적
- 그래도 우선 전체 리스트 순회해야 하므로 n보단 오래걸린다..!
- 따라서, Heap 정렬이 이 부분에서는 더 효율적이긴 함
실제 데이터 처리
- 대부분의 실제 데이터는 완전히 무작위가 아니며, Timsort는 이러한 데이터의 패턴을 잘 활용
- 즉, 지역성 잘 활용한다!
- 힙 정렬은 연속된 연산이 메모리상 가까운 위치를 다루지 않음
- 부모랑 자식이 먼 곳에 위치함 -> 따라서, 공간지역성 활용 불가
안정성: 동일한 값을 가진 요소들의 상대적 순서를 유지하는 것이 중요한 경우가 많습니다.
평균 성능: 다양한 데이터 세트에 대해 일관되게 좋은 성능을 보입니다.
최적화: Java 개발자들이 Timsort를 Java 환경에 맞게 잘 최적화했습니다.
PriorityQueue (힙 기반)
사용 시기:
- 동적으로 요소를 추가/제거하면서 최소/최대값을 자주 조회해야 할 때
- 부분 정렬 상태만 유지하면 충분할 때
- k번째 작은/큰 요소를 효율적으로 찾아야 할 때
- 데이터 스트림에서 중간값을 지속적으로 찾아야 할 때
장점:
- 삽입, 삭제: O(log n)
- 최소/최대값 조회: O(1)
- 메모리 효율적
정렬된 ArrayList + Collections.sort()
사용 시기:
- 전체 데이터셋이 정렬된 상태로 유지되어야 할 때
- 요소의 정확한 순위나 위치가 중요할 때
- 정렬된 상태에서의 이진 검색이 자주 필요할 때
- 데이터의 삽입/삭제가 비교적 적고, 조회가 많을 때
장점:
- 전체 데이터에 대한 빠른 접근과 순회
- 이진 검색 가능 (O(log n))
- 정렬 상태 유지로 인한 추가 연산 감소
TreeSet 또는 TreeMap
사용 시기:
- 정렬된 상태를 유지하면서 빠른 검색, 삽입, 삭제가 모두 필요할 때
- 중복을 허용하지 않는 정렬된 컬렉션이 필요할 때
- 범위 검색이 자주 필요할 때
장점:
- 삽입, 삭제, 검색 모두 O(log n)
- 항상 정렬된 상태 유지
- 범위 연산에 효율적
판단 기준:
- 연산의 빈도:
- 삽입/삭제가 빈번 → PriorityQueue 또는 TreeSet
- 조회가 주로 필요 → 정렬된 ArrayList
- 정렬 요구사항:
- 부분 정렬로 충분 → PriorityQueue
- 완전 정렬 필요 → 정렬된 ArrayList 또는 TreeSet
- 메모리 제약:
- 메모리 효율성 중요 → PriorityQueue
- 검색 패턴:
- 최소/최대값만 필요 → PriorityQueue (인덱스로 접근 불가)
- 임의의 요소 빠른 접근 필요 → 정렬된 ArrayList
- 범위 검색 필요 → TreeSet
- 중복 처리:
- 중복 허용 → PriorityQueue 또는 ArrayList
- 중복 불허 → TreeSet
- 데이터 크기와 변동성:
- 큰 데이터셋, 잦은 변경 → PriorityQueue 또는 TreeSet
- 작은 데이터셋, 적은 변경 → 정렬된 ArrayList도 고려 가능