timsort

Computing 2010.10.07 16:27

timsort ?

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

위와 같은 strict 한 descending 의 정의로 인해서 sorting 시 descending 으로 정렬되어 있는 run 을 만날 경우, 양 끝의 element 를 서로 swap 해서 해당 run 을 ascending 으로 교환하더라도 stability 가 보장된다.


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 ARUN B 를 merge 하게 된다. 이 때, gallop_right() 함수를 수행하여 RUN B 의 첫번째 원소보다 큰 원소들이 첫번째 출현하는 위치를 RUN A 에서 찾는다. 그리고, gallop_left() 함수로 RUN A 의 마지막 원소보다 작은 원소가 첫번째 출현하는 위치를 RUN B 에서 역순으로 찾는다.

사실상, AB 를 전부 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)

  1. Completely randomly reshuffled array (this is the only test that naive people use in evaluating sorting algorithms) .
    완전히 random 하게 뒤섞인 수열.

  2. 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.
    이미 정렬되어 있는 수열 (이 경우 퀵 소트가 얼마나 형편 없는 성능을 내며, 쉘소트가 얼마나 빠른지 봐야 한다. 이 케이스는 사실상 매우 중요한 케이스라고 할 수 있는데, 왜냐하면 대부분의 경우 소팅은 이전에 정렬되어 있던 데이터에 아주 작은 데이터를 수정한 후 그 세트를 다시 소팅하는 경우가 많기 때문이다)

  3. Already sorted in reverse order array (many algorithms work slow on such an array)
    역순으로 이미 정렬되어 있는 수열 (상당수의 알고리즘이 느린 성능을 보인다)

  4. Chainsaw array
    톱날처럼 분포되어 있는 수열

  5. Array consisting of identical elements (many algorithms work slow on such an array)
    같은 값으로 구성된 수열 (상당수의 알고리즘이 느리게 동작한다)

  6. Already sorted array with N permutations (with N from 0.1 to 10% of the size)

  7. Already sorted array in reverse order array with N permutations

  8. Data that have normal distribution with duplicate (or close) keys (for stable sorting only)
    중복되거나 아주 근사한 값이 여러개 분산되어 존재하는 수열 (stable sorting 에만 적용)

  9. 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

python mailing list : http://mail.python.org/pipermail/python-dev/2002-July/026837.html

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


저작자 표시 비영리 변경 금지
신고
Trackback 0 : Comment 0

Write a comment

티스토리 툴바