우리가 학부 시간에 자료구조 수업에서 다루는 정렬은 in-memory sorting을 가정한다. 즉, 데이터가 메인 메모리에 적재 가능한 수준일 경우를 가정한다. 그런데, 메인 메모리에 담기지 않을 경우에는 어떻게 할까? 디스크 저장소를 여러번 읽고 쓰거나 여러 컴퓨터에서 정렬을 병렬적으로 수행하는 것으로 보인다.
In-memory Sorting
나는 힙정렬이 왜 병합정렬 또는 퀵정렬보다 느린지 궁금했다. 힙정렬 같은 경우는 locality가 병합정렬 또는 퀵정렬보다 떨어져서 최악 시간복잡도가 O(nlogn)이라도 실제 성능이 좋지 않다고 한다. 병합정렬 같은 경우에는 in-place가 아니라 추가 메모리 할당이 O(nlogn)만큼 필요하기 때문에 평균 성능이 퀵정렬보다 느리다고 한다. 퀵정렬 최악 시간 복잡도가 O(n ** 2)이기에 피봇을 잘못 골랐다가는 실행 시간이 크게 늘어난다는 문제점이 있다.
여러 라이브러리와 빌트인 함수의 경우 트레이드오프를 고려해서 정렬을 섞어 사용하는 것으로 보인다.
locality
프로그램의 메모리 접근 패턴이 얼마나 캐시에 효율적인지 나타내는 성질이다. Locality는 spatial locality와 temporal locality로 구분된다.
- spatial locality: 최근에 접근했던 메모리 영역의 근처에 다시 접근하느 정도를 의미한다.
- temporal locality: 최근에 접근했던 메모리 영역에 다시 접근하는 정도를 의미한다.
in-place sort
데이터를 적재하기 위해 힙 메모리 영역에 추가 메모리를 할당하지 않고 정렬이 가능한 경우 in-place sorting이라고 부른다.
External Sorting
데이터가 메인 메모리에 다 안 들어갈 때 정렬을 수행한다. 캐시 히트를 늘리기 위한 관점에서 locality를 높이는 것보다는 디스크 랜덤 I/O 최소화와 순차 I/O 최대화로 목표가 바뀐다.
Top comments (0)