timsort
Computing 2010. 10. 7. 16:27timsort ?
timsort 는 merge sort 를 아주 많이 최적화 한 소팅 알고리즘이다. 고안자의 이름인 Tim Peter 를 따서 timsort 라고 부른다.
소팅 알고리즘 종류의 분류상 timsort 는 stable sort, in-place sort 로 분류된다.
timsort 는 naive 한 (실험실에서나 볼 수 있는) pseudo random data 뿐만 아니라 quick sort 등이 좋은 성능을 보이지 못하는 real world data 에서도 상당히 좋은 성능을 보여 준다. 그런 연유로 사이, java.util 의 array sort 가 timsort 를 사용하고 있으며, python 의 list sort 가 timsort 알고리즘을 사용하고 있다. 좀 더 자세한 소개는 wikipedia 에 잘 나온다: http://en.wikipedia.org/wiki/Timsort
timsort 는 merge sort 에 아주 많은 최적화를 해 두어서 완벽하게 이해하는 데에는 꽤나 시간이 걸린다. 그러나 일단의 기본 원리만 알면 복잡하긴 해도 그다지 어렵지는 않다. 영문으로 된 자세한 설명은 timsort 의 고안자인 Tim Peter 가 다음의 페이지에 잘 적어 두었다: http://svn.python.org/projects/python/trunk/Objects/listsort.txt
본 article 에서는 위 문서의 내용 중 timsort 의 핵심이라고 할 수 있는 몇가지를 알기 쉽게 (우리말로) 다시 설명해 보도록 하겠다.
Runs
일단, 위에서도 언급하였듯이, timsort 의 기본 알고리즘은 변형된 merge sort 이다. 다만, naive 한 merge sort 와 크게 다른 점은 run 생성시 run 의 size 를 adaptive 하게 동적으로 구한다는 점이다. timsort 는 run 을 만들 때, 이미 정렬되어 있는 sequence 를 기본 단위로 해서 생성한다. 만약 정렬되어 있는 기본 단위가 특정 상수 (minrun) 보다 작다면, 그 특정 상수만큼의 길이를 binary insertion sort 를 한 후 인위적으로 정렬시킨 후 이를 run 으로 사용한다.
timsort 가 호출되면 제일 처음 하는 일은 minrun 값을 구하는 것이다. minrun 은 임의의 run 이 구성될 수 있는 최소 길이이다. minrun 을 구할 때, 만약 입력된 sequence 의 element 갯수 N 이 64 보다 작으면 minrun 은 N 이 된다. 이처럼 작은 단위에서는 웬만해서는 binary insertion sort 보다 빠른 소팅방법은 없으며, 그냥 binary insertion sort 를 sequence 에 대해 수행해 버린다.
minrun 을 계산할때의 목표는 merge 과정에서 merge 대상이 되는 각각의 run 이 가능한한 perfectly balanced 상태를 유지하도록 하는 것이다. 왜냐하면 그렇게 했을 때 merging 이 가장 빠르기 때문이다. 이 조건을 만족하는 minrun 값을 구하는 법에 대한 자세한 내용은 http://svn.python.org/projects/python/trunk/Objects/listsort.txt 의 Computing minrun 부분을 참조하도록 한다.
run 을 구하는 데 있어서, 만약 구해진 run 의 길이가 minrun 값보다 작다면, 앞에서도 계속 언급했듯이, minrun 길이의 구간을 binary insertion sort 를 이용해서 sort 해 버린 후 이를 run 으로 잡는다. binary insertion sort 는 작은 길이의 sequence 에서는 매우 빠른 성능을 보이는 sorting algorithm 으로써, gnu libc 의 quick sort 나 bsd libc 의 quick sort 또한 partition 을 해 나가다가 partition 의 길이가 일정 사이즈 이하가 되면 quick sort 를 포기하고 binary insertion sort 를 수행하는 최적화를 하고 있다.
Stablity and definition of descending and ascending
한가지 염두에 두어야 할 것은 timsort 는 stable sort 라는 것이다. 이로 인해 descending 과 ascending 의 정의는 아래와 같이 strict 하게 정의되어 있다:
a run with n elements is ascending iff a1 <= a2 <= a3 ... an-1 <= an
a run with n elements is descending iff a1 > a2 > a3 ... an-1 > an
Merge Stack
timsort 는 run 을 구하고, 구해진 run 을 계속 merge 해 나가는 과정의 반복이다.
이에 있어서, 앞서도 언급했지만, merge 가 가능한한 balanced 상태로 이루어 지는 것이 알고리즘의 효율이 훨씬 좋아지기 때문에, 가능한한 비슷한 길이의 run 끼리 merge 하기 위해 merge stack 이라는 구조체를 사용하고 있다.
일단 하나의 run 이 만들어지거나 판별 되면, timsort 는 그 run 의 시작 위치와 길이를 merge stack 이라는 구조체에 push 해 넣는다. merge stack 은 소스코드를 살펴 보면, 그냥 시작 위치와 길이를 가지고 만들어진 구조체의 배열이다.
이렇게 하나의 run 을 push 한 후에는 merge_collapse() 함수를 호출하여서 앞서 push 되어 있던 run 과 merge 를 할 것인가를 판단하여 merge 를 하거나 혹은 merge 하는 것은 약간 뒤로 미룬 후 그 다음 run 을 찾는 루틴으로 돌아가거나 한다.
메모리 사용이나 캐쉬 히트율등을 고려할 때 merge 를 최대한 미루는 것과 최대한 빨리 그때그때 하는 것 사이에서 적절한 타협을 해야 하는데, timsort 에서 취하고 있는 방법은 아래의 두 가지 조건을 만족하도록 merge stack 을 유지하는 방법을 취하고 있다:
run 이 입력 sequence 상에서 왼쪽에서 오른쪽으로 A, B, C 의 순서로 배치되어 있을 경우,
invariant #1 : A > B + C
invariant #2 : B > C
그러나 만약 merge stack 의 각 run 의 길이가 A <= B + C 일 경우에는 A 와 B 둘 중 작은 쪽을 B 와 merge 하는 정책을 취한다. 예를 들면 아래와 같다: (뒤의 숫자는 run 의 길이이다)
A:30 B:20 C:10 ----> A:30 BC:30 (A > C 임. 따라서 C 를 B 와 merge)
만약 다음과 같다면:
A:500 B:400 C:1000 ----> AB:900 C:1000 (A < C 임. 따라서 A 를 B 와 merge)
그러나, 위 두가지 경우 모두 이처럼 merge 를 수행한 이후에도 위의 조건 2 번을 여전히 만족시키지 못한다. 그럴 경우 위의 조건들을 만족시킬 때 까지 merge_collapse() 함수를 계속 수행하도록 한다.
참고로, 서로 인접해 있는 run 끼리만 merge 를 하는 이유는 stability 를 만족시키기 위해서이다. 왜 그렇게 해야만 stability 가 만족되는지는 http://svn.python.org/projects/python/trunk/Objects/listsort.txt 문서를 참조할 것.
Right before actual merging
윗 절에서 merge 할 run 을 선택하는 방법을 설명했으니 이제는 merge_collapse() 함수에서 실제 merge 가 어떻게 수행되는지를 살펴 보도록 하겠다.
merge_collapse() 함수는 merge stack 에 남아있는 run 이 없어질 때까지 merge stack 의 run 들을 merge 하는 함수인데, 실제 merge 는 merge_collapse() 함수에서 호출되는 merge_at() 함수에서 수행되므로 merge_at() 함수를 개략적으로 살펴 보도록 하겠다.
merge_at() 함수에서 본격적인 merge 에 들어가기 전에 하는 일은 merge 를 수행할 필요가 없는 구간을 구해내는 것이다. 다시 말하면, 각각의 run 은 모두 이미 그 안에서 정렬되어 있는 상태이므로 아래의 조건을 만족하는 구간을 주어진 두 개의 run 에서 구해낸다. 아래의 그림과 같다:
merge_at() 함수에서는 위 그림의 RUN A 와 RUN B 를 merge 하게 된다. 이 때, gallop_right() 함수를 수행하여 RUN B 의 첫번째 원소보다 큰 원소들이 첫번째 출현하는 위치를 RUN A 에서 찾는다. 그리고, gallop_left() 함수로 RUN A 의 마지막 원소보다 작은 원소가 첫번째 출현하는 위치를 RUN B 에서 역순으로 찾는다.
사실상, A 와 B 를 전부 merge 할 필요는 없다. 위의 조건을 만족하는 A' 과 B' 만 merge 하면 되는 것이다.
gallop_left(), gallop_right() 함수에 대해서는 다음 절에서 설명하도록 하고, 본격적인 merge 함수의 개략적 흐름에 관해서 이야기해 보도록 하자.
Merge Memory
메모리에 대해 다루기 전에 우선 알아 두어야 할 사항을 짚어 두고서 넘어가도록 하자.
우선 바로 앞 절에서 다루었듯이, merge 를 수행할 필요가 없는 부분은 이미 잘려지고, 위 그림의 A' 과 B' 으로만 merge 를 수행하게 된다. 앞으로는 A' 과 B' 에서 ' 기호를 떼고 그냥 A, B 라고 부르겠다. 이처럼 merge 를 수행할 필요가 없는 부분을 잘라 냄으로써, memory 할당량을 줄일 수 있다. 뿐만 아니라 성능면에서도 이득을 기대할 수 있다. 그러나, 만약 data sequence 가 random 일 경우에는 이같은 노력이 오버헤드로 작용한다. 그럼에도 불구하고, timsort 는 "real world data" 에 완전한 random data 는 아주 드물다는 rationale 하에 작성되었기 때문에, 더 큰 성능 이득을 얻기 위한 작은 도박을 하고 있는 것이다.
어찌 되었던, timsort 의 merge algorithm 은 성능과 메모리 효율을 높이기 위한 목적으로 크게 두 가지 루틴으로 나뉜다: merge_lo() 와 merge_hi() 가 그것인데, 두 루틴의 기본 로직은 동일하다. 다만 각각의 루틴이 사용되는 경우 및 merge 의 진행 방향이 다를 뿐인데, run 의 길이에 따라서 어떤 루틴이 사용될지가 결정된다:
if A <= B, merge_at() calls merge_lo()
if A > B, merge_at() calls merge_hi()
이제, 메모리에 대해 이야기할 준비가 되었다.
merge algorithm 이 원래 그렇듯이, timsort 역시 merge 를 수행하기 위한 부가적인 memory 를 필요로 한다. 이 메모리를 merging area 라고 부르자. timsort 는 입력 sequence 에서 이미 정렬된 구간을 run 으로 선택하기 때문에 run 의 길이가 교과서의 merge sort 와는 달리 가변적이다. 따라서 merging area 를 할당하는 데에도 약간의 트릭을 사용하였다.
트릭은 간단하다. merging area 를 할당할 때 두 개의 run 중 더 작은 run 의 사이즈만큼만 할당하는 것이다.
우선 merge_lo() 의 경우를 살펴 보자. merge_lo() 는 merge 대상이 되는 run 의 길이가 A <= B 일 때 호출된다. 따라서, merging area 의 구성 및 merge 방향은 아래의 그림과 같이 구성된다:
위 그림에서 볼 수 있듯이, run A 의 길이가 더 짧기 때문에, run A 의 사이즈만큼 메모리를 할당한다. 그리고 나서 할당한 메모리로 원래 run A 의 내용을 복사해 준다. merge 는 복사된 run A 와 run B 사이에서 일어나며, merge 의 결과는 원래 run A 였던 메모리의 시작부분부터 하나씩 저장되게 된다.
약간 주의깊이 생각해야 할 것은, 이처럼 merge 를 하는 와중에 exception 이 발생하거나 sort 가 중단될 경우, 나머지 남은 부분을 원래 있던 부분에 복사해 주어야 한다는 것이다. in-place sort 의 조건을 만족시켜야 하기 때문이다.
merge_hi() 의 경우는 merge 대상이 되는 run 의 길이가 A > B 일 때 호출된다. 따라서 merging area 의 구성 및 merge 방향은 아래의 그림과 같이 구성된다:
마찬가지로, 더 짧은 길이의 run 인 run B 만큼의 메모리를 할당하고, 그곳에 원래의 run B 를 복사해 넣는다. 그리고, merge_lo() 와는 반대로 오른쪽에서 왼쪽으로 각 run 의 element 를 비교해 가면서 merging area 에 merge 결과를 채워 넣는다.
merge_hi() 는 merge_lo() 와는 달리, 각 run 의 element 를 비교해서 merging area 에 채워넣는 결과는 두 element 중 보다 큰 element 를 채워 넣는다는 것에 주의하도록 한다.
Merge Algorithms
앞 절에서 merge_hi() 와 merge_lo() 에 대해 소개했기 때문에, 두 루틴의 공통적인 부분만 설명하겠다.
merge 루틴은 크게 두 개의 mode 로 나누어진다. 첫번째는 일반적인 merge 와 동일한 mode 이다. "one pair at a time mode" 라고 부르도록 하겠다. 두번째는 "galloping mode" 라는 특수한 mode 이다.
설명은 merge_lo() 를 기준으로 진행하겠다. merge_hi() 의 경우는 괄호 안의 단에 기입했다.
merge 의 시작은 교과서의 알고리즘대로 run A 와 B 의 첫번째 (merge_hi() 에서는 마지막) element 를 서로 비교해서 더 작은 (merge_hi() 에서는 더 큰) 값을 merging area 에 복사해 넣는 것으로 시작한다. 설명의 편의를 위해서 run B 의 첫번째 (마지막) element 가 더 작은 값 (큰 값) 을 가지고 있다고 가정하자. 그러면, run B 의 첫번째 (마지막) element 가 merging area 에 복사된다.
여기서, 교과서의 merge 와 다른 점은 각각의 run 이 연속해서 선택된 횟수를 유지한다는 점이다.
만약 어느 한쪽의 run 이 연속해서 MIN_GALLOP 만큼 선택되었을 경우에는 "galopping mode" 로 전환된다. 설명의 편의상 run A 가 연속해서 선택된 run 이고, run B 는 연속해서 선택되지 않은 run 이라고 가정하도록 하자.
galopping mode 는 연속해서 MIN_GALLOP 이상 선택된 run A 에서 연속해서 선택되지 않은 run B 의 현재 위치의 값 (편의상 B[0] 라고 두겠다) 보다 큰 값이 언제 출현하는가를 검색한다. galopping mode 라는 이름이 시사해 주듯이, A 에서 B[0] 를 검색해 갈 때, A 의 인덱스를 1 씩 증가시켜서 검색하는 것이 아니라 2n 씩 검색주기를 늘려서 검색해 간다. 그리고, B[0] 보다 큰 값이 발견되면 바로 앞의 인덱스와 발견된 인덱스 사이에서 binary search 를 해서 B[0] 가 어느 위치에 들어가야 할지를 결정한다. 그리고 그 위치보다 앞에 존재하는 모든 A 의 값을 merging area 에 복사해 넣는다.
그리고 나면, 다시 A[0] 의 값을 가지고 run B 를 동일한 방식으로 검색한다. 이 때, 방향은 오른쪽에서 왼쪽방향이다. 그렇게 해서 결정된 run B 의 일정 구간을 다시 merging area 에 복사해 넣는다.
위의 두 과정을 복사해 넣어진 구간의 길이가 MIN_GALLOP 보다 길 동안 계속한다. 만약 복사해 넣은 구간의 길이가 MIN_GALLOP 보다 작을 경우 다시 "one pair at a time mode" 로 돌아간다.
Galloping 에 대한 자세한 설명은 그다지 필요 없을 듯 하다.
소스를 받아서 한번 살펴보는 것과, 방금 위에서 설명한 것으로 충분할 것 같다.
Performance
그러면, 가장 중요한 소팅 알고리즘의 성능을 실제로 테스트해 볼 시점이다.
naive 한 성능 측정은 random 데이터를 생성해서 그것을 소팅하는 데에 걸리는 시간을 가지고 알고리즘의 성능을 판단한다. 그렇지만, 그것만으로는 불충분하다. 왜냐하면 실 세계에서 발생하는 데이터는 random 한 경우보다 일정한 패턴을 가지고 있기 때문이다. 이 때문에 timsort 가 고안되었다고도 할 수 있다.
성능 측정에 사용할 입력 sequence 는 대략 아래와 같은 유형이다 : (출처 : http://www.softpanorama.org/Algorithms/sorting.shtml)
- Completely randomly reshuffled array (this is the only test that naive people use in evaluating sorting algorithms) .
완전히 random 하게 뒤섞인 수열.
- Already sorted array (you need to see how horrible quicksort is on
this case and how good shellsort is ;-). This is actually a pretty
important case as often sorting is actually resorting of previously
sorted data done after minimal modifications of the data set.
이미 정렬되어 있는 수열 (이 경우 퀵 소트가 얼마나 형편 없는 성능을 내며, 쉘소트가 얼마나 빠른지 봐야 한다. 이 케이스는 사실상 매우 중요한 케이스라고 할 수 있는데, 왜냐하면 대부분의 경우 소팅은 이전에 정렬되어 있던 데이터에 아주 작은 데이터를 수정한 후 그 세트를 다시 소팅하는 경우가 많기 때문이다)
- Already sorted in reverse order array (many algorithms work slow on such an array)
역순으로 이미 정렬되어 있는 수열 (상당수의 알고리즘이 느린 성능을 보인다)
- Chainsaw array
톱날처럼 분포되어 있는 수열
- Array consisting of identical elements (many algorithms work slow on such an array)
같은 값으로 구성된 수열 (상당수의 알고리즘이 느리게 동작한다)
- Already sorted array with N permutations (with N from 0.1 to 10% of the size)
- Already sorted array in reverse order array with N permutations
- Data that have normal distribution with duplicate (or close) keys (for stable sorting only)
중복되거나 아주 근사한 값이 여러개 분산되어 존재하는 수열 (stable sorting 에만 적용)
- Pseudorandom data (daily values of S&P500 or other index for a
decade might be a good test set here; they are available from Yahoo.com)
의사난수(?) 로 이루어진 수열 (주식시세 변동 등)
실제 테스트한 데이터는 http://orchistro.tistory.com/205 를 참조한다.
----
timsort source code download : http://timsort.googlecode.com/
python 소스트리에서 timsort 루틴만 추출해 낸 것. 포인터를 직접 증/감 시키는 것이 아니라 java 의 구현처럼 index variable 을 사용함. 포인터를 직접 증감하는 방식과의 성능 차이는? 테스트 해 보지 않음.
python 소스보다 조금 더 많은 주석.
----
참고 웹 페이지들 :wikipedia : http://en.wikipedia.org/wiki/Timsort
android java.util : http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/TimSort.java?view=co
python svn repository :
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
http://svn.python.org/projects/python/trunk/Objects/listobject.c
그 외 참고 문헌 (timsort 저자의) :
"Optimistic Sorting and Information Theoretic Complexity" / Peter McIlroy / SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp 467-474, Austin, Texas, 25-27 January 1993