라딕스 분류

Radix sort
라딕스 분류
클래스정렬 알고리즘
데이터 구조배열
최악의 경우 공연( ) 여기서 n은 키 수, w는 키 길이.
최악의 경우 공간 복잡성

컴퓨터 과학에서 라딕스 분류는 비교 정렬 알고리즘이다.원소의 라디스에 따라 버킷으로 원소를 만들어 분배함으로써 비교를 회피한다.둘 이상의 유의한 자릿수를 가진 요소의 경우, 모든 자릿수가 고려될 때까지 이전 단계의 순서를 유지하면서 각 자릿수에 대해 이 버킷 프로세스를 반복한다.이러한 이유로 라딕스 분류는 버킷 분류와 디지털 분류라고도 불린다.

라딕스 분류는 어휘, 단어, 펀치 카드, 플레이 카드 또는 우편물 등 사전 통계학적으로 정렬할 수 있는 데이터에 적용할 수 있다.

역사

Radix는 1887년까지 표로 만든 기계에 관한 Herman Hollerith의 작업으로 거슬러 올라간다.[1]Radix 정렬 알고리즘은 1923년 초에 펀치된 카드를 정렬하는 방법으로 널리 사용되었다.[2]

이 분류법에 대한 최초의 메모리 효율적인 컴퓨터 알고리즘은 1954년 MIT에서 해롤드 H에 의해 개발되었다. 시워드.컴퓨터화된 라믹스 종류는 알 수 없는 크기의 버킷의 가변적 할당에 대한 필요성 때문에 이전에는 비실용적인 것으로 간주되지 않았다.시워드의 혁신은 선형 스캔을 사용하여 필요한 버킷 크기와 오프셋을 미리 결정함으로써 보조 메모리를 하나의 정적 할당을 허용하는 것이었다.선형 스캔은 Seward의 다른 알고리즘인 계수 정렬과 밀접하게 관련되어 있다.

현대에 있어서, 라딕스 분류는 이진 문자열과 정수의 집합에 가장 일반적으로 적용된다.일부 벤치마크에서는 범용 정렬 알고리즘이 다른 범용 정렬 알고리즘보다 빠를 수 있으며, 때로는 50%에서 3배 더 빠를 수 있다.[3][4][5]

한 IBM 카드 정렬기가 펀치된 대형 카드 세트에서 라딕스 정렬을 수행하고 있다.카드는 작업자의 턱 아래 호퍼에 공급되며 카드의 한 열에 펀칭된 데이터를 기반으로 기계의 13개 출력 바구니 중 하나로 분류된다.입력 호퍼 근처의 크랭크는 소트 진행에 따라 읽기 헤드를 다음 열로 이동시키는 데 사용된다.뒤쪽의 랙에는 이전 분류 패스의 카드가 들어 있다.

디지트 순서

라딕스 정렬은 가장 유의한 자리(MSD) 또는 가장 유의하지 않은 자리(LSD)에서 시작하도록 구현될 수 있다.예를 들어 1234로 1(MSD) 또는 4(LSD)로 시작할 수 있다.

LSD radix 정렬은 일반적으로 다음과 같은 정렬 순서를 사용한다: 짧은 키는 긴 키보다 먼저 오고, 같은 길이의 키는 사전순으로 정렬된다.이는 순서[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]와 같은 정상 정수 표현 순서와 일치한다.LSD 종류는 일반적으로 안정된 종류다.

MSD radix 정렬은 문자열 또는 고정 길이 정수 표현에 가장 적합하다.[b, c, e, d, f, g, ba]와 같은 순서는 [b, ba, ba, c, d, e, f, g]로 분류될 것이다.사전 편찬 순서를 사용하여 가변 길이 정수를 베이스 10으로 정렬할 경우, 1부터 10까지의 숫자는 [1, 10, 2, 3, 4, 5, 6, 7, 8, 9]로 출력된다. 마치 짧은 키를 가장 긴 키만큼 길게 만들기 위해 빈 문자로 오른쪽에 패딩한 것처럼 말이다.중복 키의 원래 순서가 항상 유지되어야 하는 경우 MSD 정렬이 반드시 안정적인 것은 아니다.

통과 순서 외에 MSD와 LSD 정렬은 가변 길이 입력의 처리 방식이 다르다.LSD 정렬은 길이에 따라 그룹화하고, 라딕스는 각 그룹을 분류한 다음, 크기 순서로 그룹을 연결시킬 수 있다.MSD 정렬은 모든 짧은 키를 가장 큰 키 크기로 효과적으로 '확장'하고 그에 따라 정렬해야 하는데, 이는 LSD가 요구하는 그룹화보다 더 복잡할 수 있다.

그러나 MSD 분류는 세분화와 재귀에 더 적합하다.MSD 단계에서 생성된 각 버킷은 이전 단계에서 생성된 다른 버킷을 참조하지 않고 다음 가장 중요한 숫자를 사용하여 라디스를 정렬할 수 있다.마지막 숫자에 도달하면 버킷 연결만 하면 정렬이 완료된다.

예

최하위 자리수

입력 목록:

[170, 45, 75, 90, 2, 802, 2, 66]

가장 오른쪽(마지막) 숫자부터 시작하여 해당 숫자를 기준으로 다음 숫자를 정렬하십시오.

[{170, 90}, {2, 802, 2}, {45, 75}, {66}]

다음 왼쪽 자릿수로 정렬:

[{02, 802, 02}, {45}, {66}, {170, 75}, {90}]
802가 두 2s 사이에서 위치를 유지하도록 암시적 숫자 0이 두 2s에 대해 앞에 붙는다는 점에 유의하십시오.

마지막으로 가장 왼쪽 자리까지:

[{002, 002, 045, 066, 075, 090}, {170}, {802}]
0은 1자리 또는 2자리 숫자에 모두 앞에 붙는다는 점에 유의하십시오.

각 항목을 다른 요소와 비교하지 않고 버킷에 넣을 수 있기 때문에 각 단계에는 데이터 위에 한 번만 통과하면 된다.

일부 radix 정렬 구현에서는 키를 버킷으로 이동하기 전에 먼저 각 버킷에 속하는 키 수를 세어 버킷에 공간을 할당한다.각 숫자가 배열로 저장되는 횟수.

카운트를 사용하여 버킷 경계를 미리 결정하는 것은 항상 가능하지만, 일부 구현에서는 대신 동적 메모리 할당을 사용하기로 선택한다.

가장 유의한 숫자, 앞으로 재귀

입력 목록, 선행 0이 있는 고정 너비 숫자 문자열:

[170, 045, 075, 025, 002, 024, 802, 066]

버킷을 나타내는 대괄호가 있는 첫 번째 숫자:

[{045, 075, 025, 002, 024, 066}, {170}, {802}]
170과 802는 버킷에 남아 있는 모든 것이므로 더 이상 재귀가 필요하지 않기 때문에 이미 완료되었다는 점에 유의하십시오.

다음 숫자:

[{ {002}, {025, 024}, {045}, {066}, {075} }, 170, 802]

최종 숫자:

[ 002, { {024}, {025} }, 045, 066, 075 , 170, 802]

이제 연결만 남았다.

[002, 024, 025, 045, 066, 075, 170, 802]

복잡성과 성능

Radix 정렬은 O(nw) 시간으로 작동하며, 여기서 n은 키 수, w는 키 길이다.위에서 설명한 대로 가변 길이 키를 그룹으로 나눌 때 LSD 변형은 '평균 키 길이'의 하한을 달성할 수 있다.

최적화된 라딕스 정렬은 자신에게 맞는 도메인에서 작업할 때 매우 빠를 수 있다.[6]그들은 사전 편찬 데이터에 제약을 받지만, 많은 실제 적용의 경우 이것은 제한이 아니다.키 크기가 크면 유도 패스 수가 병목현상이 될 때 LSD 구현을 방해할 수 있다.[2]

전문변형

MSD radix 정렬 구현

이진 퀵소트라고도 하는 이진 MSD radix 정렬은 입력 배열을 0s bin과 1s bin이라는 두 개의 bin으로 나누어 인플레이스 방식으로 구현할 수 있다.0s bin은 배열의 시작부터 자라는 반면, 1s bin은 배열의 끝에서 자라는 것이다.0s bin 경계는 첫 번째 배열 요소 앞에 배치된다.1s bin 경계는 마지막 배열 요소 뒤에 배치된다.첫 번째 배열 요소의 가장 중요한 비트를 검사한다.이 비트가 1일 경우 첫 번째 요소는 1s bin 경계(배열의 마지막 요소) 앞에 있는 요소와 교환되며, 1s bin은 1s 경계 배열 지수를 감소시켜 한 요소만큼 성장한다.이 비트가 0이면 첫 번째 원소는 현재 위치에 남아 있고 0s bin은 한 원소에 의해 성장한다.검사된 다음 배열 요소는 0s bin 경계(즉, 0s bin 또는 1s bin에 없는 첫 번째 요소) 앞에 있는 것이다.이 과정은 0s bin과 1s bin이 서로 닿을 때까지 계속된다.그런 다음 0s bin과 1s bin은 각 어레이 요소의 다음 비트를 기반으로 반복적으로 정렬된다.최소 중요 비트가 정렬에 사용될 때까지 재귀적 처리가 계속된다.[7][8]부호화된 정수를 취급하려면 반대 감각으로 가장 유의한 비트를 취급해야 하며, 그 다음에 나머지 비트의 부호 없는 처리가 필요하다.

인플레이스 MSD 바이너리-라디ix 정렬은 더 큰 라디ix까지 확장될 수 있으며, 인플레이스 기능을 유지할 수 있다.계산 정렬은 각 빈의 크기와 시작 지수를 결정하는 데 사용된다.스와핑은 현재 요소를 해당 빈에 넣은 다음 빈 경계를 확장하는 데 사용된다.배열 요소가 스캔되면 전체 배열이 처리되고 모든 요소가 각각의 빈에 포함될 때까지 빈을 건너뛰고 빈 사이의 요소만 처리된다.빈의 수는 사용된 라디스와 동일하다 - 예를 들어 16-라디스의 16개 빈.각 패스는 가장 유의한 숫자부터 시작하여 한 자릿수(16-radix의 경우 한 자릿수당 4비트)를 기준으로 한다.그런 다음 모든 숫자를 정렬에 사용할 때까지 다음 숫자를 사용하여 각 빈을 재귀적으로 처리한다.[9][10]

위의 단락에서 논하는 인플레이스 바이너리-라믹스 분류나 n비트-라믹스 분류는 모두 안정된 알고리즘이 아니다.

안정적인 MSD Radix 정렬 구현

MSD radix 정렬은 안정적인 알고리즘으로 구현할 수 있지만 입력 어레이와 같은 크기의 메모리 버퍼 사용이 필요하다.이 여분의 메모리는 입력 버퍼를 첫 번째 배열 요소에서 마지막 순서로 스캔할 수 있게 하고, 배열 요소를 동일한 순서로 대상 빈으로 이동시킨다.따라서 동일한 요소가 입력 배열에서와 동일한 순서로 메모리 버퍼에 배치될 것이다.MSD 기반 알고리즘은 첫 번째 재귀 수준의 출력으로 여분의 메모리 버퍼를 사용하지만, 출력 결과를 다시 입력 버퍼로 복사하는 오버헤드를 피하기 위해 다음 수준의 재귀에서 입력과 출력을 스왑한다.각 빈은 MSD radix sort에서와 같이 재귀적으로 처리된다.마지막 자릿수까지의 정렬이 완료된 후 출력 버퍼에서 원본 입력 배열인지 확인하고, 그렇지 않은 경우에는 단일 복사를 실시한다.키 크기를 숫자 크기로 나눈 값이 짝수일 정도로 숫자 크기를 선택하면 끝의 복사는 피한다.[11]

하이브리드 접근 방식

각 재귀 레벨의 첫 번째 통과 시 카운팅 정렬을 사용하는 투패스 방식과 같은 라딕스 정렬은 상수 오버헤드가 크다.따라서 빈이 작아지면 삽입 정렬과 같은 다른 정렬 알고리즘을 사용해야 한다.삽입 분류의 좋은 구현은 작은 배열, 안정적, 내부적, 그리고 라딕스 분류의 속도를 현저히 높일 수 있다.

병렬 컴퓨팅에 대한 애플리케이션

이 재귀적 정렬 알고리즘은 각 빈을 독립적으로 정렬할 수 있기 때문에 병렬 컴퓨팅에 특별히 적용된다.이 경우 각 빈은 사용 가능한 다음 프로세서로 전달된다.시작 부분(가장 중요한 숫자)에는 단일 프로세서가 사용될 것이다.두 번째 또는 세 번째 자리까지 사용 가능한 모든 프로세서가 결속될 가능성이 높다.이상적으로는 각 소분할이 완전하게 정렬됨에 따라 점점 더 적은 수의 프로세서가 활용될 것이다.최악의 경우, 모든 키가 서로 동일하거나 거의 동일할 것이며, 그 결과 키를 정렬하기 위해 병렬 컴퓨팅을 사용하는 것은 거의 또는 전혀 이점이 없을 것이다.

최상위 재귀 수준에서 병렬 처리를 위한 기회는 알고리즘의 계수 분류 부분에 있다.카운트는 병렬_reduce 패턴에 따라 매우 병렬적이며 메모리 대역폭 한계에 도달할 때까지 여러 코어에 걸쳐 작업을 잘 분할한다.알고리즘의 이 부분은 데이터 독립 병렬이 있다.그러나 후속 재귀 수준에서 각 빈을 처리하는 것은 데이터에 의존한다.예를 들어, 모든 키가 같은 값이라면, 그 안에 어떤 요소가 들어 있는 빈은 단 한 개뿐일 것이고, 병렬은 사용할 수 없을 것이다.임의 입력의 경우 모든 빈은 거의 균등하게 채워져 있고 많은 양의 병렬 처리 기회를 이용할 수 있을 것이다.[12]

더 빠른 병렬 정렬 알고리즘을 사용할 수 있다. 예를 들어 최적의 복잡성 O(log(n)는 Three Hungians, Richard Cole)와[13][14] Batcher의 바이토닉 병합 분류는 O(log2(n)의 알고리즘 복잡성을 가지고 있으며, 모두 CRUE-PRAM에서 라딕스 분류에 대한 알고리즘 시간 복잡성이 낮다.가장 빨리 알려진 PRAM 종류는 1991년 데이비드 파워스가 암묵적으로 파티셔닝을 수행하여 n개의 프로세서로 CRCW-PRAM에서 O(log(n)시간 내에 작동할 수 있는 병렬 퀵소트, 그리고 K가 최대 키 길이인 O(k)에서 동일한 트릭을 사용하여 작동하는 라딕소트(Radixsort)를 사용하여 설명한 것이다.[15]그러나 PRAM 아키텍처나 단일 순차 프로세서는 실제로 O(log(n)로 증가함에 따라 사이클당 일정한 팬아웃 게이트 지연 횟수가 증가하지 않고 확장되는 방식으로 구축될 수 없으므로, 사실상 배쳐링된 버전의 비트론 병합 및 O(log(n) PRAM 정렬이 클럭 사이클, Wi-Cycle 측면에서 모두 O(log2(n)이다.Powers는 O2(nlog([16]n)의 키 길이 독립적인 정렬 네트워크에 대해 Batcher의 병렬 퀵소트 및 라딕스 정렬 또는 콜의 병합 정렬보다 게이트 지연 측면에서 상수가 낮다는 것을 인정한다.

트리 기반 래딕스 정렬

라딕스 정렬은 입력 세트에서 트리(또는 라딕스 트리)를 만들고 사전 주문 트래버설을 수행함으로써 이루어질 수도 있다.이것은 힙포트와 힙 데이터 구조 사이의 관계와 유사하다.이 기능은 특정 데이터 유형에 유용할 수 있다(버스트ort 참조).

참고 항목

참조

  1. ^ US 395781 및 영국 327
  2. ^ a b 도널드 크누스컴퓨터 프로그래밍의 기술 제3권: 정렬과 검색, 제3판애디슨 웨슬리, 1997년 ISBN0-201-89685-0.제5.2.5장: 분포에 의한 분류, 페이지 168–179.
  3. ^ "I Wrote a Faster Sorting Algorithm". 28 December 2016.
  4. ^ "Is radix sort faster than quicksort for integer arrays?". erik.gorset.no.
  5. ^ "Function template integer_sort - 1.62.0". www.boost.org.
  6. ^ "Efficient Trie-Based Sorting of Large Sets of Strings".
  7. ^ R. Sedgewick, "C++의 알고리즘", 제3판, 1998, 페이지 424-427
  8. ^ Duvanenko, Victor J. "Algorithm Improvement through Performance Measurement: Part 2". Dr. Dobb's.
  9. ^ Duvanenko, Victor J. "Algorithm Improvement through Performance Measurement: Part 3". Dr. Dobb's.
  10. ^ Duvanenko, Victor J. "Parallel In-Place Radix Sort Simplified". Dr. Dobb's.
  11. ^ Duvanenko, Victor J. "Algorithm Improvement through Performance Measurement: Part 4". Dr. Dobb's.
  12. ^ Duvanenko, Victor J. "Parallel In-Place N-bit-Radix Sort". Dr. Dobb's.
  13. ^ A. 기븐스와 W. 라이터, 효율적인 병렬 알고리즘.케임브리지 대학 출판부, 1988년
  14. ^ H. 카사노바 외, 평행 알고리즘.채프먼 & 홀, 2008년
  15. ^ David M. W. Powers, Parallelized Quicksort and Radixsort with Optimal Speedup, Parallel Computing Technologies에 관한 국제 회의의 진행.노보시비르스크 1991.
  16. ^ David M. W. Powers, 병렬 통일: 실무적 복잡성, 오스트레일리아 컴퓨터 건축 워크숍, 플린더스 대학교, 1995년 1월

외부 링크