[Python] sort, sorted ( Tim sort, 팀 소트)

파이썬 내장 모듈을 유용하게 쓰다보니 내부 구조나 알고리즘을 뭘로 썼지?

내장 모듈의 sort() 알고리즘이 궁금해졌다.

 

Sort() vs Sorted() 

sort 함수는 List.sort(*, key=None, reverse=False) 형식으로 "리스트형의 메소드"​​으로 리스트_객체 값을 직접 수정한다.

sorted 함수는 sorted(iterable, /, *, key=None, reverse=False) 형식으로 "파이썬 기본 내장 함수"으로  원본 값은 그대로이고 정렬 값을 반환한다.

 

 

결론부터 말하면 

• 파이썬 Sort 알고리즘은 Tim Sort로 삽입 정렬과 머지 정렬을 혼합하여 사용하였는 데, 삽입 정렬을 사용한 이유는 캐시히트 & 캐시미스 & 지역 참조성을 잘 만족시키기 때문이다. Tim Sort 는 삽입 정렬과 머지 정렬의 적절한 경계선을 찾는 것이 핵심이다.
• 무작위 데이터에서는 최악 O(n log n )이 발생할 수 있지만, 실제 데이터는 완전 무작위 데이터 보다는 규칙성이 있다고 가정했을 때, 매우 효과적인 알고리즘이어서, 많은 언어에서 채택하고 있다.

 

 

그러면 이제 궁금한 건

1. 어떤 알고리즘을 사용하였는 가 ?

기본적으로 둘다 Tim Sort 알고리즘을 사용한다. 정렬 하면

1. 선택 정렬(Selection Sort)
2. 삽입 정렬(Insertion Sort)
3. 버블 정렬(Bubble Sort)
4. 병합 정렬(Merge Sort)
5. 퀵 정렬(Quick Sort)

이 떠오르는 데 , Tim Sort은 삽입 정렬과 병합 정렬을 적절히 섞은 개념으로

출처 : https://d2.naver.com/helloworld/0315536 Insertion Sort

출처 : https://d2.naver.com/helloworld/0315536   Merge Sort

 

출처 : https://d2.naver.com/helloworld/0315536

왜 시간 복잡도(n^2)가 높은 Insertion sort 를 썻을 까?

삽입 정렬의 경우 인접한 메모리와 비교하는 경우가 많아 참조 지역성의 원리가 잘 적용된다.

 

참조 지역성을 알려면 

 

1) 공간(spatial) 지역성 : 특성 클러스터의 기억 장소들에 대해 참조가 집중적으로 이루어지는 경향으로, 참조된 메모리 근처의 메모리를 참조합니다.

2) 시간(temporal) 지역성 : 최근 사용되었던 기억 장소들이 집중적으로 액세스되는 경향으로, 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높습니다.

3) 순차(sequential) 지역성 : 데이터가 순차적으로 액세스되는 경향으로, 프로그램 내의 명령어가 순차적으로 구성되어 있다는 것이 대표적인 경우입니다. 공간 지역성에 편입되어 설명되기도 합니다.

출처: https://jwprogramming.tistory.com/18 [개발자를 꿈꾸는 프로그래머:티스토리]

 

참조 지역성을 생각하려면 CPU안에 캐시는 빠르고, 메모리에서 가져오는 (페이지, 로드, 가상메모리 아무튼 느림)라는 기본전제에서

마침 필요한 데이터가 캐시에 있는 (캐시 히트) 좋은 경우,  메모리에 데이터가 있는 (캐시 미스) 안 좋은 경우로 나눠 이해하자

 

공간 지역성은 메모리 주소상 비슷하니 뭉칠 째로 들고 올때 같이 들고 오면 좋을 것이다.

시간 지역성은 최근에 사용했으니 또 쓸 것이다.

순차 지역성은 보통 데이터들이 for문이나 while문을 통해 하나씩 조회한다. 다시 조회할 확률이 높다.

라는 생각에 캐시 가져오면 잘 쓰겠지하면서 캐시에 밀어 넣는다. -> 캐시히트가 나서 -> 처리가 빠르다

 

그러다 보니 삽입 정렬이 작은 케이스에 대해 퀵 소트보다 빠르다. 

이 상황에서 전체 케이스를 작은 덩어리로 만들고 이를 병합하는 형식이 기본 컨셉이다.

 

Tim Sort

드디어 Tim sort 내부 알고리즘을 보자

 

전체를 적당한 덩어리로 잘라서 삽입 정렬 후, 머지 정렬을 한다하니, 이제 적당한 덩어리를 정해야한다.

 

출처 : https://d2.naver.com/helloworld/0315536

 

이후 내용은 간략하게만 서술

 

Run 

1. 기본적으로 2^X 개로 덩어리 나누어 자른다.

2. 덩어리가 최대로 키우기 위해 덩어리 나눈 후, 이후의 값이 덩어리 값보다 큰다면 덩어리에 넣는다. (작을 때까지)

3. 한 덩어리 (run) 을 만들었다면, 이후 덩어리는 작아지는 방향으로 만든다.

 

2. 과정에서 실생활에서 사용하는 데이터들이 규칙적 또는 순차적인 특성을 가지고 있다고 가정했을 때, Tim sort의 장점이 나온다.

Binary Insertion sort

덩어리는 이미 정렬되어 있기에 이진 정렬방식을 사용한다.

Merge

앞서 덩어리의 크기를 유동적으로 사용했기 때문에, 지나친 크기 차이는 비효율적인 결과 가져온다. (사실상 머지가 아니라 정렬이라)

머지를 할 때는 비슷한 크기 끼리 먼저 머지를 한 후, 머지를 친다.

 

2 Run Merge

위에 방법을 통해, 머지의 효율성을 올렸다. 하지만 여전히 머지 정렬의 단점인 많은 메모리를 사용하는 문제가 있는데, 이를 해결하기 위해서, 작은 run을 Copy 한 다음, 두 run 시작 위치부터 순차적으로 접근 후, 덮어쓴다. 이 때,  큰 Run 값은 정렬 전에 덮어지지 않는다.

 

여기서 한번 더 최적화를 했는데, 계산이 필요없는 부분을 미리 계산한다. 

Galloping

이건 나중에..