팀소트

팀소트

클래스	정렬 알고리즘
데이터 구조	배열
최악의 경우 공연	${\displaystyle O(n\log n)}$[1][2]
베스트 케이스 공연	${\displaystyle O(n)}$[3]
평균 공연	${\displaystyle O(n\log n)}$
최악의 경우 공간 복잡성	${\displaystyle O(n)}$

Timsort는 여러 종류의 실제 데이터에서 우수한 성능을 발휘하도록 설계된, 병합 정렬과 삽입 정렬에서 파생된 하이브리드 안정 정렬 알고리즘이다.그것은 파이톤 프로그래밍 언어에서 사용하기 위해 2002년에 팀 피터스에 의해 구현되었다.알고리즘은 이미 순서가 정해진 데이터의 부분(실행)을 찾아 나머지를 더 효율적으로 정렬하는 데 사용한다.이는 특정 기준이 충족될 때까지 런을 병합하여 수행한다.Timsort는 버전 2.3 이후 파이썬의 표준 정렬 알고리즘이었다.또한 Java SE 7에서,^[4] 안드로이드 플랫폼에서,^[5] GNU 옥타브에서,^[6] V8,^[7] Swift,^[8] Rust에서, 비원격 타입의 어레이를 정렬하는 데도 사용된다.^[9]

그것은 피터 매킬로이의 1993년 논문 "최적론적 분류와 정보 이론적 복잡성"^[10]의 기법을 사용한다.

작전

Timsort는 대부분의 실제 데이터, 자연 런에 이미 존재하는 연속적인 순서 요소의 런을 활용하도록 설계되었다.데이터 수집 요소를 반복해서 런으로 만들고 동시에 스택에 넣는다.스택 상단의 런이 병합 기준과 일치할 때마다 병합된다.이 작업은 모든 데이터가 통과될 때까지 계속되며, 그런 다음 모든 실행이 한 번에 두 번 병합되고 정렬된 실행 하나만 남게 된다.기존 병합에서 수행하는 고정 크기 하위 목록을 병합하는 대신 순서가 지정된 런을 병합할 수 있는 이점은 전체 목록을 정렬하는 데 필요한 총 비교 횟수를 줄인다는 것이다.

각 실행은 입력의 크기에 기초하여 최소 크기를 가지며 알고리즘의 시작에서 정의된다.실행이 이 최소 실행 크기보다 작은 경우, 삽입 정렬을 사용하여 최소 실행 크기에 도달할 때까지 실행에 더 많은 요소를 추가한다.

병합 기준

Timsort는 안정적인 정렬 알고리즘(같은 키를 가진 요소의 순서가 유지됨)으로 균형적 병합(따라서 유사한 크기의 병합 실행)을 수행하도록 노력한다.

정렬 안정성을 달성하기 위해 연속 주행만 병합한다.두 번의 비연속 주행 사이에 실행 내부에 동일한 키를 가진 요소가 있을 수 있다.이 두 런을 병합하면 동일한 키의 순서가 변경된다.이러한 상황의 예([]의 실행 순서 지정): [1 2] 1 4 2 [0 1 2]

Timsort는 균형 잡힌 합병을 추구하기 위해 스택 상단에 있는 X, Y, Z 3개의 런을 고려하고 불변성을 유지한다.

이러한 불변성 중 하나라도 위반되면 Y는 X나 Z의 작은 것과 병합되어 불변성을 다시 점검한다.불변기가 유지되면 데이터에서 새로운 실행을 위한 검색이 시작될 수 있다.^[12]이러한 불변자는 균형을 위해 합병을 지연시키고, 캐시 메모리에서 새로운 런 발생을 이용하고, 병합 결정을 비교적 단순하게 하는 절충점을 유지하면서 합병을 대략적으로 균형 잡힌 것으로 유지한다.

공간 오버헤드 병합

원래 병합 정렬 구현은 제자리에 있지 않으며 공간 오버헤드가 N(데이터 크기)이다.인플레이스 병합 정렬 구현이 존재하지만 시간 오버헤드가 높다.Timsort는 중간 기간을 달성하기 위해 N보다 적은 시간 오버헤드와 작은 공간 오버헤드로 병합 정렬을 수행한다.

먼저 Timsort는 이진 검색을 수행하여 첫 번째 순서 실행에서 두 번째 실행의 첫 번째 요소가 삽입될 위치를 찾고, 순서를 유지한다.그런 다음 동일한 알고리즘을 수행하여 두 번째 순서 실행에서 첫 번째 실행의 마지막 요소가 삽입될 위치를 찾고, 순서를 유지한다.이러한 위치 전후의 요소는 이미 올바른 위치에 있으므로 병합할 필요가 없다.그런 다음, 두 런의 나머지 요소들 중 더 작은 요소는 임시 메모리로 복사되고, 요소들은 더 큰 런과 합쳐져서 지금의 여유 공간으로 들어간다.첫 번째 런이 작으면 맨 처음에 병합이 시작되고 두 번째 런이 작으면 맨 끝에 병합이 시작된다.이 최적화는 일반적인 경우에 필요한 요소 이동 횟수, 작동 시간 및 임시 공간 오버헤드를 감소시킨다.

예: 두 개의 런[1, 2, 3, 6, 10]과 [4, 5, 7, 9, 12, 14, 17]은 병합해야 한다.두 실행은 이미 개별적으로 정렬되어 있다는 점에 유의하십시오.2차 주행에서 가장 작은 요소는 4이며, 순서를 보존하기 위해 1차 주행의 4번째 위치에 추가해야 한다(실행의 첫 번째 위치가 1이라고 가정한다.1차 주행의 가장 큰 요소는 10이며, 질서를 유지하기 위해서는 2차 주행의 5번째 위치에 추가해야 할 것이다.따라서 [1, 2, 3]과 [12, 14, 17]은 이미 최종 위치에 있으며 요소 이동이 필요한 주행은 [6, 10]과 [4, 5, 7, 9]이다.이 지식으로 우리는 4가 아닌 2사이즈의 임시 버퍼만 할당하면 된다.

병합 방향

병합은 전통적인 병합에서와 같이 왼쪽에서 오른쪽으로 또는 오른쪽에서 왼쪽으로 양방향으로 이루어질 수 있다.

병합 중 갈로핑 모드

R1과 R2의 개별 병합은 런에서 선택한 연속 요소의 카운트를 유지한다.이 숫자가 최소 갈로핑 임계값(min_gallop)에 도달하면, Timsort는 해당 실행에서 많은 연속적인 요소가 선택되어 갈로핑 모드로 전환될 가능성이 있다고 생각한다.R1이 그것을 촉발시킨 책임이 있다고 가정해보자.이 모드에서 알고리즘은 R1 실행에서 R2의 다음 요소 x에 대해 갈로핑 검색이라고도 하는 지수 검색을 수행한다.이것은 두 단계로 이루어진다: 첫 번째 단계는 x가 있는 범위(2^k - 1, 2 - 1)를^k+1 찾는다.두 번째 단계는 첫 번째 단계에서 찾은 범위에서 요소 x에 대한 이진 검색을 수행한다.갤러핑 모드는 런에서 요소들 사이의 간격 패턴에 병합 알고리즘을 적용하려는 시도다.

질주하는 것이 항상 효율적인 것은 아니다.질주 모드에서는 단순한 선형 검색보다 더 많은 비교가 필요한 경우도 있다.개발자가 실시한 벤치마크에 따르면, 질주하는 것은 1회 주행의 초기 요소가 다른 주행의 처음 7회 요소 중 하나가 아닐 때만 유익하다.이는 초기 임계값인 7을 의미한다.질주 모드의 단점을 피하기 위해, (1) 질주하는 것이 바이너리 검색보다 효율성이 낮은 것으로 판명되면 질주 모드를 종료한다. (2) 질주하는 성패는 min_gallop을 조정하는 데 사용된다.선택한 요소가 이전에 요소를 반환한 어레이와 동일한 어레이의 요소인 경우 min_gallop이 1로 감소하므로 갤러핑 모드로 복귀하도록 권장한다.그렇지 않으면 값이 1씩 증가하여 질주 모드로 복귀하지 못하게 된다.랜덤 데이터의 경우 min_gallop 값이 너무 커져서 질주 모드가 절대 반복되지 않는다.^[13]

내림차순 계단진행

또한 내림차순으로 정렬된 데이터를 활용하기 위해 Timsort는 런을 찾아 런 스택에 추가할 때 엄격하게 내림차순 런을 역전시킨다.내림차순 주행은 나중에 맹목적으로 역전되기 때문에, 동일한 요소가 있는 런을 제외하면 알고리즘의 안정성이 유지된다. 즉, 동일한 요소가 역전되지 않는다.

최소 실행 크기

팀소트는 주행 횟수가 2회 주행과 같거나 약간 적을 때 병합이 가장 효율적이며, 주행 횟수가 2회 주행보다 약간 많을 때 특히 효율성이 낮기 때문에 이전 조건을 보장하기 위해 Minrun을 선택한다.^[11]

Minrun은 데이터의 크기를 Minrun으로 나눈 값이 2의 검정력과 같거나 약간 작도록 32에서 64까지의 범위에서 선택된다.최종 알고리즘은 어레이 크기의 가장 중요한 6개의 비트를 취하며, 나머지 비트가 하나라도 설정되면 하나를 추가하고, 그 결과를 Minrun으로 사용한다.이 알고리즘은 64보다 작은 어레이를 포함한 모든 어레이에 대해 작동하며, 크기가 63 이하인 어레이의 경우, 이는 어레이 크기와 동일한 minrun을 설정하고 Timsort는 삽입 정렬로 축소한다.^[11]

분석

최악의 경우 Timsort는 O${\displaystyle (n}$ $){\displaystyle O(n\log n)}$를 비교하여 n 요소의 배열을 정렬한다.입력이 이미 정렬되었을 때 발생하는 최선의 경우, 그것은 적응형 정렬 알고리즘이라는 것을 의미하는 선형 시간으로 실행된다.^[3]

Quicksort보다 개체 참조나 포인터를 정렬하는 데 유리하다. 이는 데이터에 접근하고 비교를 수행하기 위해 값비싼 메모리를 필요로 하고 Quicksort의 캐시 일관성 이점이 크게 감소하기 때문이다.

형식검증

2015년 EU FP7 ENVISAGE 프로젝트의 네덜란드와 독일 연구자들은 팀소트의 표준 구현에서 버그를 발견했다.^[14]2015년 파이썬, 자바, 안드로이드 등에서 고정됐다.

특히, 스택 실행 크기의 불변제는 필요한 스택의 최대 크기에 대한 엄격한 상한을 보장한다.구현은 2바이트의⁶⁴ 입력을 정렬하기에 충분한 스택을 미리 할당하고, 추가적인 오버플로 검사를 피했다.

다만 보증은 불변자가 3회 연속 출격하는 모든 조에 적용하도록 돼 있지만 시행은 상위 3회만 체크했다.^[14]연구원들은 Java 소프트웨어의 공식적인 확인을 위해 KeY 도구를 사용하여 이 검사로는 충분하지 않으며, 실행 길이(및 이러한 실행 길이를 생성하는 입력값)를 찾을 수 있었으며, 이로 인해 불변성이 스택의 상단을 병합한 후 스택의 더 깊은 곳에서 위반될 수 있다는 것을 발견했다.^[15]

결과적으로, 특정 입력의 경우 할당된 크기가 모든 비잠금 실행을 보유하기에 충분하지 않다.Java에서 이것은 그러한 입력에 대해 배열-아웃-오-바운드 예외를 생성한다.Java 및 Android v7에서 이 예외를 트리거하는 가장 작은 입력은 67108864(2²⁶) 크기입니다(이전의 Android 버전은 65536(2) 크기의¹⁶ 특정 입력에 대해 이미 이 예외를 트리거함).

Java 구현은 업데이트된 최악의 경우 분석을 기반으로 사전 할당된 스택의 크기를 증가시킴으로써 수정되었다.이 기사는 또한 공식적인 방법으로 스택에서 가장 상위 4개의 런이 위의 두 가지 규칙을 만족하는지 확인함으로써 의도된 불변성을 확립하는 방법을 보여주었다.이 접근법은 Python과^[16] Android에 의해 채택되었다.

참조

추가 읽기

• Auger, Nicolas; Nicaud, Cyril; Pivoteau, Carine (2015). "Merge Strategies: from Merge Sort to TimSort". hal-01212839.
• 오거, 주게, 니카우, 피보토(2018)."팀소트의 최악의 복잡성에 대하여"ESA 2018.
• 샘 버스, 알렉산더 노프"안정적 병합 정렬 전략" SODA 2019

외부 링크

• 시간을 재다txt – Tim Peters의 원래 설명