파이썬 팀소트의 자바 구현의 버그

사전 지식

본 글은 팀소트(Timsort, 팀 정렬)에 대해 어느 정도 알고 있음을 전제로 한다. 그렇지 않다면 네이버디벨로퍼(https://d2.naver.com/helloworld/0315536), st-lab(https://st-lab.tistory.com/276)을 참고하라.

 

복습

위키피디아

정렬되지 않은 배열로부터 run(이하 런)이 여러 개가 만들어지고, 이들이 하나씩 스택으로 옮겨가는데, 위에서 1번째 런을 X, 2번째 런을 Y, 3번째 런을 Z라고 부르면 식 1과 식2(이하 대소비교식)가 충족되어야 하고, 이 식1과 식2는 스택이 변화하더라도 불변(invariants)한다 혹은 불변해야한다. 이때 스택이 변화한다는 것은 규칙에 따라 스택 내의 런들을 머지시키는 것을 의미한다.

arXiv:1805.08612

스택 내의 런들을 머지시키는 공식은 라인 3~8이다. 일단 파란색은 무시하자.

 

시사점

한편 대소비교식을 잘 생각해보면 피보나치 수열의 공식과 흡사하다는 점을 알 수 있다. 피보나치 수열은 대충 2^x 정도로 매우 빠르게 증가한다.

위키피디아

두 번째 문장은 일단 무시하고 첫 번째 문장만 보자. "불변성의 존재가 스택의 크기의 tight upper bound를 만든다."라고 한다. 스택의 크기가 5로 선언되었다면 이 속에는 최대 5개의 피보나치 수열의 값(과 유사한 런들의 크기의 수열의 값)이 담겨있을 수 있다. 그 값들의 합은 피보나치 수열의 성질상 7(N+2)번째 값-1이고 이것이 tight upper bound로 작용한다.
구체적인 예를 들어 크기 5짜리 스택에 5개의 원소가 담겨 [1, 1, 2, 3, 5](+ 8, 13, ...)가 되었다고 하자. 최소한의 값만 담긴 최악의 경우에도 이들의 합은 12(=13-1)가 되고 이는 곧 크기 5짜리 스택은 크기 12짜리 미정렬 배열을 처리하는 데에 쓰일 수 있다는 뜻이다. 거꾸로 말하면 크기 12짜리 미정렬 배열을 처리하는 데에는 크기 5짜리 스택 혹은 그 이상의 스택이 있다면 무조건 처리할 수 있고 이 값이 tight한 값이 된다. 한편 만약 스택이 [1, 1, 2, 3, 1234]가 되었다고 하자. 이 스택은 대소비교식을 만족하고 크기 1241짜리 미정렬 배열을 정렬하는 데에 쓰일 수 있다. 마찬가지로 5보다 작은 크기의 스택이 크기 12짜리 미정렬 배열을 처리할 수 있다. 하지만 1234와 같은 큰 크기의 런이 만들어진다는 보장이 없으니 상한을 사용해야 한다.

길이 N짜리 미정렬 배열을 무조건 처리할 수 있는 스택의 크기를 x라 하자. 최소한의 x는 몇일까? 상술했듯이 fib(x+2)-1 >= N이 되는 첫 x값이다. 대략적으로는 몇일까? X=x+2라 할 때 피보나치 수열의 성질상 2^X >= fib(X) >= 2^(X/2)이고 로그를 취해주면 X >= log(fib(X)) >= X/2이다. 조건은 log(fib(X)-1) >= logN이다. 교점이 되는 1.111 초과의 x에 대하여 기울기의 차이로 인하여 log(fib(X)-1) > log(fib(X)) -1이고 log(fib(X))-1 >= logN 혹은 log(fib(X)) >= logN + 1은 원래 조건보다 더 강한 조건이다. 이 더 강한 조건은 X/2 >= logN + 1일 때 충족된다. 이때 미정렬 배열을 무조건 처리할 수 있는 최소한의 x는 2*logN이다.

함수의 하한값을 엄밀하게 계산하여 증가할 때(ex: fib(x)=1*phi^x), 피보나치 수열보다 빠르게 증가하는 수열(ex: 대소비교식에 의해 만들어지는 수열)을 사용할 때, 큰 크기의 런이 존재할 때, 수열의 초항이 1이 아닐 때(ex: 팀소트의 minrun) 함수의 값과 하한값이 커지고 최소한의 스택의 크기는 감소한다.

병합정렬의 성질상 머지되는 런들의 크기는 서로 비슷할수록 좋고 머지되는 런들의 크기가 작을수록 좋다.

 

자바의 버그

2015년(?)에 팀이 발표한 알고리즘은 파란색 글씨가 빠져있었고 따라서 파이썬의 구현에서도 파란색 글씨가 빠져있었다. 이로 인해 불변이 깨지고 미정렬 배열을 처리하는 데에 필요한 스택 크기의 상한 역시 깨지게 된다. 다행히 파이썬에서는 어쨌든 정렬을 하긴 한다. 파이썬(CPython)의 스택의 크기는 85개로 고정되어 있고 오류가 있는 걸 가정할 때 2^49개(=1e15)의 원소를 가진 미정렬 배열을 정렬할 수 있는데 이보다 큰 미정렬 배열을 만들기 위해서는 슈퍼컴퓨터보다 높은 메모리 용량이 필요하기 때문에 문제가 생기지 않는다.(de Gouw, Stijn (24 February 2015). "Proving that Android's, Java's and Python's sorting algorithm is broken (and showing how to fix it)" 링크, 파이썬 깃허브 링크) 지금 이 문단도 일단 넘어가자. 오류가 없다고 가정하면 2^64개의 원소를 가진 미정렬 배열을 정렬할 수 있다.
위에서 스택의 크기 = 2*logN이라 했는데 이러면 128이 나오고 85라는 값과 얼추 비슷하게 나온다. 원문은 32*phi^x >= len(arr)인데 이는 곧 초항이 32, 공비가 phi인 수열의 일반항이라고 볼 수 있다.

 

파란색 글씨가 빠진다면 어떤 일이 일어나는가? 이하의 표기에서는 왼쪽이 스택의 입출력이 이루어지는 top을 의미한다.
..., 4, 6, 20, 28, 92]
위의 스택은 모든 세 쌍에 대해 대소비교식을 만족한다. 이때 8짜리 런이 들어온다고 하자.
..., 8, 4, 6, 20, 28, 92]
첫 세 쌍 (8, 4, 6)에서 대소비교식을 만족하지 못한다. 라인 6에 해당되고 4와 6을 머지시킨다.
..., 8, 10, 20, 28, 92]
가 된다. 다시 while문으로 돌아오는데 첫 세 쌍은 대소비교식을 만족하기 때문에 while문을 탈출하게 된다. 그리고 다음 런을 들어오게 시킬 것이다.

문제는 그 다음 세 쌍 (10, 20, 28)이 대소비교식을 만족하지 못한다는 점이다. 이대로 가면 주어진 미정렬 배열에 대한 스택의 크기 상한을 규정하는 데에 필요한 조건을 만족시키지 못한다. 스택 내의 원소들이 작아지게 되고 합 역시 작아져 합>=N을 맞추기 위해서는 스택 크기의 상한이 커지게 된다. 주어진 크기 N의 미정렬 배열에 대해 스택의 크기를 f(N), 2*logN으로 설정하였는데, 이러한 오류가 발생해서 스택 내의 값들이 충분히 커지지 못한 채로 추가되게 된다면 스택을 꽉 채운 이후, 남는 런 즉 남는 배열의 길이를 다시 추가하려고 시도할 가능성이 있다.
이때 자바에서는 array-out-of-bound exception가 발생한다.

참고로 그 다음 세 쌍 (20, 28, 92)는 언제나 대소비교식을 만족한다. 따라서 만족하지 못할 가능성이 있는 것은 맨 위의 4개의 원소들뿐이니 이것들만 확인하면 된다.

 

해결책

해결책은 두 가지이다. 1. 스택의 크기를 늘린다. 간단하지만 메모리 비효율적이다. 2. 파란색 글씨를 추가한다. 해결책 1에 대한 설명은 생략하고 해결책 2에 대한 설명을 하겠다.

불변이 깨지는 경우는 어떤 런이 스택에 들어왔을 때이다. 들어오고나서도 대소비교식을 만족한다면, 문제가 없다. 만족하지 못한다면, 런 1과 2를 머지시키거나 런 2와 3을 머지시킬 것이다.
런 1이 새로 들어온 상황에서 런 1과 2를 머지시키는 경우를 알아보자.
..., 1, 2, 3, a, b, c, d]
... <12>, 3, a, b, c, d]
이렇게 변화하게 된다. 세 쌍 (3, a, b)는 대소비교식을 무조건 만족하고 세 쌍 (<12>, 3, a>)는 만족할 수도 안 할 수도 있는데 이것은 본질적으로 3까지만 추가된 배열에서 <12>라는 단일 런이 들어온 것과 동일하고 while 문 내에서 처리 가능하니 문제가 없다.
런 2와 3을 머지시키는 경우를 알아보자.
..., 1, 2, 3, a, b, c, d]
... 1, <23>, a, b, c, d]
이렇게 변화하게 된다. 세 쌍 (1, <23>, a)가 대소비교식을 만족할 수도 안 할 수도 있는데 이것은 while 문 내에서 처리 가능하니 문제가 없다. 그 다음 세 쌍 (<23>, a, b)가 대소비교식을 만족할 수도 안 할 수도 있는데 해당 경우는 파란색 글씨가 없다면 while 문 내에서 처리가 불가능하다. 이 세 쌍에 대해서도 조건문을 걸고 머지를 시켜줘야 한다. 13처럼 띄어서 머지를 시킨다면 안정정렬 요건이 충족이 안 되니 연속된 두 런에 대해서만 머지를 시켜야 하는데, 12, 23, 34, 45, ~~~ 중에서 하나를 골라야 한다. 대소비교식에 의해 2+3<a<b<c<d이니 (1, <23>), (<23>, a) 외의 다른 쌍은 병합정렬의 성질상 자명하게 불리하다. 1과 a의 크기 비교를 한 후 작은 것과 <23>을 머지시킨다. 이러면 다시금 while 문 내에서 처리 가능하다.

 

기타

파이썬은 3.11 버전 (2022년 10월 24일 릴리즈)부터는 팀소트가 아니라 파워소트(powersort)를 쓴다. https://leeingyun96.tistory.com/42 참고.

arXiv:1805.08612

알고리즘 2는 알고리즘 3과 같이 번역될 수 있고 이때 파란색 글씨는 런 3과의 비교 없이 무조건 런 1과 머지를 시키는 것을 알 수 있다. 알고리즘 2의 조건 분기를 잘 생각해보자. r1 > r3이라서 파란색 글씨에서 r3과 머지가 될 것이라면 애초에 알고리즘 2의 라인 3의 or의 왼쪽 항에 먼저 걸리기 때문에 r3과 머지가 될 일은 일어나지 않는다. 따라서 무조건 런 1과 머지를 시켜도 올바르다. 이에 맞춰 해결책 문단의 글도 "무조건 런 1과 머지시킨다."라고 수정해도 올바르겠으나 논리의 가시성을 위해 그대로 적도록 하겠다.