[자료구조 및 알고리즘] unordered_map과 배열의 성능 차이

unordered_map과 배열의 성능 차이

오프라인 쿼리 문제를 풀다가 unordered_map을 이용하면 시간초과가 나고 배열을 사용하면 시간이 단축되는 경험을 했다. 둘 다 접근할 때 O(1)으로 알고 있었는데, 어디서 차이가 날까 생각해보았다. 해시충돌 때문이라고 넘어갈까 했지만 자세히 알아보고 기록해두는 게 좋을 거 같아서 포스팅하기로 결정했다.

 

1. unordered_map vs 배열

a) unordered_map의 특성

• 시간 복잡도
  • 평균적으로 O(1) 시간에 접근 가능
  • 핮만 최악의 경우 O(N)으로 느려질 수 있음 (해시 충돌 발생 시)
• 캐시 활용도
  • unordered_map은 내부적으로 해시 테이블을 사용하며 데이터가 메모리 상에 분산되어 저장된다.
  • 따라서 캐시 적중률(cache hit rate)가 낮아질 수 있다.
• 해시함수 비용
  • unordered_map은 키를 해싱하기 위해 추가 연산이 필요하며 이로 인해 오버헤드가 발생한다.

b) 배열의 특성

• 시간 복잡도
  • 접근 시간 O(1), 항상 일정
• 캐시 활용도
  • 배열은 메모리 상에서 연속된 공간에 저장되므로 캐시 적중률이 높음
  • CPU가 데이터를 읽어올 때 근처 메모리까지 미리 가져오는 특성(spatial locality) 덕분에 속도가 빠름

2. Mo's에서 시간 차이가 났던 이유

• Mo's는 구간 내의 값의 추가/제거 작업을 반복한다. 많은 빈도 계산을 할 때 unordered_map의 해시 충돌이 누적되거나 캐시 적중률이 낮아지면 성능이 크게 저하된다.
• 배열은 메모리 상에 연속적으로 저장되어 있어 Mo's의 데이터 접근 패턴과 잘 맞다.
• 반면 unordered_map은 데이터가 분산되어 있어 반복적인 접근에서 더 많은 비용이 발생한다.

3. unordered_map이 유리할 때는 언제?

unordered_map은 절ㄹ되지 않은 임의의 키값으로 접근할 때 유리하다.