본 내용은 http://www.drdobbs.com/architecture-and-design/algorithm-improvement-through-performanc/220300654의 내용을 번역한 것이다.
기수(radix) 소팅 알고리즘은 배열의 요소들을 서로 비교하지 않기 때문에 비교 기반의 O(nlogn) 성능 제약에 걸리지 않는다. 사실, 그들은 O(kn)의 선형 성능을 가진다. 기수(radix) 정렬은 배열 요소 값의 최상위 숫자(most significant digit, MSD) 혹은 최하위 숫자(least significant digit, LSD) 한 숫자 값만을 취해서 처리한다. 예를 들어, 다음의 두자리 숫자를 정렬하기 하려면 다음과 같이 한다.
각 숫자들을 최상위 숫자값(10의 자리)을 기준으로 쪼개어 저장소(bin, 빈)에 저장해 둔다.
다음 자리 숫자(1의 자리)에 기준하여 빈을 쪼갠다.
빈에서 최상위 숫자 중 가장 작은 값, 그 다음 자리 숫자의 가장 작은 값을 순서대로 모은다.
기수 정렬을 구현하는 방법은 입력 배열을 취해서 각 요소의 최상위 숫자를 보는 것이다. 한 빈(구현시는 독립된 배열)은 숫자 0을 위한 빈, 1을 위한 빈, 2를 위한 빈, ... 9를 위한 빈을 생성한다. 모든 배열 요소들을 최상위 숫자가 빈 숫자와 일치하는 곳에 넣는다. 다음으로 다음 숫자값을 기준으로 순환적으로 각 빈으로 구분하여 넣는다. 모든 숫자가 그들이 가진 모든 숫자들에 대해서 개별 빈들에 분류가 되었다면, 최상위 숫자 중 가장 작은 숫자 값, 그리고 다음 숫자 중 가장 작은 값의 순서로 조합한다; 예를 들어, 모든 00 빈에 있는 모든 숫자, 다음으로 01 빈, 다음으로 02 빈, ..., 09 빈, 10 빈, 11빈, 그리고 계속 해서 99 빈에 있는 숫자를 모은다. 이 결과는 정렬된 배열이다.
기수 정렬의 한 약점은 입력 배열 외에도 (빈을 위한) 추가적인 공간 소모이다; 즉, 이것은 그자리에서(in-place) 수행하는 정렬이 아닌 것이다. 예를 들어, 인텔의 성능 향상 원시 데이터 라이브러리(Integrated Performance Primitives (IPP) library)는 다음의 함수 호출 프로토타입을 구현한다.
IppStatus ippsSortRadixAscend_32u_I(Ipp32u* pSrcDst, Ipp32u* pTmp, Ipp32s len);
이 알고리즘에서는 원래 입력 벡터[1]과 동일한 크기의 임시 벡터 pTmp가 요구된다. 이 배열이 pSrcDst로 명명 되었음을 알 수있고, 이는 배열이 정렬을 위한 입력과 출력 동시에 이용됨을 나타낸다. 인텔의 IPP는 또한 기수 정렬이 아닌 방식의 정렬의 경우 다음의 함수 호출 프로토타입을 가진다.
IppStatus ippsSortAscend_32s_I(Ipp32s* pSrcDst, int len);
이것은 추가적인 저장공간이 필요하지 않음을 나타낸다 -- 즉 원본 배열을 그대로 이용하여(in-place) 정렬을 수행한다.
기수는 반드시 십진수일 필요는 없고 , 어떠한 정수라도 될 수있다. 예를 들어, decimal-기수는 십진수(0 부터 9까지의 값들), hex-기수는 16진수(0부터 15의 값), octal-기수는 8진수(0부터 7까지의 값), 그리고 binary-기수는 2진수(0과 1)을 가진다.
이진수
10진수는 인간에게 익숙하지만, 2진수가 가장 작은 유용한 진수이다. 이진수에는 오직 2개의 가능한 빈이 있다: 0과 1의 빈이다. 예를 들어, 배열은 시작부터 끝까지 최상위 숫자들을 확인하면서 검사된다. 2진수에서 이 최상위 숫자는 최상위 비트(most significant bit, MSB) 이다. 만약, MSB가 0이면, 배열 요소는 0의 빈으로 가고, 아니면, MSB가 1일 때, 1의 빈으로 간다.
원본 배열을 이런 두 빈들로 쪼갠 후에, 0의 빈에 있는 요소의 수와 1의 빈에 있는 요소의 수의 합은 원본 배열에 있는 요소의 수가 된다. 다음의 비트를 이용하여 0의 빈은 이제 또다시 0과 1의 빈으로 쪼개어질 수 있다. 동일한 일이 1의 빈에도 수행될 수 있다. 이 작업은 모든 비트들이 소비될 때까지 재귀적으로 계속된다. 그림 1은 이 단계를 보인다.
예를 들어, 만약 배열 요소가 32비트라면, 개별 배열 요소에 대해 32번의 반복이 수행될 것이고, 이 과정은 개별 요소를 0과 1의 빈에 개별 32비트 값들로 정렬할 것이다. 그러므로, 이진 기수 정렬은 O(kn)이며, 여기에서 k는 개별 배열 요소의 비트 수이며, n은 배열 요소의 개수이다. 다시 말하면, 개별 배열 요소들은 32번 처리될 것이며, 한 번의 처리에서 한 개의 비트를 처리한다.
제자리 특성(in-place)
제자리 특성은 정렬 알고리즘의 유용한 특싱이다. 즉, 입력 배열은 추가적인 메모리 없이 정렬되며, 출력 배열로 이용된다. 만약, 한 알고리즘이 제자리 특성을 지원하면, 지원하는 정렬 알고리즘 보다 큰 배열을 처리할 수 있다. 이 차이점은 인텔의 IPP 라이브러리의 기수 정렬 함수에 보였고, 이는 제자리 정렬을 지원하지 않기 때문에 원본 배열 크기와 동일한 추가적인 메모리를 요구한다. 하지만, IPP의 제자리 특성을 지원하는 다른 정렬들은 추가적인 메모리가 필요하지 않다.
이진수 기수 정렬은 다음 기법에 의해서 제자리 정렬로 수행될 수 있다. 0이나 1의 빈을 위한 추가적인 메모리를 할당하는대신에, 원본 배열은 두 빈의 요소들을 저장하는데 이용될 수 있다. 0의 빈은 배열의 시작부터 처리되고, 1의 빈은 배열의 끝에서부터 처리된다. 빈으로 분류하는 것이 완료되면, 이 두 빈들은 배열 어디선가 만나고 서로 겹치지 않는다.
최상위 비트 (MSB)에 기반하여 정렬을 수행하는 알고리즘의 다음 단계가 아래에 보여진다. 왼쪽에 있는 포인터는 0의 빈의 현재 위치를 추적한다. 오른쪽에 있는 포인터는 1의 빈의 현재 위치를 추적한다.
3비트 이진값들로 시작
a0의 MSB가 0이므로, a0는 그대로 둔다. (왼쪽 포인터는 오른쪽으로 한 요소 크기만큼 움직이고, 오른쪽 포인터는 그대로 있다.)
a1의 MSB가 1이므로, a1과 a5에 있는 값을 교환한다. (오른쪽 포인터는 교환 후 왼쪽으로 한 칸 옮긴다.)
a1의 MSB가 1이므로, a1과 a4에 있는 값을 교환한다. (오른쪽 포인터는 교환 후 왼쪽으로 한 칸 옮긴다.)
a1의 MSB가 1이므로, a1과 a3에 있는 값을 교환한다. (오른쪽 포인터는 교환 후 왼쪽으로 한 칸 옮긴다.)
a1의 MSB가 0이므로, a1는 그대로 둔다.
a2의 MSB는 1이므로, a2와 a2를 교환한다.
포인터가 교차 되었으므로, MSB에 의한 정렬은 완료되었다.
여기에서 명심할 것은 0의 MSB를 가진 모든 배열 요소들이 배열의 왼쪽으로 옮겨졌고, 1의 MSB를 가진 모든 배열 요소들은 오른쪽으로 이동했다(첫번째 이진수 비트를 기준으로). 배열은 아직 완전히 정렬되지 않았다. 이 알고리즘은 0의 빈(배열의 왼쪽)과 1의 빈(배열의 오른쪽)에 대해서, 재귀적으로 수행되며, 다음 비트 값에 의해서 정렬된다. 다음으로 알고리즘은 마지막 비트를 기준으로 또 한번 재귀적으로 호출함으로써 정렬한다.
아래는 제자리 이진-기수 정렬 알고리즘을 보인다.
// Copyright(c), Victor J. Duvanenko, 2009
// In-place Binary Radix Sort implementations.#ifndef _InPlaceBinaryRadixSort1_h#define _InPlaceBinaryRadixSort1_h// Swap that does not check for self-assignment.template< class _Type >inline void _swap( _Type& a, _Type& b ){ _Type tmp = a; a = b; b = tmp;}template< class _Type >inline void _binaryRadixSort_initialUnsigned( _Type* a, long first, long last, _Type bitMask ){ // Split the provided array range into 0's and 1's bins long _zerosEndPlusOne = first; // index is one beyond the last 0's bin long _onesEndMinusOne = last; // index is one before the first 1's bin for ( ; _zerosEndPlusOne <= _onesEndMinusOne; ) { if ( 0 == ( bitMask & a[ _zerosEndPlusOne ] )) // 0's bin { // this element belongs in the 0's bin // it stays at its current location and the 0's bin size is increased _zerosEndPlusOne++; } else { // 1's bin _swap( a[ _zerosEndPlusOne ], a[ _onesEndMinusOne ] ); // move this element to 1's bin _onesEndMinusOne--; // increase the 1's bin size } } // At this point the provided array portion has been split into 0's bin and 1's bin // Recursively call to sort this 0's bin and this 1's bin using the next bit lower bitMask >>= 1; if ( bitMask != 0 ) // end recursion when all the bits have been processes { if ( first < ( _zerosEndPlusOne - 1 )) _binaryRadixSort_initialUnsigned( a, first, _zerosEndPlusOne - 1, bitMask ); if (( _onesEndMinusOne + 1 ) < last ) _binaryRadixSort_initialUnsigned( a, _onesEndMinusOne + 1, last, bitMask ); }}inline void binaryRadixSortInPlace_initialUnsigned( unsigned long* a, unsigned long a_size ){ if ( a_size < 2 ) return; unsigned long bitMask = 0x80000000; _binaryRadixSort_initialUnsigned( a, 0, a_size - 1, bitMask );}endif // _InPlaceBinaryRadixSort_h최바깥단의 루틴인 binaryRadixSortInPlace_initialUnsigned()는 초기의 비트 마스크를 설정하여 최상위 비트를 선택하고, 템플릿 함수 _binaryRadixSort_initialUnsigned()를 호출한다. 이 핵심 함수는 제공되는 는 배열의 처음과 끝 범위의 요소들을 0과 1의 빈으로 제자리에서 쪼갠다. 다음으로 비트 마스크를 오른쪽으로 시프트 연산 시켜서 다음 하위 비트를 선택하고, 재귀적으로 스스로를 두번 호출한다. 즉, 한 번은 0의 빈, 그리고 두번째는 1의 빈을 위해서 수행한다. 쪼개는 과정에서 알고리즘은 제네릭 함수 템플릿 _swap()을 이용해서 요소를 1의 빈으로 보낸다.
표 1은 임의의 양의 정수 32비트 요소의 배열에 대한 제자리 이진-기수 정렬, STL 정렬, 그리고 인텔의 IPP 기수 정렬 함수의 성능 비교를 보인다. 인텔의 IPP 라이브러리는 다양한 입력 자료 형태를 다루는 기수 정렬 외의 정렬 알고리즘을 가지나 32비트 양의 정수에 대한 것이 없다.
표 1. 임의의 32-비트 양수들
이 측정값들과 그들로부터 계산된 비율들은 이진-기수 정렬이 임의 입력 자료 집합에 대한 STL의 정렬 성능에 근접함을 보인다. 인텔의 IPP 기수 정렬은 32비트 양의 정수에 대해서 이진-기수 정렬의 4-6배 가량 빨랐다.
실험 설정
정확도 검증을 위한 한 방법은 STL의 정렬 알고리즘과 동일한 결과를 나타내는지 비교하는 것인데, 이것은 STL의 정렬이 옳다는 가정하 에서이다. STL 정렬의 정확도에 의존하지 않기 위해서는 정렬 알고리즘을 위한 정확도 테스트를 구현해야한다.
정확도는 배열[i] ≤ 배열[i+1]가 모든 배열 요소에 대해 성립하는지 보는 것이고, 이는 간단히 검사할 수 있다. 물론, STL 정렬 결과와 비교하는 것 역시 중복되지만 유용한 검증일 것이다. 이 두 테스트들은 모든 구현된 루틴들에 대해서 이용되었고, 이것은 인텔의 IPP 라이브러리 루틴들에 대해서도 마찬가지이다. 경계 값에 있는 입력 배열의 경우인 크기 0과 1에 대해서도 테스트 되었다.
성능 비교를 위한 설정은 다음과 같다.
- 비쥬얼 스튜디오 2008, 최적화 프로젝트 설정은 스피드, 크기, 그리고 적합한 함수에 대한 인라이닝 어떠한 것도 수행하지 않았다.
- 인텔 Core 2 듀오 CPU E8400, 3 GHz(64 Kb L1 캐시와 6 Mb L2 캐시)
- 14-단계 파이프라인 1,333 MHz 앞단 버스
- 2 GB 시스템 메모리(듀얼 채널, 채널당 64-bits, 800 MHz DDR2)
- 메인 보드는 DQ35JOE.
배열에 있는 요소들은 임의의 숫자는 다음 방법을 이용해서 생성되었다.
// each call to rand() produces 15-bit random number.
unsigned long tmp = ((unsigned long)rand()) << 30 | ((unsigned long)rand())<< 15 | ((unsigned long)rand());배열은 유일한 값들의 비율(%)에 대해서 검사도이써고, 모두 95%의 배열이 32 비트 양의 정수값으로 채워졌다. 최소와 최대 범위는 개별 배열에 대해서 검사되었고, 이 값은 0과 32비트 양의 정수 최대 값에 근접한 값 사이였다.
성능은 항상 1억개의 값들에 대해 처리하여 측정되었다. 즉, 10개의 배열이 측정될 때, 1000만개의 요소들이 할당되었다. 이 때, 100개의 배열이 측정된다면, 100만 개의 요소들이 할당되는 식이다. 개별 배열에 대해서 다른 임의 숫자 생성기의 씨드 값이 사용되었지만, 알고리즘 별로는 동일한 씨드값들을 사용하여 측정하였다. 1억개의 배열들을 정렬 전후에 시간을 측정했고, 이 값의 평균 값을 보고했다.
혼합 방식
STL의 sort 함수 구현은 3개의 다른 알고리즘의 개별적인 최상의 특성을 추출하여 구현되었고, 이로 인해 전반적으로 최상의 성능을 보인다. STL 정렬은 퀵 정렬, 힙 정렬, 그리고 삽입 정렬 알고리즘의 최고의 특성을 조합하며, 이는 특정 상황에서 한 알고리즘이 다른 알고리즘을 뛰어 넘을 때 적용된다. 그것은 재귀 호출 깊이의 1.5*log2(n) 분할에 대해서 퀵소트를 이용하고, 분할이 32 요소 이상을 가지고 있을 때는 힙 정렬을, 분할이 32와 2개 요소 사이일 경우엔 삽입 정렬을 이용한다. 삽입 정렬은 이진 재귀 호출 트리의 리프 노드에서 좋은 캐시 응집(cache locality)를 제공하고, 입력 데이터에 적응적이다. 대략 32 요소들에서 재귀 호출을 피함으로써 작은 입력 데이터에 대해서 함수 호출과 반환 오버헤드를 줄일 수 있다.
동일하게 좋은 방법이 기수 정렬(이진 또는 그 이상의 기수)에 대해서도 적용될 수 있다. 다음 코드는 그런 구현을 보이며, 이것은 삽입 정렬을 [4]로 부터 가져온 버전을 이용하며, 코드에도 추가했다.
// Copyright(c), Victor J. Duvanenko, 2009
// In-place Binary Radix Sort implementations.#ifndef _InPlaceBinaryRadixSort2_h#define _InPlaceBinaryRadixSort2_h// Swap that does not check for self-assignment.template< class _Type >inline void _swap( _Type& a, _Type& b ){ _Type tmp = a; a = b; b = tmp;}template< class _Type >inline void insertionSortSimilarToSTLnoSelfAssignment( _Type* a, unsigned long a_size ){ for ( unsigned long i = 1; i < a_size; i++ ) { if ( a[ i ] < a[ i - 1 ] ) // no need to do (j > 0) compare for the first iteration { _Type currentElement = a[ i ]; a[ i ] = a[ i - 1 ]; unsigned long j; for ( j = i - 1; j > 0 && currentElement < a[ j - 1 ]; j-- ) { a[ j ] = a[ j - 1 ]; } a[ j ] = currentElement; // always necessary work/write } // Perform no work at all if the first comparison fails - i.e. never assign an element to itself! }}inline void _binaryRadixSort_wInsertion( unsigned long* a, long first, long last, unsigned long bitMask ){ if (( last - first ) > 32 ) { // Split the provided array range into 0's and 1's sub-ranges long _zerosEndPlusOne = first; // index is one beyond the last 0's portion long _onesEndMinusOne = last; // index is one before the first 1's portion for ( ; _zerosEndPlusOne <= _onesEndMinusOne; ) { if ( 0 == ( bitMask & a[ _zerosEndPlusOne ] )) // 0's portion { // nothing to do, as this is our 0's portion of the array _zerosEndPlusOne++; } else { // 1's portion _swap( a[ _zerosEndPlusOne ], a[ _onesEndMinusOne ] ); _onesEndMinusOne--; } } // Recursively call to sort 0's portion and 1's portion using the next bit lower bitMask >>= 1; if ( bitMask != 0 ) { if ( first < ( _zerosEndPlusOne - 1 )) _binaryRadixSort_wInsertion( a, first, _zerosEndPlusOne - 1, bitMask ); if (( _onesEndMinusOne + 1 ) < last ) _binaryRadixSort_wInsertion( a, _onesEndMinusOne + 1, last, bitMask ); } } else { insertionSortSimilarToSTLnoSelfAssignment( &a[ first ], last - first + 1 ); }}inline void binaryRadixSortInPlace_wInsertion( unsigned long* a, unsigned long a_size ){ if ( a_size < 2 ) return; unsigned long bitMask = 0x80000000; _binaryRadixSort_wInsertion( a, 0, a_size - 1, bitMask );}endif // _InPlaceBinaryRadixSort_h표 2에서 5, 그리고 그래프 1은 혼합 이진-기수 정렬과 STL 정렬, IPP의 기수 정렬의 성능을 비교한다.
표 2. 임의의 양의 32비트 값들
그래프 1
표 3. 증가시킨 양의 32비트 값들
표 4. 감소시킨 양의 32비트 값들
이들 측정 값들과 이들로 부터 계산된 비율들은 혼합 이진-기수 정렬이 임의의 입력 자료 집합에 대해서 STL 정렬의 20% 가량의 성능을 웃도는 것을 보이지만, 증가되거나 감소된 입력 자료 집합에 대해서는 아님을 보인다. 이렇게 증가되거나 감소된 경우에 40% 까지의 성능 하락이 있다. 인텔의 IPP 기수 정렬은 임의의 입력 자료에 대해서 최소 3X 가량 다른 정렬을 웃도는 성능을 보였으나 다른 입력 자료 통계에서는 STL 정렬보다 늦었다.
개선점
여러 가지 비효율성이 위에 보인 6개의 3비트 숫자 정렬 예제에서 명확하다.
- 알고리즘의 다음 포인터에서 끝 포인터까지 가는 단계에서, 요소 a2가 스스로를 교체 시도했다.
- 코드의 셋째와 넷째 줄에서, 1의 빈에 속한 요소들끼리 교환이 수행되었다.
첫째 개선은 [4]에 사용된 방법과 유사하게 구현할 수 있고, 여기에서는 스스로에 대한 할당의 경우 추가적인 작업 없이 수행되도록 고쳐졌다. 이 경우에, 마지막 루프의 경우 for 루프에서 빠질 수 있는데 이는 <=를 <으로 고치면서 수정할 수 있다. 이런 세밀한 차이점은 다음과 같다.
if (_zerosEndPlusOne == _onesEndMinusOne )
위의 코드는 불필요하며, 제거될 수 있다. 왜냐하면 모든 재귀 호출이 개별 빈이 최소한 2개의 요소를 가지고 있는지 확인하기 때문이다. 그런 까닭에, for 루프는 최소한 한 개의 루프에 대해 처리하는 것이 보장되기 때문에, "==" 상황이 루프가 다 처리된 후에 해야할 것으로 바뀌게 된다; 가령, 가장 마지막에 해야하는 일은 한 개의 요소값이 남은 경우이다(그리고 이 경우에는 교환이 불필요하다). 이 경우에 명심할 것은, 이 비교 상황을 처리하기 위해서 실제로 해야하는 작업이 줄었다는 점이다. 왜냐하면, "==" 비교 구문이 사라졌기 때문이다. 이 최적화는 임의의 32비트 양의 정수 자료에 대해서 4-5% 성능 향상을 이룬다. 그 구현은 다음의 코드에서 보인다.
// Copyright(c), Victor J. Duvanenko, 2009
// In-place Binary Radix Sort implementations.#ifndef _InPlaceBinaryRadixSort3_h#define _InPlaceBinaryRadixSort3_h// Swap that does not check for self-assignment.template< class _Type >inline void _swap( _Type& a, _Type& b ){ _Type tmp = a; a = b; b = tmp;}template< class _Type >inline void insertionSortSimilarToSTLnoSelfAssignment( _Type* a, unsigned long a_size ){ for ( unsigned long i = 1; i < a_size; i++ ) { if ( a[ i ] < a[ i - 1 ] ) // no need to do (j > 0) compare for the first iteration { _Type currentElement = a[ i ]; a[ i ] = a[ i - 1 ]; unsigned long j; for ( j = i - 1; j > 0 && currentElement < a[ j - 1 ]; j-- ) { a[ j ] = a[ j - 1 ]; } a[ j ] = currentElement; // always necessary work/write } // Perform no work at all if the first comparison fails - i.e. never assign an element to itself! }}template< class _Type >inline void _binaryRadixSortNoSelfAssignment_unsigned( _Type* a, long first, long last, _Type bitMask ){ // Split the provided array range into 0's and 1's portions long _zerosEndPlusOne = first; // index is one beyond the last 0's portion long _onesEndMinusOne = last; // index is one before the first 1's portion for ( ; _zerosEndPlusOne < _onesEndMinusOne; ) { if ( 0 == ( bitMask & a[ _zerosEndPlusOne ] )) // 0's portion { // this element belongs in the 0's portion // so just keep it in its place and grow the 0's portion size _zerosEndPlusOne++; } else { // 1's portion _swap( a[ _zerosEndPlusOne ], a[ _onesEndMinusOne ] ); // move this element to 1's portion _onesEndMinusOne--; } } if ( 0 == ( bitMask & a[ _zerosEndPlusOne ] )) // 0's portion { _zerosEndPlusOne++; } else { // 1's portion _onesEndMinusOne--; // No swap is needed, since it's self-assignment } // Recursively call to sort 0's portion and 1's portion using the next bit lower bitMask >>= 1; if ( bitMask != 0 ) // end recursion when all the bits have been processes { if ( first < ( _zerosEndPlusOne - 1 )) // call only if number of elements >= 2 _binaryRadixSortNoSelfAssignment_unsigned( a, first, _zerosEndPlusOne - 1, bitMask ); if (( _onesEndMinusOne + 1 ) < last ) // call only if number of elements >= 2 _binaryRadixSortNoSelfAssignment_unsigned( a, _onesEndMinusOne + 1, last, bitMask ); }}inline void binaryRadixSortInPlaceNoSelfAssignment_unsigned( unsigned long* a, unsigned long a_size ){ if ( a_size < 2 ) return; unsigned long bitMask = 0x80000000; _binaryRadixSortNoSelfAssignment_unsigned( a, 0, a_size - 1, bitMask );}endif // _InPlaceBinaryRadixSort_h두번째 개선은 [5]에 의해서 나타났고, 위의 정렬 예제에서 명확하게 보여졌다. 다음의 코드는 1의 빈에 포함된 요소의 교환을 제거했다. 알고리즘은 0의 빈에 있는 교체 가능한 요소를 찾는 와중에 1의 빈에 있는 포인터의 위치를 변경한다.
// Copyright(c), Victor J. Duvanenko, 2009// In-place Binary Radix Sort implementations.#ifndef _InPlaceBinaryRadixSort4_h#define _InPlaceBinaryRadixSort4_h// Swap that does not check for self-assignment.template< class _Type >inline void _swap( _Type& a, _Type& b ){ _Type tmp = a; a = b; b = tmp;}template< class _Type >inline void insertionSortSimilarToSTLnoSelfAssignment( _Type* a, unsigned long a_size ){ for ( unsigned long i = 1; i < a_size; i++ ) { if ( a[ i ] < a[ i - 1 ] ) // no need to do (j > 0) compare for the first iteration { _Type currentElement = a[ i ]; a[ i ] = a[ i - 1 ]; unsigned long j; for ( j = i - 1; j > 0 && currentElement < a[ j - 1 ]; j-- ) { a[ j ] = a[ j - 1 ]; } a[ j ] = currentElement; // always necessary work/write } // Perform no work at all if the first comparison fails - i.e. never assign an element to itself! }}template< class _Type >inline void _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( _Type* a, long first, long last, _Type bitMask ){ if (( last - first ) > 32 ) { // Split the provided array range into 0's and 1's bins long _zerosEndPlusOne = first; // index is one beyond the last 0's portion long _onesEndMinusOne = last; // index is one before the first 1's portion for ( ; _zerosEndPlusOne <= _onesEndMinusOne; ) { if ( 0 == ( bitMask & a[ _zerosEndPlusOne ] )) // 0's bin { _zerosEndPlusOne++; // grow 0's bin } else { // 1's portion do // Locate an element that belongs in 0's portion, to eliminate unnecessary swaps { if ( 0 != ( bitMask & a[ _onesEndMinusOne ])) { _onesEndMinusOne--; // grow 1's bin of the array } else { _swap( a[ _zerosEndPlusOne ], a[ _onesEndMinusOne ] ); _onesEndMinusOne--; _zerosEndPlusOne++; // grow 0's and 1's - found a perfect swap match break; // switch back to the 0's bin } } while( _zerosEndPlusOne <= _onesEndMinusOne ); } } // Recursively call to sort 0's portion and 1's portion using the next bit lower bitMask >>= 1; if ( bitMask != 0 ) { if ( first < ( _zerosEndPlusOne - 1 )) _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( a, first, _zerosEndPlusOne - 1, bitMask ); if (( _onesEndMinusOne + 1 ) < last ) _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( a, _onesEndMinusOne + 1, last, bitMask ); } } else { insertionSortSimilarToSTLnoSelfAssignment( &a[ first ], last - first + 1 ); }}inline void binaryRadixSortInPlace( unsigned char* a, unsigned long a_size ){ if ( a_size < 2 ) return; unsigned char bitMask = 0x80; _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( a, 0, a_size - 1, bitMask );}inline void binaryRadixSortInPlace( unsigned short* a, unsigned long a_size ){ if ( a_size < 2 ) return; unsigned short bitMask = 0x8000; _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( a, 0, a_size - 1, bitMask );}inline void binaryRadixSortInPlace( unsigned long* a, unsigned long a_size ){ if ( a_size < 2 ) return; unsigned long bitMask = 0x80000000; _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( a, 0, a_size - 1, bitMask );}inline void binaryRadixSortInPlace( unsigned __int64* a, unsigned long a_size ){ if ( a_size < 2 ) return; unsigned __int64 bitMask = 0x8000000000000000ui64; _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( a, 0, a_size - 1, bitMask );}endif // _InPlaceBinaryRadixSort_h
알고리즘이 0의 요소를 찾을 때, 알고리즘은 관련된 두 요소들이 그들의 최종 위치의 빈으로 갈 것임을 아는 상태에서 교환을 수행한다. 이 두 요소들은 다시 교체되지 않을 것이다(즉, 0과 1을 가리키고 있는 두 포인터의 값들이 교환 후에 동시에 변경된다.) 수정된 알고리즘 단계는 아래에 보인다.
3비트 이진 값들로 시작
a0의 MSB가 0이므로, a0는 그대로 둔다
a1의 MSB가 1이므로, 1의 빈으로 바꾸고, a5의 MSB는 1이므로, a5는 그대로 둔다
a4의 MSB는 1이므로, a4는 그대로 둔다
a3의 MSB는 1이므로, a1과 a3는 교환되고 두 포인터의 위치는 변경된다
a2의 MSB는 1이므로, a2는 그대로 둔다
포인터가 교차되었으므로, MSB에 의한 정렬은 완료되었다.
이 성능 개선은 초기 구현에 있었던 1의 빈에 속한 요소들 간의 불필요한 교환을 제거한다. 정렬을 수행하기 위한 단계들이 감소했는데 이는 교환이 "완벽" (교환 대상의 요소를 그들의 관련 빈으로 옮김으로써) 하기 때문이고, 이 "완벽"함은 두 포인터의 위치를 동시에 수정할 수 있도록 해준다; 위 예제의 5번째 줄을 보자. 또한, 스스로에 대한 할당 역시 두 경우 모두 제거되었다. 즉, 마지막 요소가 0이나 1의 빈에 있을 때, 스스로에 대한 할당 연산 없이 개별 포인터는 이동한다 (이는 구현에서 보여진다.)
이 성능 개선은 또한 알고리즘에 있는 한가지 불일치를 고친다. 즉, 현재 요소가 1의 빈이 아니라 0의 빈에 속했을 때 0의 빈에서 현재 포인터가 교환없이 오른쪽으로 옮겨졌을 때를 고친다. 이 수정으로 인해, 만약 요소가 1의 빈에 속하고, 1의 빈 위치에 이미 있다면, 알고리즘은 그 자리를 벗어나고, 포인터는 1의 빈에 속하지 않은 요소를 계속 찾는다; 예를 들어, "완벽한" 교환 대상을 찾는다(교환 전에 두 요소 모두 잘못된 빈에 있는 경우)
다른 종결 조건도 가능한며 아래에 보인다.
이 종결 조건 역시 정확하게 마무리되며, 단일 완전한 교환을 수행한 후에 포인터 위치를 수정한다.
최종 버전의 혼합 이진 기수 정렬과 다른 알고리즘들에 대한 성능 측정들은 표 5, 6, 그리고 7에 보인다. 인텔 IPP 라이브러리는 32 비트와 64비트 양의 정수에 대한 비-기수 정렬 구현이 없다.
표 5. 임의 양의 정수들
표 5는 많은 정보를 제공하며, 몇몇 특이한 점들을 보인다.
- 인텔의 기수 정렬은 다른 알고리즘들에 비해서 훨씬 빠르다 -- 8, 16, 32 비트 양의 정수들에 대해서 그들의 근접한 경쟁 알고리즘에 대해서 각각 20x, 8x, 그리고 3x 빠르다.
- 8 비트 양수에 대한 IPP 정렬 알고리즘은 IPP의 기수 정렬과 동일한 것처럼 보이나, 제자리 특성이 있다.
- 16비트 양수에 대한 IPP 정렬은 8비트 버전에 비해 심각하게 성능이 나쁘다. -- 64x 느리다.
- 혼한 이진-기수 정렬은 STL 정렬에 대해서 모든 자료 크기에서 앞섰고, 16비트 IPP 정렬에 비해 최소 15% 정도 빨랐다.
- 표 6과 7은 혼합 이진-기수 정렬이 증가되고 감소된 입력 자료 집합에 대해서 STL과 IPP 정렬을 최소 30% 앞서는 것을 보인다.
- 혼합 이진-기수 정렬은 초기 구현에 비해서 40% 이상의 성능이 향상되었다.
표 6. 증가한 32-비트 양수들
표 7. 감소한 32비트 양수들
오버로딩 함수들을 통해 구현된 제네릭 함수들은 데이터 타입을 인식하기 때문에 삽입 정렬을 사용하는 시점을 나타내는 자료 구조 별 임계값들을 제공할 수 있다. 간단한 실험은 이것은 매우 희망적임을 보이지만, 더 세심한 실험이 있다면 더 좋을 것이다.
부호화된 정수값들
부호화 정수들은 아래에 보이듯이 2의 보수 형태를 이용하며, 아래에는 이진 표기법을 왼쪽에 그리고 10진 표기법을 오른쪽에 나타냈다.
01111111b 12701111110b 12601111101b 125 ….00000001b 100000000b 011111111b -111111110b -211111101b -3 …10000011b -12510000010b -12610000001b -12710000000b -128최상위 비트(MSB)는 부호 비트이다. 하지만, 그것의 의미는 정렬을 위해 요구되는 것과는 반대의 의미를 가진다. 즉, 만약 양수 이진-기수 정렬 알고리즘이 이용되면, 음수 값이 양수 값보다, 크게 인식될 것이며, 이는 음수 값들이 MSB에 1의 값을 가지기 때문이다. 하지만, 나머지 비트들은 양수와 같은 의미를 가진다. -- 한 1의 비트 값은 한 0의 비트 값보다 크다. 그런 까닭에, 부호 비트인 MSB는 반대의 의미로 특별하게 다뤄져야 하며 -- 한 0 의 비트 값은 한 1의 비트값 보다 크다. 다음 코드는 구현을 보이며, 기호가 있는 수의 부호 비트(MSB)를 반대로 다루는 동시에 그 하위 비트에 대해서는 부호 없는 숫자의 재귀 호출 핵심 루틴을 따르는 것을 보인다.
// Copyright(c), Victor J. Duvanenko, 2009
// In-place Binary Radix Sort implementations.#ifndef _InPlaceBinaryRadixSort5_h#define _InPlaceBinaryRadixSort5_h// Swap that does not check for self-assignment.template< class _Type >inline void _swap( _Type& a, _Type& b ){ _Type tmp = a; a = b; b = tmp;}// A set of logical right shift functions to work-around the C++ issue of performing an arithmetic right shift// for >>= operation on signed types.inline char logicalRightShift( char a, unsigned long shiftAmount ){ return (char)(((unsigned char)a ) >> shiftAmount );}inline short logicalRightShift( short a, unsigned long shiftAmount ){ return (short)(((unsigned short)a ) >> shiftAmount );}inline long logicalRightShift( long a, unsigned long shiftAmount ){ return (long)(((unsigned long)a ) >> shiftAmount );}inline __int64 logicalRightShift( __int64 a, unsigned long shiftAmount ){ return (__int64)(((unsigned __int64)a ) >> shiftAmount );}template< class _Type >inline void insertionSortSimilarToSTLnoSelfAssignment( _Type* a, unsigned long a_size ){ for ( unsigned long i = 1; i < a_size; i++ ) { if ( a[ i ] < a[ i - 1 ] ) // no need to do (j > 0) compare for the first iteration { _Type currentElement = a[ i ]; a[ i ] = a[ i - 1 ]; unsigned long j; for ( j = i - 1; j > 0 && currentElement < a[ j - 1 ]; j-- ) { a[ j ] = a[ j - 1 ]; } a[ j ] = currentElement; // always necessary work/write } // Perform no work at all if the first comparison fails - i.e. never assign an element to itself! }}template< class _Type >inline void _binaryRadixSort_wInsertionMinSwapsSymmetric_signedOnly( _Type* a, long first, long last, _Type bitMask ){ if (( last - first ) > 32 ) { // Split the provided array range into 0's and 1's bins long _zerosEndPlusOne = first; // index is one beyond the last 0's portion long _onesEndMinusOne = last; // index is one before the first 1's portion for ( ; _zerosEndPlusOne <= _onesEndMinusOne; ) { if ( 0 != ( bitMask & a[ _zerosEndPlusOne ] )) // 0's bin { _zerosEndPlusOne++; // grow 0's bin } else { // 1's portion do // Locate an element that belongs in 0's portion, to eliminate unnecessary swaps { if ( 0 == ( bitMask & a[ _onesEndMinusOne ])) { _onesEndMinusOne--; // grow 1's bin of the array } else { _swap( a[ _zerosEndPlusOne ], a[ _onesEndMinusOne ] ); _onesEndMinusOne--; _zerosEndPlusOne++; // grow 0's and 1's - found a perfect swap match break; // switch back to the 0's bin } } while( _zerosEndPlusOne <= _onesEndMinusOne ); } } // Recursively call to sort 0's portion and 1's portion using the next bit lower bitMask = logicalRightShift( bitMask, 1 ); if ( bitMask != 0 ) { if ( first < ( _zerosEndPlusOne - 1 )) _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( a, first, _zerosEndPlusOne - 1, bitMask ); if (( _onesEndMinusOne + 1 ) < last ) _binaryRadixSort_wInsertionMinSwapsSymmetric_unsignedOnly( a, _onesEndMinusOne + 1, last, bitMask ); } } else { insertionSortSimilarToSTLnoSelfAssignment( &a[ first ], last - first + 1 ); }}inline void binaryRadixSortInPlace( char* a, unsigned long a_size ){ if ( a_size < 2 ) return; char bitMask = (char)0x80; _binaryRadixSort_wInsertionMinSwapsSymmetric_signedOnly( a, 0, a_size - 1, bitMask );}inline void binaryRadixSortInPlace( short* a, unsigned long a_size ){ if ( a_size < 2 ) return; short bitMask = (short)0x8000; _binaryRadixSort_wInsertionMinSwapsSymmetric_signedOnly( a, 0, a_size - 1, bitMask );}inline void binaryRadixSortInPlace( long* a, unsigned long a_size ){ if ( a_size < 2 ) return; long bitMask = 0x80000000; _binaryRadixSort_wInsertionMinSwapsSymmetric_signedOnly( a, 0, a_size - 1, bitMask );}inline void binaryRadixSortInPlace( __int64* a, unsigned long a_size ){ if ( a_size < 2 ) return; __int64 bitMask = 0x8000000000000000i64; _binaryRadixSort_wInsertionMinSwapsSymmetric_signedOnly( a, 0, a_size - 1, bitMask );}endif // _InPlaceBinaryRadixSort_h이 구현은 모든 기호 있는 8-64비트 숫자를 다루기 위해서 오버로딩 함수를 사용한다. 이것은 기호 없는 숫자에 대한 함수와 일치성 있고 완전히 제네릭화된 구현을 제공하기 때문에 기호 있는 타입이나 없는 타입이나 동일한 인터페이스를 동일한 함수 이름으로 제공해준다. 기호 있는 숫자에 대한 구현 역시 기호 없는 숫자에 대한 검사 단계와 동일하게 테스트 되었다.
기호 있는 구현은 약간의 다른 점이 있다. 그것은 오버로딩된 함수인 logicalRightShift()를 이용한다. 이 함수는 C++이 오른쪽 쉬프트 연산 ">>"을 우리가 원하는 방식이 아닌 산술 쉬프트로 구현했고, 논리 쉬프트로 구현하지 않았기 때문에 필요하다. 흥미롭게도, 자바는 ">>>" 연산자를 선언했으며, 부호 있는 숫자들에 대해 논리 쉬프트 [6]르 수행하며, ">>" 연산은 산술쉬프트를 수행한다. 운나쁘께도 C++이 이런 한계에 멈춰있으며, 이것은 C에 대한 호환성 때문이다. 왜냐하면 C에서 ">>" 연산자가 논리 쉬프트를 의미하고, "/2"가 기호 있는 그리고 기호가 없는 정수에 대한 산술 쉬프트를 의미한다면 훨씬 명확할 것이기 때문이다. 발전된 컴파일러들은 이미 "정수를 2의 급수에 해당하는 상수로의 나누기 연산"을 산술 쉬프트로 최적화한다.
비교 순서
성능 척도가 다른 비교 기반 알고리즘들은, 가령 STL 정렬의 O(nlogn)과 기수 정렬의 O(kn), 한 알고리즘이 다른 알고리즘보다 나은 것을 예측하는데 통찰력을 줄 수 있다. 만약 다른 알고리즘들이 유사한 형태, 가령 O(log2(n)*n) 그리고 O(k*n), 일 때 더욱 쉽게 알 수 있다. 두 식은 n 기호를 동시에 가지고 있으므로 log2(n)과 k를 비교한다 [3]. 다른 방법으로 보는 것은 이 두 수식들을 쪼개는 것이다. 이 경우에, n은 log2(n)/k 비율을 남긴다. 만약 log2(n)이 k보다 크면, 비율은 1보다 클 것이다. 만약 k가 크면, 비율은 1보다 작을 것이다.
표 8은 이 관계를 보인다. 그것은 log2(n)이 n이 두 배 증가될 때 1씩 증가됨을 보인다 -- 이것은 로그 함수의 규칙 중 하나를 따르며, 이 규칙은 log(m*n) = log(m) + log(n)이다. 이 경우에, log2(2*n) = log2(2) + log2(n) = 1 + log2(n)이 된다. 표의 둘째 부분에서 log2(n)이 두 배로 증가하는 동안, n은 제곱으로 증가하는 것을 보이며, 이것은 로그 함수의 다른 규칙을 따르며, 그 규칙은
표 8. 로그 함수와 n
표 8에서, log2(4.3*10^9)=32 이다. -- 예를 들어, n = 4.3E+9, 또는 43억이다. 이 경우에, 배열이 43억 요소를 가지고 있는 경우, O(log(n)*n)=32*4.3*10^9 이며, 이는 STL 정렬 알고리즘의 비교 횟수의 예상치이다.
이진-기수 정렬에 대해서, 척도는 O(k*n) 으로, k는 개별 요소의 비트 수들이다. 만약 요소가 개별적으로 32비트이면, 43억개 요소에 대해서 O(k*n)=32*4.3*10^9 번의 연산이다. 이 경우에, STL 정렬과 이진 기수 정렬의 예측은 동일하다. 8 비트 요소에 대해서, 이진 기수 정렬의 예측치는 8*4.3*10^9이며, 반면, STL은 32*4.3*10^9에 머무르며, 이진-기수 정렬이 더 빠를 것임이 예측된다. 64비트 요소에 대해서 이진 기수 정렬의 예측은 64*4.3*10^9이며, 반면 STL은 32*4.3*10^9에 머물러서 STL 정렬이 더 빠를 것으로 예상된다.
이들 예제들은 STL 정렬이 배열에 있는 요소들의 수에 대해서만 에측된 것이고, 그 크기에 대한 것이 아니며, 이진 기수 정렬의 경우에는 비트의 수와 개별 요소, 그리고 요소의 수에 의해 예측된 것이다. 척도 식은 요소들이 적은 비트들로 이뤄져 있을 경우에 이진 기수 정렬이 STL보다 빠를 것으로 (실제적으로 어떠한 최적의 비교 정렬) 예상한다. 반면, STL 정렬이 요소 크기가 클 때 더 빠를 것으로 예상된다.
표 9는 비교를 위해서 측정된 성능을 보인다. 인텔 IPP는 8비트와 64비트 기호 있는 정수에 대해서 기수 정렬과 비-기수 정렬에 구현하지 않는다.
표 9는 많은 정보를 제공하며, 몇몇 주요한 점들이 있다.
- 모든 알고리즘들은 (존재한다면) 그들의 기호 있는 숫자에 대한 버전에서도 잘 동작했다. 즉 기호 있거나 없는 성능이 거의 동일했다.
- IPP 기수 정렬은 16비트와 32 비트 기호 이쓴 정수에서 모든 다른 알고리즘들 보다 훨씬 빨랐다 -- 그들의 근접한 경쟁 알고리즘에 비해서 8X와 대략 3X 빨랐다.
- 척도 예측은 혼합 이진-기수 정렬에 대해서 8, 16, 32 비트 버전에 대해 정확했으며, 이는 비트의 수(k)가 2배 증가했을 때 성능이 2배 하락했다. 하지만, 64비트의 경우 예측된 것처럼 2배 감소한 것이 아니라, 16% 정도 증가됬다.
- STL 정렬에 대해서 배열 요소의 크기에 성능이 의존하지 않고 요소 수에만 의존하는 것으로 예상하던 척도 예측은 정확하지 않았다. 반면, STL 정렬 성능은 이는 8, 16, 그리고 32-비트 숫자들의 경우 비트의 수가 2배 증가함에 따라 2배 감소했으며, 64-비트 숫자의 경우에는 그렇지 않았다.
- STL 정렬이 이진 기수 정렬을 앞지를 것이라는 척도 예측은 64 비트 숫자에 대해서 일치하지 않았다.
댓글