부동 소수점 값 27개 집합에서 중위수를 선택하는 가장 빠른 코드 C/C++
이것은 잘 아는 선택 알고리즘입니다.http://en.wikipedia.org/wiki/Selection_algorithm 를 참조하십시오.
3x3x3 복셀 값 집합의 중앙값을 구하려면 필요합니다.볼륨이 10억 복셀로 구성되어 있고 알고리즘이 재귀적이기 때문에 조금 빠른 것이 좋습니다.일반적으로 값이 비교적 가깝다고 예상할 수 있습니다.
제가 지금까지 시도해 본 알고리즘 중 가장 빨리 알려진 것은 빠른 정렬 파티션 기능을 사용합니다.더 빠른 것이 있는지 알고 싶습니다.
저는 두 개의 더미를 사용하여 20% 더 빠른 것을 "발명"했지만 해시를 사용하여 훨씬 더 빠른 것을 기대했습니다.이를 구현하기 전에 전격적으로 신속한 솔루션이 이미 존재하는지 알고 싶습니다.
부호 비트를 뒤집으면 부호 없는 정수로 간주될 수 있기 때문에 제가 플로트를 사용하고 있다는 사실은 문제가 되지 않습니다.주문은 그대로 유지됩니다.
편집: 데이비 랜드만이 제안한 대로 벤치마크와 소스 코드가 별도의 답변으로 이동되었습니다.chmike에 의한 답변은 아래를 참조하세요.
편집: 지금까지 가장 효율적인 알고리즘은 Boojum이 Fast Median and Butilian Filtering paper에 대한 링크로 아래에 언급한 것으로, 이제 이 질문에 대한 답이 되었습니다.이 방법의 첫 번째 현명한 아이디어는 래딕스 정렬을 사용하는 것이고, 두 번째는 픽셀을 많이 공유하는 인접 픽셀의 중앙값 검색을 결합하는 것입니다.
선택 알고리즘은 선형 시간(O(n))입니다.모든 데이터를 읽는 데 선형 시간이 걸리기 때문에 복잡성 측면에서는 선형 시간보다 더 나은 작업을 수행할 수 없습니다.따라서 복잡성 측면에서 더 빠른 것을 만들 수는 없었습니다.특정 입력에서 더 빠른 상수 인자를 가지고 계신 것은 아닐까요?그것이 큰 변화를 가져올지는 의문입니다.
C++에는 이미 선형 시간 선택 알고리즘이 포함되어 있습니다.왜 그냥 사용하지 않습니까?
std::vector<YourType>::iterator first = yourContainer.begin();
std::vector<YourType>::iterator last = yourContainer.end();
std::vector<YourType>::iterator middle = first + (last - first) / 2;
std::nth_element(first, middle, last); // can specify comparator as optional 4th arg
YourType median = *middle;
편집: 기술적으로는 홀수 길이의 컨테이너에 대한 중앙값일 뿐입니다.짝수 길이 중 하나에 대해서는 "윗쪽" 중위수가 됩니다. 정의를 면의 각각에 한 두 번해야 할 . 간"다를두합니다.first + (last - first) / 2그리고.first + (last - first) / 2 - 1평균을 내거나 뭐 그런거죠
편집: 사과를 드려야겠습니다.아래 코드는 잘못된 것입니다. 저는 고정 코드를 가지고 있지만, 측정을 다시 할 icc 컴파일러를 찾아야 합니다.
지금까지 고려된 알고리즘의 벤치마크 결과
알고리즘에 대한 프로토콜과 간단한 설명은 아래를 참조하십시오.첫 번째 값은 200개 이상의 다른 시퀀스에 대한 평균 시간(초)이고 두 번째 값은 stdDev입니다.
HeapSort : 2.287 0.2097
QuickSort : 2.297 0.2713
QuickMedian1 : 0.967 0.3487
HeapMedian1 : 0.858 0.0908
NthElement : 0.616 0.1866
QuickMedian2 : 1.178 0.4067
HeapMedian2 : 0.597 0.1050
HeapMedian3 : 0.015 0.0049 <-- best
프로토콜: rand()에서 얻은 랜덤 비트를 사용하여 27개의 랜덤 플로트를 생성합니다.각 알고리즘을 연속으로 500만 번 적용(이전 어레이 복사 포함)하고 평균 및 stdDev를 200개 이상의 랜덤 시퀀스로 계산합니다.icc-S-O3로 컴파일된 C++ 코드는 8GB DDR3와 함께 Intel E8400에서 실행됩니다.
알고리즘:
힙 정렬 : 힙 정렬과 픽 중간 값을 사용하는 전체 정렬 시퀀스입니다.구독자 액세스를 사용한 순진한 구현.
QuickSort: QuickSort와 Pick 중간 값을 사용하는 전체 시퀀스 형식입니다.구독자 액세스를 사용한 순진한 구현.
QuickMedian1: 스왑이 있는 알고리즘을 빠르게 선택합니다.구독자 액세스를 사용한 순진한 구현.
HipMedian1: 이전 스와핑과 균형 잡힌 힙 메소드를 배치합니다.구독자 액세스를 사용한 순진한 구현.
NthElement : nth_element STL 알고리즘을 사용합니다.데이터는 memcpy(vct.data(), rndVal, ... )를 사용하여 벡터에 복사됩니다.
QuickMedian2: 포인터가 있는 빠른 선택 알고리즘을 사용하고 두 개의 버퍼에 복사하여 스왑을 방지합니다.M salters의 제안을 기반으로 합니다.
힙메디안2 : 공유 헤드가 있는 듀얼 힙을 사용하는 내가 발명한 알고리즘의 변형.왼쪽 힙은 헤드 값이 가장 크고 오른쪽은 헤드 값이 가장 작습니다.첫 번째 값을 공통 머리와 첫 번째 중위수 값 추측으로 초기화합니다.힙 중 하나가 가득 찰 때까지 헤드보다 작은 경우 왼쪽 힙에 후속 값을 추가하고, 그렇지 않으면 오른쪽 힙에 추가합니다.14개의 값을 포함할 때 꽉 찼습니다.그러면 전체 힙만 고려합니다.적합한 힙인 경우 헤드보다 큰 모든 값에 대해 팝 헤드 및 삽입 값을 입력합니다.다른 값은 모두 무시합니다.왼쪽 힙일 경우, 헤드보다 작은 모든 값에 대해 헤드를 팝하고 힙에 삽입합니다.다른 값은 모두 무시합니다.모든 값이 진행된 경우 공통 헤드는 중앙값입니다.배열에 정수 인덱스를 사용합니다.포인터(64비트)를 사용한 버전은 거의 2배(~1초) 느린 것으로 나타났습니다.
HipMedian3 : HipMedian2와 알고리즘은 같지만 최적화되어 있습니다.서명되지 않은 문자 인덱스를 사용하고 값 스와핑 및 기타 여러 가지 사소한 것을 방지합니다.평균 및 stdDev 값은 1000개 이상의 랜덤 시퀀스에서 계산됩니다.n번째_element I은 동일한 1000개의 랜덤 시퀀스로 0.508s 및 stdDev 0.159537을 측정했습니다.따라서 HipMedian3은 nth_element stl 함수보다 33배 빠릅니다.반환된 각 중위수 값은 hapSort에서 반환된 중위수 값과 비교되며 모두 일치합니다.해시를 사용하는 방법이 훨씬 더 빠를지는 의문입니다.
EDIT 1: 이 알고리즘은 더욱 최적화 될 수 있습니다.비교 결과에 따라 요소가 왼쪽 또는 오른쪽 힙에 배치되는 첫 번째 단계는 힙이 필요하지 않습니다.두 개의 순서 없는 시퀀스에 요소를 단순히 추가하는 것으로 충분합니다.하나의 시퀀스가 가득 차면 위상 1이 중지됩니다. 즉, 중위수 값을 포함하여 14개의 요소가 포함됩니다.두 번째 단계는 전체 시퀀스를 히프화하는 것으로 시작하여 HipMedian3 알고리즘에 설명된 대로 진행합니다.새로운 코드와 벤치마크를 최대한 빨리 제공하겠습니다.
EDIT 2: 최적화된 알고리즘을 구현하고 벤치마킹하였습니다.하지만 힙Median3와 비교했을 때 큰 성능 차이는 없습니다.그것은 평균적으로 조금 더 느립니다.표시된 결과가 확인됩니다.훨씬 큰 세트가 있을 수도 있습니다.또한 첫 번째 값을 초기 중위수 추측으로 선택합니다.제시된 바와 같이, "중복" 값 집합에서 중앙값을 검색할 수 있다는 점에서 이점을 얻을 수 있습니다.중앙값 알고리즘의 중앙값을 사용하면 훨씬 더 나은 초기 중앙값 추측을 선택하는 데 도움이 될 것입니다.
HipMedian3의 소스코드
// return the median value in a vector of 27 floats pointed to by a
float heapMedian3( float *a )
{
float left[14], right[14], median, *p;
unsigned char nLeft, nRight;
// pick first value as median candidate
p = a;
median = *p++;
nLeft = nRight = 1;
for(;;)
{
// get next value
float val = *p++;
// if value is smaller than median, append to left heap
if( val < median )
{
// move biggest value to the heap top
unsigned char child = nLeft++, parent = (child - 1) / 2;
while( parent && val > left[parent] )
{
left[child] = left[parent];
child = parent;
parent = (parent - 1) / 2;
}
left[child] = val;
// if left heap is full
if( nLeft == 14 )
{
// for each remaining value
for( unsigned char nVal = 27 - (p - a); nVal; --nVal )
{
// get next value
val = *p++;
// if value is to be inserted in the left heap
if( val < median )
{
child = left[2] > left[1] ? 2 : 1;
if( val >= left[child] )
median = val;
else
{
median = left[child];
parent = child;
child = parent*2 + 1;
while( child < 14 )
{
if( child < 13 && left[child+1] > left[child] )
++child;
if( val >= left[child] )
break;
left[parent] = left[child];
parent = child;
child = parent*2 + 1;
}
left[parent] = val;
}
}
}
return median;
}
}
// else append to right heap
else
{
// move smallest value to the heap top
unsigned char child = nRight++, parent = (child - 1) / 2;
while( parent && val < right[parent] )
{
right[child] = right[parent];
child = parent;
parent = (parent - 1) / 2;
}
right[child] = val;
// if right heap is full
if( nRight == 14 )
{
// for each remaining value
for( unsigned char nVal = 27 - (p - a); nVal; --nVal )
{
// get next value
val = *p++;
// if value is to be inserted in the right heap
if( val > median )
{
child = right[2] < right[1] ? 2 : 1;
if( val <= right[child] )
median = val;
else
{
median = right[child];
parent = child;
child = parent*2 + 1;
while( child < 14 )
{
if( child < 13 && right[child+1] < right[child] )
++child;
if( val <= right[child] )
break;
right[parent] = right[child];
parent = child;
child = parent*2 + 1;
}
right[parent] = val;
}
}
}
return median;
}
}
}
}
볼륨 데이터의 대규모 배열에 대해 중앙값 필터를 수행하는 것처럼 들리기 때문에 SIGGRAPH 2006의 Fast Median and Butual Filtering paper를 살펴볼 수 있습니다.이 논문에서는 2D 이미지 처리를 다루지만 3D 볼륨에 대한 알고리즘을 적용할 수도 있습니다.다른 것이 없다면, 그것은 여러분에게 뒤로 물러서서 문제를 조금 다른 관점에서 바라볼 수 있는 방법에 대한 몇 가지 아이디어를 줄 수도 있을 것입니다.
당신이 확실히 알고 있듯이, 한 알고리즘의 성능이 온 컴파일러/프로세서/데이터 구조 조합만큼 다른 알고리즘에 상대적으로 좌우된다는 단순한 이유로 질문에 쉽게 대답할 수 없습니다.
따라서 두 가지를 시도해 보는 접근법은 충분히 좋은 것 같습니다.그리고 네, 빠른 분류는 꽤 빠를 겁니다.그렇지 않은 경우 작은 데이터 세트에서 더 나은 성능을 발휘하는 삽입 정렬을 시도해 볼 수도 있습니다.이 말은, 작업을 충분히 빠르게 수행할 수 있는 정렬 알고리즘으로 결정하라는 것입니다.일반적으로 "올바른" 알고리즘을 선택하는 것만으로 10배 이상 빨라지지는 않을 것입니다.
상당한 속도 향상을 위해서는 더 많은 구조를 사용하는 것이 더 좋은 방법입니다.과거에 대규모 문제를 해결할 수 있었던 몇 가지 아이디어:
당신은 복셀을 만들면서 효율적으로 사전 계산을 하고 27개의 Float 대신 28개를 저장할 수 있습니까?
근사적인 해결책이면 충분합니까?그렇다면 "일반적으로 값이 상대적으로 가까울 것으로 예상할 수 있다"는 점에서 9개의 값의 중위수만 보아도 알 수 있습니다.또는 값이 상대적으로 가까운 한 평균으로 대체할 수도 있습니다.
수십억 복셀의 중앙값이 정말 필요합니까?중위수가 필요한지 여부를 쉽게 검정한 다음 관련 부분 집합에 대해서만 계산할 수 있습니다.
다른 도움이 되지 않는다면: 컴파일러가 생성하는 asm 코드를 보세요.(예: 레지스터를 사용하여 모든 calc를 수행함으로써) 상당히 빠른 asm 코드를 작성할 수 있습니다.
편집 : 가치가 있어서 아래 댓글에 언급된 (부분적) 삽입구코드를 첨부하였습니다(전혀 검증되지 않음). 만약numbers[]입니다의 입니다.N, 그리고 당신은 가장 작은 것을 원합니다.P, 된 Flots,,partial_insertionsort<N, P, float>(numbers);하면..partial_insertionsort<27, 13, float>(numbers);,numbers[13]중위수를 포함합니다.추가 속도를 얻으려면 while 루프도 펼쳐야 합니다.위에서 살펴본 바와 같이, 정말 빠르게 진행하기 위해서는 데이터에 대한 지식을 활용해야 합니다(예: 데이터가 이미 부분적으로 정렬되어 있습니까?).데이터 분포의 속성을 알고 계십니까?내 생각엔, 당신이 이해할 수 있을 겁니다).
template <long i> class Tag{};
template<long i, long N, long P, typename T>
inline void partial_insertionsort_for(T a[], Tag<N>, Tag<i>)
{ long j = i <= P+1 ? i : P+1; // partial sort
T temp = a[i];
a[i] = a[j]; // compiler should optimize this away where possible
while(temp < a[j - 1] && j > 0)
{ a[j] = a[j - 1];
j--;}
a[j] = temp;
partial_insertionsort_for<i+1,N,P,T>(a,Tag<N>(),Tag<i+1>());}
template<long i, long N, long P, typename T>
inline void partial_insertionsort_for(T a[], Tag<N>, Tag<N>){}
template <long N, long P, typename T>
inline void partial_insertionsort(T a[])
{partial_insertionsort_for<0,N,P,T>(a, Tag<N>(), Tag<0>());}
첫 번째 시도에서 사용할 가능성이 가장 높은 알고리즘은 nth_element이며 직접 원하는 것을 제공합니다.14번째 원소만 달라고 하면 됩니다.
두 번째 시도에서는 고정된 데이터 크기를 활용하는 것이 목표입니다.알고리즘을 수행하는 동안 메모리를 전혀 할당하지 않으려는 경우가 있습니다.따라서 복셀 값을 미리 할당된 27개 요소 배열에 복사합니다.피벗을 선택하고 53 요소 배열의 가운데에 복사합니다.나머지 값을 피벗의 양쪽에 복사합니다.서 두 유지합니다(터()float* left = base+25, *right=base+27, 이 더 둘다를 가지고 세 좌변이 더 크거나 우변이 더 크거나 둘 다 12개의 요소를 가진다는 세 가지 가능성이 있습니다.마지막 경우는 사소한 경우입니다. 피벗은 중위수입니다.그렇지 않으면 왼쪽 또는 오른쪽에 있는 nth_element를 호출합니다.Nth의 정확한 값은 피벗보다 큰 값 또는 작은 값의 수에 따라 달라집니다.예를 들어 나눗셈이 12/14이면 피벗보다 작은 원소가 가장 필요하므로 Nth=0이고, 나눗셈이 14/12이면 피벗보다 작은 원소가 가장 필요하므로 Nth=13입니다.최악의 경우는 피벗이 극단적이었던 26/0과 0/26이지만, 이는 모든 경우의 2/27에서만 발생합니다.
세 번째 개선(또는 첫 번째 개선)은 C를 사용해야 하고 nth_element가 없는 경우) nth_element를 완전히 대체합니다.을 53만으로 ,다을장).float[27] 이 첫 이 첫 번째 반복에서의 피벗은 단지 복셀[0][0][0]입니다.에는 두 할당된e를 float[53](둘 다 같은 크기인 경우 easier) 및 복사는 둘 사이에서 이동합니다.여기서 기본적인 반복 단계는 그대로입니다: 피벗을 가운데로 복사하고 나머지를 왼쪽과 오른쪽으로 정렬합니다.각 단계가 끝날 때마다 중앙값이 현재 피벗보다 작은지 또는 큰지 알 수 있으므로 해당 피벗보다 크거나 작은 플로트를 폐기할 수 있습니다.반복할 때마다 1개에서 12개 사이의 요소가 제거되고 나머지의 평균 25%가 제거됩니다.
더 많은 속도가 필요한 경우 마지막 반복은 대부분의 복셀이 상당히 겹친다는 관측에 근거합니다.중위수 값을 3x3x1 절편마다 미리 계산합니다.그런 다음 3x3x3 복셀 큐브에 대한 초기 피벗이 필요할 때는 3개의 중앙값을 사용합니다.중위수의 중위수(4+4+1)보다 9개의 작은 복셀과 9개의 큰 복셀이 있다는 선험적 사실을 알고 있습니다.따라서 첫 번째 피벗 단계 이후 최악의 경우는 9/17과 17/9 분할입니다.따라서 플로트[26]에서 12번째 또는 14번째 대신 플로트[17]에서 4번째 또는 13번째 요소만 찾으면 됩니다.
배경:먼저 피벗을 복사하고 나머지 Float[N]을 왼쪽 및 오른쪽 포인터를 사용하여 Float[2N-1]에 복사하는 아이디어는 피벗 주위에 Float[N] 하위 배열을 채우고 피벗보다 작은 모든 요소를 왼쪽(아래쪽 인덱스)으로 채우고 오른쪽(위쪽 인덱스)으로 높은 것입니다.자, M번째 요소를 원한다면 운이 좋고 피벗보다 작은 M-1 요소를 가질 수 있습니다. 이 경우 피벗이 필요한 요소입니다.피벗보다 작은 요소가 (M-1)개 이상인 경우 M번째 요소가 포함되므로 피벗과 피벗보다 큰 요소를 폐기하고 모든 하위 값에서 M번째 요소에 대해 seacrh를 사용할 수 있습니다.피벗보다 작은 요소가 (M-1)보다 적으면 피벗보다 높은 값을 찾는 것입니다.그러면 피벗과 그보다 작은 것은 버리게 됩니다.피벗보다 작은 요소의 수, 즉 피벗의 왼쪽에 있는 요소의 수를 L로 합니다.다음 반복에서는 피벗보다 큰 (N-L-1) 플로트의 (M-L-1)번째 요소를 원합니다.
이런 종류의 nth_element 알고리즘은 작업의 대부분이 캐시에 있는 두 개의 작은 배열 사이에서 플로팅을 복사하는 데 사용되기 때문에 상당히 효율적입니다. 그리고 상태는 대부분 3개의 포인터(소스 포인터, 왼쪽 대상 포인터, 오른쪽 대상 포인터)로 표시되기 때문입니다.
기본 코드 표시하기
float in[27], out[53];
float pivot = out[26] = in[0]; // pivot
float* left = out+25, right = out+27
for(int i = 1; i != 27; ++1)
if((in[i]<pivot)) *left-- = in[i] else *right++ = in[i];
// Post-condition: The range (left+1, right) is initialized.
// There are 25-(left-out) floats <pivot and (right-out)-27 floats >pivot
Bose-Nelson 알고리즘을 사용하여 생성된 정렬 네트워크는 173개의 비교를 사용하여 루프/재귀 없이 직접 중위수를 찾습니다.벡터-산술 명령을 사용하는 등의 비교를 병렬로 수행할 수 있는 기능이 있는 경우 비교를 28개의 병렬 연산으로 그룹화할 수 있습니다.
Float가 (qs)NaN이 아닌 정규화된 경우 정수 연산을 사용하여 일부 CPU에서 더 유리한 성능을 발휘할 수 있는 IEEE-754 Float를 비교할 수 있습니다.
이 정렬 네트워크를 C(gcc 4.2)로 직접 변환하면 내 Core i7에서 388 클럭 주기의 최악의 경우가 발생합니다.
나는 당신이 기존의 정렬 알고리즘을 가지고 세트를 완전히 정렬할 필요가 없도록 당신이 그것을 조정할 수 있는지를 알아내는 것이 최선의 방법이라고 생각합니다.중위수를 결정하기 위해서는 정렬된 값의 최대 절반이 필요하며, 절반이 낮거나 높은 값이면 충분합니다.
original: | 5 | 1 | 9 | 3 | 3 |
sorted: | 1 | 3 | 3 | 5 | 9 |
lower half sorted: | 1 | 3 | 3 | 9 | 5 |
higher half sorted: | 3 | 1 | 3 | 5 | 9 |
나머지 절반은 정렬되지 않은 값의 버킷으로, 정렬된 값이 가장 크거나 작거나 같은 속성을 공유할 뿐입니다.
하지만 저는 그것을 위한 준비된 알고리즘이 없습니다. 그것은 당신이 당신의 정렬에서 바로가기를 어떻게 할 수 있는지에 대한 아이디어일 뿐입니다.
Alex Stepanov의 신간 Elements of Programming은 런타임 오버헤드를 최소화하면서 최소 평균 비교 수를 사용하여 순서 통계를 찾는 것에 대해 다소 길게 이야기합니다.안타깝게도 5개 요소의 중위수를 계산하는 데만 상당한 양의 코드가 필요합니다. 그런데도 그는 평균적으로 비교의 일부를 덜 사용하는 대체 솔루션을 프로젝트로 제공하기 때문에 이 프레임워크를 27개 요소의 중위수를 찾는 데까지 확장할 생각은 없습니다.그리고 이 책은 2009년 6월 15일까지는 구입할 수 없을 것입니다.요점은 이것이 고정된 크기의 문제이기 때문에 최적임을 입증할 수 있는 직접 비교 방법이 있다는 것입니다.
또한 이 알고리즘은 분리된 상태에서 한 번 실행되는 것이 아니라 여러 번 실행되며 대부분의 실행 사이에 27개의 값 중 9개의 값만 변경됩니다.그것은 이론적으로 그 일의 일부가 이미 끝났다는 것을 의미합니다.하지만 이 사실을 이용한 영상 처리의 중간 필터링 알고리즘에 대해서는 들어본 적이 없습니다.
nth_element를 언급한 모든 사람들에게 +1이지만, 특정 데이터 세트를 가진 하나의 CPU에서 실행되는 컴파일러에 대해 가장 효율적인 코드를 생성하고자 하기 때문에 이러한 종류의 코드는 STL보다 더 나은 것입니다.예를 들어, 일부 CPU/컴파일러 조합 std::swap(int,int)은 XOR을 사용한 손으로 쓴 스왑보다 느릴 수 있습니다(답변하기 전에 이것이 20년 전에는 사실일 수 있지만 더 이상은 아닙니다).CPU 고유의 어셈블리 코드를 손으로 작성하면 성능이 향상되는 경우가 있습니다.GPU의 스트림 프로세서를 활용할 계획이라면 알고리즘을 그에 맞게 설계해야 할 수도 있습니다.
2개의 더미를 사용하고 중앙값을 삽입할 때 계속해서 추적해야 한다고 말씀하셨습니다.그게 제가 얼마 전에 프로젝트에서 했던 일입니다.배열을 변경하고 힙을 하나만 사용했습니다.더 빠른 알고리즘은 생각할 수 없지만 메모리 사용량, 특히 CPU 캐시 메모리에 대해 주의를 드립니다.메모리 액세스에 주의해야 합니다.CPU 캐시는 페이지별로 스왑 인/아웃되므로, CPU 캐시 누락을 최소화하기 위해 알고리즘이 가까운 메모리를 터치하도록 합니다.
중앙값이 필요한 백만 개의 다른 값을 말할 때.당신의 중앙값을 그 백만의 부분집합에 기초하는 것이 가능한가요, 예를 들어 10%라고 합시다.중위수가 2등분(또는 거의 동일한) 부분집합의 값을 나누는 n번째 원소에 가깝도록?따라서 중위수를 찾기 위해서는 O(n)-배(이 경우 O(1/10n) 미만이 필요하며 따라서 O(nnogn)의 빠른 정렬로 최적 정렬에 가까워집니까?
알고리즘을 보고 싶다면 도널드 E. 크누스의 책을 찾아보세요.
PS. 만약 당신이 더 나은 것을 발명했다고 생각한다면, 당신은 복잡성이 알려진 알고리즘의 복잡성과 비슷하거나 더 낫다는 것을 보여줄 수 있어야 합니다.버킷 및 래딕스를 기반으로 한 변형의 경우 O(n)인 반면 빠른 정렬은 O(n.log(n))뿐입니다.알고리즘을 표시할 수 있을 때까지 20% 더 빠른 방법은 O(n.log(n))입니다.
디스크에서 로드하는 동안(또는 생성되는 방식에 따라) 별도의 스레드에서 제로 비용으로 계산할 수 있다고 장담합니다.
제가 정말로 말하고 싶은 것은 '속도'는 Big O 표기법이 실제적인 요소가 되기에는 27개의 값으로는 충분하지 않기 때문에 비트 트위들링에서 나오지 않을 것이라는 것입니다.
Knuth의 연습 5.3.3.13을 보고 싶을 수도 있습니다.(3/2)n+O(n^(2/3) log n) 비교를 사용하여 n개 요소의 중위수를 찾는 Floyd로 인한 알고리즘을 설명하며, O(·)에 숨겨진 상수가 실제로는 그리 크지 않은 것 같습니다.
3x3x3=27개의 가능한 값이 있는 경우(만약 그렇다면 왜 부유물이 떠있는 것입니까?), 27개의 요소로 구성된 배열을 만들고 데이터를 통과하는 한 번에 각 가능성을 셀 수 있습니까?
1-D 데이터 세트의 중앙값 계산을 위한 나의 초고속 알고리즘은 3번의 패스로 작업을 수행하며 데이터 세트를 정렬할 필요가 없습니다(!!!).
매우 일반적인 설명은 다음과 같습니다.
- 통과 1: 1-D 데이터 세트를 스캔하고 데이터 세트의 일부 통계 정보를 수집합니다.
- 패스 2: 데이터 세트의 통계 정보를 사용하고 일부 데이터 마이닝을 적용하여 중간(헬퍼) 배열을 만듭니다.
- 통과 3: 중간(도우미) 배열을 스캔하여 중위수를 찾습니다.
이 알고리즘은 Single-Precision Floating Point 값(32GB의 물리적 메모리와 128GB의 가상 메모리가 있는 데스크톱 시스템에서)의 8GE(기가 요소)보다 큰 1-D 데이터 세트의 중앙값을 찾거나 하드 실시간 환경에서 작은 데이터 세트의 중앙값을 찾도록 설계되었습니다.
알고리즘은 다음과 같습니다.
- 힙 정렬 또는 병합 정렬 알고리즘을 기반으로 하는 기존 알고리즘보다 빠른 속도(~60~75배)
- 순수 C언어로 구현된
- 어떤 인텔 고유 함수도 사용하지 않습니다.
- 인라인 어셈블러 명령을 사용하지 않습니다.
- MS, Intel, MinGW, Borland, Turbo 및 Watcom과 같은 C/C++ 컴파일러 간에 절대적으로 휴대 가능합니다.
- 플랫폼 간에 완전히 휴대 가능한
잘부탁드립니다, 세르게이 코스트로프
언급URL : https://stackoverflow.com/questions/810657/fastest-code-c-c-to-select-the-median-in-a-set-of-27-floating-point-values
'sourcecode' 카테고리의 다른 글
| my.ini에서 character_set_database 및 collation_database를 outf8로 설정하는 방법은 무엇입니까? (0) | 2023.10.10 |
|---|---|
| python(openpyxl)을 사용하여 Excel에서 그리드 라인 제거 (0) | 2023.10.10 |
| Angularjs에서 $compile을 지시 외에 사용하려면 어떻게 해야 합니까? (0) | 2023.10.10 |
| 파이썬 패키지에 포함된 모든 모듈을 나열하시겠습니까? (0) | 2023.10.10 |
| 많은 수의 DOM 요소를 변환/이동하는 가장 성능적인 방법 (0) | 2023.10.10 |