플래시소트

Flashsort는 균일하게 분산된 데이터 세트에 대한 선형 계산 복잡성 O(n)를 나타내는 분포 정렬 알고리즘이며, 비교적 적은 추가 메모리 요구 사항이다.원작은 1998년 칼 디에트리히 뉴베르트에 의해 출판되었다.^[1]

개념

Flashsort는 히스토그램 정렬의 효율적인 인플레이스 구현이며, 그 자체가 버킷 정렬의 한 유형이다.각 n 입력 요소를 m 버킷 중 하나에 할당하고 입력을 효율적으로 재배열하여 버킷을 올바른 순서로 배치한 다음 각 버킷을 정렬한다.원래 알고리즘은 입력 배열 A를 다음과 같이 정렬한다.

1. 입력 또는 사전 지식을 통해 첫 번째 패스를 사용하여 최소 및 최대 정렬 키를 찾으십시오.
2. 범위[A_min, A_max]를 m 버킷으로 선형 분할한다.
3. 각 버킷에 포함되는 요소 A의_i 수를 세면서 입력을 한 번 통과하십시오. (Neubert는 버킷을 "분류"라고 부르고 요소 할당을 "분류"라고 부른다.)
4. 각 버킷의 요소 카운트를 접두사 합으로 변환하십시오. 여기서 L은_b 버킷 b 또는 그 이하에 있는 요소 A의_i 수입니다.(L_0m = 0, L = n.)
5. 각 버킷 b의 모든 요소에 대한 입력을 재정렬하여 위치_b−1 A에_i 저장한다. 위치 A에서는 L < i ≤ L_b.
6. 삽입 정렬을 사용하여 각 버킷을 정렬하십시오.

1~3단계와 6단계는 모든 버킷 분류에 공통적이며 버킷 분류에 일반적인 기술을 사용하여 개선할 수 있다.특히, 목표는 버킷의 크기가 대략 같으며(^[1]각 n/m 원소) 이상적인 값은 m 퀀텀 단위로 나누는 것이다.기본 알고리즘이 선형 보간 분류인 반면 입력 분포가 균일하지 않은 것으로 알려진 경우, 비선형 분할은 이 이상에 더 가깝게 근접하게 된다.마찬가지로, 최종 분류는 재귀 플래시 분류 등 다양한 기법을 사용할 수 있다.

플래시 정렬을 구분하는 것은 5단계: 추가 메모리의 m 단어만 사용하여 각 버킷의 요소를 정확한 상대적 순서로 함께 수집하는 효율적인 O(n) 인플레이스 알고리즘이다.

메모리 효율적 구현

Flashsort 재배열 단계는 사이클로 작동한다.원소들은 "분류되지 않은" 것부터 시작해서, 올바른 버킷으로 옮겨져 "분류되지 않은" 것으로 간주된다.기본 절차는 미분류 원소를 선택하고 정확한 버킷을 찾아 그곳에서 미분류 원소와 교환(각 버킷의 크기를 미리 세었기 때문에 존재해야 함)한 후 분류로 표시한 다음 방금 변경되지 않은 미분류 원소로 반복하는 것이다.결국 원소는 자신과 교환되고 주기는 끝난다.

자세한 내용은 버킷당 두 개의(단어 크기) 변수를 사용하여 쉽게 이해할 수 있다.가장 현명한 부분은 그러한 변수들 중 하나를 제거하는 것으로, 버킷을 두 배 더 사용할 수 있고 따라서 최종 O(n²) 정렬에 소요되는 시간의 반을 허용한다.

버킷당 두 개의 변수를 사용하여 이해하려면 두 개의 추가 단어 배열이 있다고 가정하십시오. K는_b 버킷 b(및₀ K = 0)의 (고정) 상한이고 L은_b 버킷 b에 대한 (이동 가능) 지수이므로 K_b−1 ≤ L_b ≤ K_b.

우리는 각 버킷을 L에_b 의해 분류되지 않은 접두사(A_ib−1 for K < i ≤ L은_b 아직 그들의 대상 버킷으로 이동되지 않았다)와 분류된 접미사(A_ib for L < i ≤ K는_b 모두 정확한 버킷에 있고 다시는 이동되지 않는다)로 나누는 루프 불변성을 유지한다.초기_b L = K와_b 모든 원소는 분류되지 않는다.정렬이 진행됨에 따라 L은 모든_b b에 대해_b L = K가_b−1 될 때까지 감소하고 모든 원소는 올바른 버킷으로 분류된다.

각 라운드는 첫 번째 불완전하게 분류된 버킷 c(K_c−1 < L이_c 있는 것)를 찾아 그 버킷_i A에서_c−1 첫 번째 미분류 요소를 취함으로써 시작된다. 여기서 i = K + 1. (Neubert는 이것을 "사이클 리더"라고 부른다.)A를_i 임시 변수 t에 복사하고 반복하십시오.

• t가 속한 버킷 b를 계산한다.
• j = L은_b t가 저장될 위치가 되도록 한다.
• 이전 값 A를_j 가져오는 동안 t를 A로_jj 교환, 즉 A에 저장 t를 교환하여 재배치하십시오.
• A가_j 이제 올바르게 분류되었다는 사실을 반영하기 위해 L을_b 감소시킨다.
• j가 i인 경우, 새 t로 이 루프를 재시작한다.
• j = i이면 이 라운드가 끝나고 새로운 첫 번째 미분류 요소 A를_i 찾는다.
• 더 이상 분류되지 않은 요소가 없으면 버킷으로의 분배가 완료된다.

이러한 방식으로 버킷당 두 개의 변수로 구현될 때 각 라운드의 출발점 i의 선택은 사실상 임의적이다. 분류되지 않은 모든 요소를 사이클 리더로 사용할 수 있다.유일한 요건은 사이클 리더를 효율적으로 찾을 수 있다는 것이다.

앞의 서술은 K를 사용하여 사이클 리더를 찾지만, 실제로는 그것 없이 할 수 있어 m 워드 배열 전체를 없앨 수 있다.(분포가 완료된 후 버킷 경계는 L에서 찾을 수 있다.)

모든 요소를 i-1까지 분류했으며 A를_i 잠재적인 새로운 사이클 리더로 고려하고 있다고 가정합시다.그것의 목표 버킷 b를 계산하는 것은 쉽다.루프 불변제에 의해 L_b < i ≤ K이면_b 분류되고, 내가 그 범위를 벗어나면 분류되지 않는다.첫 번째 불평등은 시험하기 쉽지만 두 번째 불평등은 K_b 값을 요구하는 것으로 보인다.

i-1까지의 모든 원소가 분류된다는 유도 가설은 i ≤ K를_b 내포하고 있으므로 제2의 불평등을 시험할 필요가 없다는 것이 밝혀졌다.

내가 어떤 위치에 있는지 버킷 c를 생각해봐.즉, K_c−1 < i ≤ K_c. 유도 가설에 의해 K_c−1 < i까지의 모든 양동이를 포함하는 i 아래의 모든 원소가 완전히 분류된다.즉, 해당 버킷에 속하는 요소가 배열의 나머지 부분에 남아 있지 않다.따라서 b < c는 가능하지 않다.

유일하게 남은 경우는_b b c c로 K ≥ K_c ≥ i, Q.E.D.를 내포하고 있다.

이를 통합하여 플래시소트 분포 알고리즘은 위에서 설명한 L과 i = 1로 시작한다.그런 다음 계속하십시오.^[1][2]

• i > n이면 분포가 완성된다.
• A가_i 지정된 경우, A가 속한 버킷 b를 계산하십시오.
• 만약_i 내가 L이라면_b A는 분류되지 않는다.임시 변수 t 및 다음을 복사하십시오.
  • j = L은_b t가 저장될 위치가 되도록 한다.
  • 이전 값 A를_j 가져오는 동안 t를 A로_jj 교환, 즉 A에 저장 t를 교환하여 재배치하십시오.
  • A가_j 이제 올바르게 분류되었다는 사실을 반영하기 위해 L을_b 감소시킨다.
  • j ≠ i인 경우 t가 속한 버킷 b를 계산하고 새 t로 이 (내부) 루프를 다시 시작한다.
• A는_i 이제 정확하게 분류되었다.i를 증분하고 (외부) 루프를 다시 시작하십시오.

플래시소트는 메모리를 절약하면서도 이미 분류된 많은 요소들을 위해 버킷을 재조합한다는 단점이 있다.이는 이미 요소당 두 번(버킷 카운팅 단계에서 한 번, 각 요소를 이동할 때 두 번째) 수행되지만, 첫 번째 미분류 요소를 검색하려면 대부분의 요소에 대해 세 번째 계산이 필요하다.단순 선형 보간법보다 더 복잡한 공식을 사용하여 버킷을 할당하면 비용이 많이 들 수 있다.변형은 미완성 버킷의 마지막 미분류 요소를 사이클 리더로 취함으로써 계산 횟수를 거의 3n에서 최대 2n + m - 1로 줄인다.

• 불완전하게 분류된 첫 번째 버킷을 식별하는 변수 c를 유지한다.c = 1로 시작하고, c > m이 되면 분포가 완성된다.
• Let i = L_c. i = L이면_c−1 c를 증가시키고 이 루프를 다시 시작한다.(L₀ = 0)
• A가_i 속한 버킷 b를 계산한다.
• 만약 b < c, 그러면_c L = K_c−1 그리고 우리는 버킷 c를 끝낸다.c를 증분하고 이 루프를 다시 시작하십시오.
• b = c이면 분류는 사소한 것이다.L을_c 줄이고 이 루프를 다시 시작하십시오.
• b > c이면 A는_i 분류되지 않는다.이전 사례와 동일한 분류 루프를 수행한 다음 이 루프를 다시 시작하십시오.

대부분의 원소는 각 버킷의 최종 원소를 제외하고 그들의 버킷을 두 번만 계산한다. 단, 이 버킷의 완료를 감지하는 데 사용된다.분류되지 않은 원소의 카운트를 유지하고 그것이 0에 도달했을 때 정지함으로써 약간의 추가 감소를 달성할 수 있다.

퍼포먼스

유일한 추가 메모리 요구 사항은 버킷 경계를 저장하기 위한 보조 벡터 L과 사용된 다른 변수의 일정한 수입니다.또한 각 요소는 (임시 버퍼를 통해) 한 번만 이동하므로 두 번의 이동 작업만 수행된다.그러나 이러한 메모리 효율성은 어레이가 랜덤으로 액세스되므로 전체 어레이보다 작은 데이터 캐시를 활용할 수 없다는 단점이 있다.

모든 버킷 종류와 마찬가지로 성능도 버킷의 균형에 따라 결정적으로 달라진다.균형 잡힌 데이터 세트의 이상적인 경우, 각 버킷의 크기는 대략 동일할 것이다.버킷의 숫자 m이 입력 크기 n에서 선형인 경우 각 버킷은 일정한 크기를 가지므로 삽입 정렬과 같은 O(n²) 알고리즘으로 단일 버킷을 정렬하면 복잡도 O(1) = O(1)가² 된다.따라서 최종 삽입 정렬의 실행 시간은 m ⋅ O(1) = O(m) = O(n)이다.

m에 대한 값, 버킷 수, 요소 분류에 소요된 시간(높은 m)과 최종 삽입 정렬 단계에서 소요된 시간(낮은 m)을 교환한다.예를 들어 m을 √n에 비례하여 선택하면 최종 삽입 정렬의 실행 시간은 따라서 m ⋅ O(√n²) = O(n^3/2)가 된다.

거의 모든 요소가 몇 개의 버킷 안에 있는 최악의 경우, 알고리즘의 복잡성은 최종 버킷 정렬 방법의 성능에 의해 제한되므로 O(n²)로 저하된다.알고리즘의 변형은 일정한 크기 제한을 초과하는 버킷에 퀵소트 또는 재귀 플래시 소트 같은 더 나은 성능의 종류를 사용함으로써 최악의 성능을 향상시킨다.^[2][3]

균일하게 분포된 랜덤 데이터를 가진 m = 0.1 n의 경우, 플래시 소트는 모든 n에 대해 힙소트보다 빠르고 n > 80에 대한 퀵소트보다 빠르다.그것은 n = 10000에서 퀵소트보다 약 2배 빨라진다.^[1]이러한 측정은 메모리 계층이 캐시에 훨씬 덜 의존했던 1990년대 후반에 수행된 것이라는 점에 유의하십시오.

플래시소트가 분류 과정에서 수행하는 상황 순열화 때문에 플래시소트는 안정적이지 않다.안정성이 필요한 경우 제2배열을 사용할 수 있어 원소를 순차적으로 분류할 수 있다.그러나 이 경우 알고리즘에는 O(n) 추가 메모리가 필요하다.

참고 항목

• 보간 검색, 정렬이 아닌 검색에 항목 배포 사용

참조

외부 링크

• 대형 평행 기계에 대한 무작위 정렬 구현(1992)
• 병렬 알고리즘 구현(1992)
• FlashSort의 시각화