목표
- 참조의 지역성과 메모리의 특성에 대해서 이해한다.
- 지역성의 원리에 따라 Mergesort가 Quicksort보다 실제로 느린지에 대해 이해한다.
참조의 지역성(Locality of Refrence)과 메모리
참조의 지역성
- 시간 지역성(Temporal)과 공간 지역성(Spatial)로 구분
- 프로세서는 메모리를 효율적으로 사용하기 위해 가장 가까운 시간, 공간 내에 있는 메모리의 데이터를 반복적으로 동일하게 접근
메모리와의 관련성
- 이러한 시간, 공간 지역성의 특성에 의해 프로세서와 메모리(RAM)은 멀리 떨어져있음에도
페이징 기법을 사용하여 메모리를 효율적으로 사용할 수 있음 - L1, L2와 같은 캐시를 이용하여 임시적인 지역성을 확보하여 최근의 데이터에는 빠르게 접근 가능
이는 시간 지역성에 따른 접근이지만 실제로 캐시는 캐싱을 위해 캐시 라인을 사용하기때문에 공간 지역성에 따른 영향도 받음
지역성의 원리에 따른 퀵과 머지소트의 비교
참조 지역성과 정렬 알고리즘
- 정렬 알고리즘은 재귀를 통해 구현되기 때문에 같은 공간 내의 데이터에 빠르게 접근할 수 있을수록 더욱 빨라짐
- 이는 같은 캐시 공간 내 데이터가 존재 한다면 -> 데이터가 움직이지 않는다면 더욱 유리함
Mergesort
- 정렬 시 분할-합병 데이터가 같은 공간 내 존재하지 않는다면 매번 다른 공간까지 이동해야 함
Quicksort
- Quicksort는 pivot을 통해 분할은 했지만 데이터가 존재할 수 있는 위치는 크게 변하지 않는다.
따라서 제자리 정렬이라고도 불리며 이 작업은 추가 메모리를 거의 필요로 하지 않는다.
결론
- 왜 merge sort가 모든 케이스에서 O(n log n)의 속도를 가짐에도 실제로 Quick sort보다 느리게 작동할 수 있는지 대한 해답은 컴퓨터의 하드웨어적 특성인 참조의 지역성에 있다.
- Merge sort는 하드웨어적 한계로 인해 Quick sort보다 느리다.
참고
ATM