스프레스포트

Spreadsort

스프레스포트는 스티븐 J. 로스가 2002년에 발명한 분류 알고리즘이다.[1]라딕스 소트, 버킷 소트 등 유통 기반 소트 개념과 퀵소트, 병합 등 비교 소트에서의 파티셔닝 개념을 결합한 것이다.실험 결과, 특히 구조와 문자열 정렬을 보여주는 분포에서 퀵소트와 같은 전통적인 알고리즘을 능가하는 효율성이 높은 것으로 나타났다.성능 분석과 벤치마크,[2] HTML 문서화를 포함한 오픈 소스 구현이 있다.[3]

Quicksort는 목록에서 피벗 요소를 식별한 다음 목록을 피벗보다 작은 요소와 피벗보다 큰 요소 두 개의 하위 목록으로 분할한다.스프레드시트는 각 단계에서 목록을 n/c 파티션으로 분할하여 이 아이디어를 일반화한다. 여기서 n은 목록의 전체 요소 수와 c는 작은 상수(실제로 비교가 느린 경우 4 - 8 사이 또는 빠른 상황에서 훨씬 큰 경우)이다.이를 달성하기 위해 유통 기반 기법을 사용하며, 먼저 리스트에서 최소값과 최대값을 찾아낸 다음, 이들 사이의 영역을 n/c 동일 크기 빈으로 나눈다.캐싱이 문제인 경우, 각 재귀적 분할 단계에서 최대 수의 빈을 보유하는 것이 도움이 될 수 있으며, 이로 인해 분할 프로세스가 여러 단계를 밟게 된다.이렇게 하면 더 많은 반복이 발생하지만, 캐시 누락을 줄이고 알고리즘을 전체적으로 더 빠르게 실행할 수 있다.

빈의 수가 최소한 원소의 수인 경우, 스프레드는 버킷 분류로 변질되고 정렬이 완료된다.그렇지 않으면 각 빈은 반복적으로 정렬된다.알고리즘은 휴리스틱 테스트를 사용하여 각 빈이 스프레드시트 또는 다른 고전적 정렬 알고리즘에 의해 보다 효율적으로 정렬되는지 여부를 확인한 다음, 반복적으로 빈을 정렬한다.

다른 배포 기반 분류와 마찬가지로 스프레드시트는 프로그래머가 각 요소를 숫자 키로 변환하는 방법을 제공하도록 요구된다는 약점을 가지고 있다.각 요소가 무한히 많은 최소값을 따르는 것을 고려하여 문자열과 같은 임의의 길이 요소에 대해, 그리고 실제로 총질서를 갖는 데이터 형식에 대해서는, 이것을 할 수 있지만, 이것은 특히 복잡한 구조에서, 단순한 비교 함수보다 정확하게 구현하기가 더 어려울 수 있다.이 값 함수의 구현이 불량하면 알고리즘의 상대적 성능을 해치는 클러스터링이 발생할 수 있다.

퍼포먼스

스프레드시트의 최악의 성능은 소형 데이터 세트의 경우 O(n log n)로 인트로포트를 예비로 사용하기 때문이다.비트 k 곱하기 2의 키 크기가 목록 크기 n 또는 그 이하(2k < (log n))2의 로그의 대략 제곱인 분포의 경우, 최악의 경우 더 잘하여, 최초 발행된 버전의 O(n nk - log n) 최악의 경우, 캐시 인식 버전의 O(n·(k/s) + s)를 달성한다.문자열 정렬을 포함하여 1000개 이상의 항목에서 실제 정렬 문제가 발생할 경우 이 증상이 없는 최악의 경우는 O(n log n)보다 낫다.

최적화된 스프레드시트의 버전을 고도로 최적화된 C++와 비교한 실험이 수행되었다.std::sort, introsort로 구현.정수와 플로트 스프레드시트 목록에는 다양한 운영 체제에서 랜덤 데이터에 대한 런타임 개선 효과가 약 2-7배 나타났다.[1]

공간 성능에서 스프레드시트는 대부분의 인플레이스 알고리즘보다 더 나쁘다. 가장 단순한 형태에서는 O(n) 여유 공간을 사용하는 인플레이스 알고리즘이 아니며, 실험에서는 c 4-8을 사용하는 퀵소트보다 약 20% 더 많다.캐시 인식 양식 포함(부스트에 포함)Sort), 더 적은 메모리가 사용되며 최대 빈 카운트의 메모리 사용량에 최대 재귀 횟수에 대한 상한 값이 있으며, 이 상한은 키 크기(바이트)의 몇 킬로바이트가 된다.퀵소트의 O(log n) 오버헤드나 heapsort의 O(1) 오버헤드보다 점증적으로 더 많은 공간을 사용하지만, 리스트가 점유한 공간과 동일한 보조 공간을 사용하는 기본 형태의 병합보다 상당히 적은 공간을 사용한다.

실행

서명이 없는  러프로그2(데이터타입 입력하다)  {  서명이 없는 마를 뜨다 cRESult = 0;  // 일부 컴파일러에서는 무한순환을 피하기 위해 &&amp;이 필요하다.  // 성능을 현저하게 손상  만일 (입력하다 >= 0)   하는 동안에 ((입력하다 >> cRESult) && (cRESult < DATA_SIZE)) cRESult++;  다른   하는 동안에 (((입력하다 >> cRESult) < -1) && (cRESult < DATA_SIZE)) cRESult++;  돌아오다 cRESult; } 시즈테페 겟맥스카운트(서명이 없는 로그 범위, 서명이 없는 u카운트) {  서명이 없는 logSize = 러프로그2사이즈(u카운트);  서명이 없는 상대 폭 = (LOG_CONSTALL * 로그 범위)/((logSize > MAX_SPLITS) ? MAX_SPLITS : logSize);  // 원소 크기보다 약간 더 치우려고 하지 마십시오.  만일 (DATA_SIZE <= 상대 폭)   상대 폭 = DATA_SIZE - 1;  돌아오다 1 << ((상대 폭 < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ?    (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) :  상대 폭); }  공허하게 하다  FindExtremes(데이터타입 *배열, 시즈테페 u카운트, 데이터타입 & 파이맥스, 데이터타입 & 피민) {  시즈테페 u;  피민 = 파이맥스 = 배열[0];  을 위해 (u = 1; u < u카운트; ++u) {   만일 (배열[u] > 파이맥스)    파이맥스 = 배열[u];   다른 만일 (배열[u] < 피민)    피민 = 배열[u];  } }   //--------------------------------------------------------------  빈 * 스프레드소트코어(데이터타입 *배열, 시즈테페 u카운트, 시즈테페 & 우빈카운트, 데이터타입 &아이맥스, 데이터타입 &아이민) {  // 이 단계는 런타임의 약 10%이지만 최악의 경우를 방지하는 데 도움이 된다.  // 동작 및 실제 데이터로 동작 개선.만약 당신이 그것을 안다면  // 최대 및 최소 시간 전에 다음 값을 전달하십시오.  // 그리고 첫 번째 반복을 위해 이 단계를 건너뛰십시오.  FindExtremes((데이터타입 *) 배열, u카운트, 아이맥스, 아이민);  만일 (아이맥스 == 아이민)   돌아오다 NULL;  데이터타입 divMin,divMax;  시즈테페 u;  인트로 LogDivisor;  빈 * 빈어레이;  빈* 커런트빈;  서명이 없는 로그 범위;  로그 범위 = 러프로그2사이즈((시즈테페)아이맥스-아이민);  만일 ((LogDivisor = 로그 범위 - 러프로그2사이즈(u카운트) + LOG_MEAN_BIN_SIZE) < 0)   LogDivisor = 0;  // 메모리가 높은 시스템에만 필요한 경우 아래 항목  // 프로세서 속도 관련 지연 시간(대부분 최신 프로세서)  만일 ((로그 범위 - LogDivisor) > MAX_SPLITS)   LogDivisor = 로그 범위 - MAX_SPLITS;  divMin = 아이민 >> LogDivisor;  divMax = 아이맥스 >> LogDivisor;  우빈카운트 = divMax - divMin + 1;    // 빈을 할당하고 크기를 결정  빈어레이 = 칼록(우빈카운트, 의 크기(빈));  // 메모리 할당 오류 검사 및 정렬된 결과를 사용하여 반환 정리  만일 (!빈어레이) {   활자화하다("메모리 할당 오류로 인해 std::sort 사용\n");   찌꺼기::분류하다(배열, 배열 + u카운트);   돌아오다 NULL;  }     // 각 빈의 크기 계산: 런타임의 약 10%가 소요됨  을 위해 (u = 0; u < u카운트; ++u)   빈어레이[(배열[u] >> LogDivisor) - divMin].u카운트++;  // bin 위치 할당  빈어레이[0].전류 위치 = (데이터타입 *)배열;  을 위해 (u = 0; u < 우빈카운트 - 1; u++) {   빈어레이[u + 1].전류 위치 = 빈어레이[u].전류 위치 + 빈어레이[u].u카운트;   빈어레이[u].u카운트 = 빈어레이[u].전류 위치 - 배열;  }  빈어레이[u].u카운트 = 빈어레이[u].전류 위치 - 배열;    // 제자리에 바꿔 끼웁니다.이는 특히 스왑에서 런타임을 지배한다.  // std::신호 통화는 다른 주요 시간 사용자다.  을 위해 (u = 0; u < u카운트; ++u) {   을 위해 (커런트빈 = 빈어레이 + ((배열[u] >> LogDivisor) - divMin);  (커런트빈->u카운트 > u);     커런트빈 = 빈어레이 + ((배열[u] >> LogDivisor) - divMin))     바꾸다(배열 + u, 커런트빈->전류 위치++);   // 이제 이 위치에 속하는 물건을 찾았으니   // 버킷 수를 늘림   만일 (커런트빈->전류 위치 == 배열 + u)    ++(커런트빈->전류 위치);  }    // 버킷을 모으면 어레이가 정렬되고 재귀는 건너뛰어야 함  만일 (!LogDivisor) {   무료의(빈어레이);   돌아오다 NULL;  }  돌아오다 빈어레이; }  공허하게 하다 스프레드소트빈스(데이터타입 *배열, 시즈테페 u카운트, 시즈테페 우빈카운트, 경시하다 데이터타입 &아이맥스     , 경시하다 데이터타입 &아이민, 빈 * 빈어레이, 시즈테페 uMaxCount) {  시즈테페 u;  을 위해 (u = 0; u < 우빈카운트; u++) {   시즈테페 수를 세다 = (빈어레이[u].전류 위치 - 배열) - 빈어레이[u].u카운트;   // 비교할 항목이 두 개 이상 없으면 정렬하지 않음   만일 (수를 세다 < 2)    계속하다;   만일 (수를 세다 < uMaxCount)    찌꺼기::분류하다(배열 + 빈어레이[u].u카운트, 빈어레이[u].전류 위치);   다른    스프레드소트레크(배열 + 빈어레이[u].u카운트, 수를 세다);  }  무료의(빈어레이); }  공허하게 하다  스프레드소트레크(데이터타입 *배열, 시즈테페 u카운트) {  만일 (u카운트 < 2)   돌아오다;    데이터타입 아이맥스, 아이민;  시즈테페 우빈카운트;  빈 * 빈어레이 = 스프레드소트코어(배열, u카운트, 우빈카운트, 아이맥스, 아이민);  만일 (!빈어레이)   돌아오다;  스프레드소트빈스(배열, u카운트, 우빈카운트, 아이맥스, 아이민, 빈어레이,                 겟맥스카운트(러프로그2사이즈((시즈테페)아이맥스-아이민), u카운트)); }

두 가지 수준이 어느 수준보다 우수함

이 일반적인 유형의 알고리즘에 대한 흥미로운 결과는 경계 및 통합 가능한 확률 밀도 함수에 대한 O(n)라는 것이다.[4]이 결과는 스프레드시트가 첫 번째 반복 후 빈 크기가 일정한 값을 초과하는 경우 항상 한 번 더 반복하도록 강제함으로써 얻을 수 있다.키 밀도 함수가 Riemann 통합 및 경계로 알려져 있는 경우, 이 스프레드시트의 수정은 기본 알고리즘에 비해 어느 정도 성능 향상을 얻을 수 있으며, 최악의 경우 성능이 향상될 것이다.일반적으로 이러한 제한에 의존할 수 없는 경우, 이 변경은 알고리즘에 약간의 런타임 오버헤드를 추가하며 거의 이득을 얻지 못한다.다른 유사한 알고리즘으로는 Flashsort(간단한)와 Adaptive Left Radix가 있다.[5]스프레드시트가 최악의 상황을 확인하고 필요한 경우 성능 문제를 피하기 위해 std::sort를 사용하는 등 Adaptive Left Radix가 완료되거나 삽입 정렬을 사용할 수 있을 정도로 데이터가 작을 때까지 연속적으로 재귀하는 등, Adaptive Left Radix의 주요 차이는 상당히 유사하다.

참조

  1. ^ 스티븐 J. 로스고성능 일반 사례 정렬 알고리즘.병렬 및 분산 처리 기법 및 응용 프로그램, 제3권, 페이지 1100–1106. 라스베이거스 네바다 주2002.
  2. ^ "Boost.Sort github repository". boostorg/sort.
  3. ^ "HTML Spreadsort Documentation". Retrieved 30 August 2017.
  4. ^ Tamminen, Markku (March 1985). "Two Levels are as Good as Any". J. Algorithms. 6 (1): 138–144. doi:10.1016/0196-6774(85)90024-0.
  5. ^ Maus, Arne (2002). ARL, a faster in-place, cache friendly sorting algorithm (PDF) (Technical report). CiteSeerX 10.1.1.399.8357.