인내 정렬

Patience sorting
인내 정렬
클래스정렬 알고리즘
데이터 구조배열
최악의 경우 공연O(n log n)
베스트 케이스 공연O(n); 입력을 미리[1] 정렬할 때 발생

컴퓨터 과학에서 인내가 분류되는 것은 카드 게임 인내가 영감을 받아 이름을 붙인 분류 알고리즘이다.알고리즘의 변형은 주어진 배열에서 가장 긴 증가 부속물의 길이를 효율적으로 계산한다.

개요

알고리즘의 이름은 인내 카드 게임의 단순화된 변형에서 유래한다.게임은 뒤범벅이 된 카드들로 시작된다.카드는 다음 규칙에 따라 차례대로 탁자 위에 쌓여 있다.[2]

  1. 처음에는 말뚝이 없다.처리된 첫 번째 카드는 단일 카드로 구성된 새로운 더미를 형성한다.
  2. 각각의 후속 카드는 새로운 카드의 값보다 크거나 같은 값을 가진 가장 왼쪽의 기존 더미 또는 모든 기존 더미의 오른쪽에 배치되어 새로운 더미를 형성한다.
  3. 처리할 카드가 더 이상 남지 않으면 게임은 끝난다.

이 카드 게임은 다음과 같이 2상 분류 알고리즘으로 전환된다.완전히 순서가 지정된 도메인에서 n개의 요소가 배열된 경우 이 배열을 카드 모음으로 간주하고 인내심 정렬 게임을 시뮬레이션하십시오.게임이 끝났을 때 최소 가시 카드를 반복해서 뽑아서 정렬된 순서를 회복하고, 다시 말해 p 말뚝의 k-way 병합을 각각 내부적으로 정리한 것이다.

분석

1단계 인내심 분류인 카드 게임 시뮬레이션은 최악의 경우 O(n log n) 비교를 위해 구현될 수 있다. 즉, 최대 n개의 말뚝이 있을 것이고, 시공에 의해 말뚝의 상단 카드가 왼쪽에서 오른쪽으로 증가하는 순서를 형성하기 때문에 원하는 말뚝을 2진 검색으로 찾을 수 있다.[1]두 번째 단계인 말뚝 병합은 우선순위 대기열을 사용하여 O(n log n) 시간에 수행될 수 있다.[1]

입력 데이터에 자연적인 "실행(runs)" 즉, 감소하지 않는 하위 선(subarrays)이 포함된 경우, 성능은 엄격히 개선될 수 있다.실제로 입력 배열이 이미 정렬된 경우 모든 값이 단일 더미를 형성하고 두 단계 모두 O(n) 시간에 실행된다.평균 사례 복잡성은 여전히 O(n log n): 모든 값의 균일 무작위 시퀀스는 예상된 수의 O(n) 말뚝을 생성하며,[3] 이는 생산과 병합에 O(n log √n) = O(n log n) 시간이 걸린다.[1]

인내심의 실제 성과에 대한 평가는 찬드라무리와 골드스타인에 의해 주어지는데, 이들은 순진한 버전이 그들의 벤치마크 문제에 대한 최첨단 퀵서비스보다 약 10배에서 20배 느리다는 것을 보여준다.그들은 이것을 인내의 종류에 투입된 비교적 적은 양의 연구 때문이라고 보고, 그것의 성과를 퀵소트 2의 요소 내에 가져오는 몇 가지 최적화를 개발한다.[1]

만약 카드의 값이 1, . . . . . n의 범위에 있다면, Van Emde Boas 트리에 의존하여 카드를 더미 속에 넣기 위한 O(n log n) 최악의 실행 시간을 가진 효율적인 구현이 있다.[3]

다른 문제와의 관계

인내심 분류는 플로이드의 게임이라는 카드 게임과 밀접한 관련이 있다.이 게임은 앞서 스케치한 게임과 매우 유사하다.[2]

  1. 처리된 첫 번째 카드는 단일 카드로 구성된 새로운 더미를 형성한다.
  2. 각각의 후속 카드는 새로운 카드의 가치 이상이나 그 이상의 가치를 지닌 기존의 일부 더미 또는 기존의 모든 더미 오른쪽에 배치되어 새로운 더미를 형성한다.
  3. 처리할 카드가 더 이상 남지 않으면 게임은 끝난다.

게임의 목적은 가능한 한 적은 더미로 끝내는 것이다.인내 분류 알고리즘과의 차이점은 새 카드를 허용된 가장 왼쪽의 파일 위에 배치할 필요가 없다는 것이다.인내심 분류는 이 게임을 하기 위한 탐욕스러운 전략이다.

알두스와 디아코니스는 9개 이하의 말뚝을 n = 52에 대한 승리 결과로 정의할 것을 제안한다. n = 52는 대략 5%의 확률로 발생한다.[4]

가장 오래 증가하는 부분 집합을 찾기 위한 알고리즘

먼저 위에서 설명한 대로 정렬 알고리즘을 실행한다.말뚝의 수는 가장 긴 여분의 길이다.카드를 더미 위에 놓을 때마다 이전 더미의 상위 카드에 백 포인터를 놓으십시오(가정할 경우 새 카드보다 값이 낮음).결국, 마지막 더미의 상단 카드에서 백 포인터를 따라 가장 긴 길이의 감소하는 반복을 복구하십시오. 그 역방향은 가장 긴 반복 알고리즘에 대한 대답이다.

S. Bespamyatnikh와 M.Segal은[3] 알고리즘의 효율적인 구현에 대한 설명을 제공하며, 정렬에 대한 추가적인 무증상 비용이 발생하지 않는다(백포인트 저장, 생성 및 통과에는 선형적인 시간과 공간이 필요하므로).그들은 또한 동일한 결과 데이터 구조에서 가장 오랫동안 증가된 모든 부분을 보고하는 방법을 보여준다.

역사

인내의 분류는 C. L. Mallows에 의해 명명되었는데, 그는 1960년대 초 이 발명품의 발명을 A.S.C. Ross의 탓으로 돌렸다.[1]알두스와 디아콘리스에 따르면,[4] 해머슬리가 가장 길게 증가시키는 부분 길이를 계산하기 위한 알고리즘으로 인내가 먼저 인정되었다.[5]틀:축구단 로스, 로버트 W 플로이드는 그것을 분류 알고리즘으로 인식했다.초기 분석은 Mallows에 의해 수행되었다.[6]플로이드의 게임은 플로이드에 의해 도널드 크누스와 통신하여 개발되었다.[2]

사용하다

프로세스 제어에는 인내 정렬 알고리즘을 적용할 수 있다.일련의 측정에서, 오랫동안 증가되는 부분들의 존재는 트렌드 마커로 사용될 수 있다.SQL Server 매거진에 실린 2002년 기사는 이러한 맥락에서 가장 오랫동안 증가된 부분들의 길이에 대한 인내심 분류 알고리즘에 대한 SQL 구현을 포함하고 있다.[7]

참조

  1. ^ a b c d e f Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (PDF). SIGMOD/PODS.
  2. ^ a b c Burstein, Alexander; Lankham, Isaiah (2006). "Combinatorics of patience sorting piles" (PDF). Séminaire Lotharingien de Combinatoire. 54A. arXiv:math/0506358. Bibcode:2005math......6358B.
  3. ^ a b c Bespamyatnikh, Sergei; Segal, Michael (2000). "Enumerating Longest Increasing Subsequences and Patience Sorting". Information Processing Letters. 76 (1–2): 7–11. CiteSeerX 10.1.1.40.5912. doi:10.1016/s0020-0190(00)00124-1.
  4. ^ a b Aldous, David; Diaconis, Persi (1999). "Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem". Bulletin of the American Mathematical Society. New Series. 36 (4): 413–432. doi:10.1090/s0273-0979-99-00796-x.
  5. ^ Hammersley, John (1972). A few seedlings of research. Proc. Sixth Berkeley Symp. Math. Statist. and Probability. Vol. 1. University of California Press. pp. 345–394.
  6. ^ Mallows, C. L. (1973). "Patience sorting". Bull. Inst. Math. Appl. 9: 216–224.
  7. ^ Kass, Steve (April 30, 2002). "Statistical Process Control". SQL Server Pro. Retrieved 23 April 2014.