0이 아닌 최소 값을 결정하는 가장 빠른 방법

Question

예를 들어 4 개의 정수 배열을 사용하면 가장 작은 방식으로 최소 0이 아닌 것으로 판단 할 수 있습니다.

Answer 1

이 문제에 대한 병렬 솔루션이 있지만 그만한 가치는 없을 것입니다.

먼저 우리는 배열 통해 동작 xchg(m, n)을 정의

는

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n]) 

이 작업들은 모두 비 - 제로 값 또는 교환을 포함하는 경우 오름차순와 'N'개의 요소가 'm'을 정렬 'm'요소의 값이 0 인 경우

xchg(0,2) xchg(1,3) 
xchg(0,1) xchg(2,3) 
xchg(1,2) 

한 쌍의 xchg 동작이 엄격한 순서의 실행을 통해 40 %의 시간 비용을 줄이고, 동시에 실행될 수있는 다음과 같이

다음 우리는 다섯 개 이러한 동작 세트를 실행한다. 작업이 끝나면 배열의 0이 아닌 요소는 오름차순으로 정렬됩니다. 가장 작은 값의 요소는 [0]이됩니다. 이 값이 0이면 배열에 0이 아닌 값이 없습니다.

이 용액 정렬 네트워크 (http://en.wikipedia.org/wiki/Sorting_network)에 의해 제공되는 고유의 병렬성을 활용하지만, 4 개 요소의 순차적 스캔과 같은 세 개 이상의 비교 연산을 사용하고, 결정적으로 절반만큼의 저장을 필요로 평균적 쓴다

이 작업중인 특정 플랫폼에 크게 의존한다

int v = a[0] 
for (n = 1; n < 4; n++) { 
    if ((a[n] < v && a[n] != 0) || v == 0) v = a[n] 
} 

Answer 2

입력에 따라 다릅니다. 배열이 정렬되지 않으면 전체 배열을 반복해야합니다. 배열이 정렬되어 있다면, 0이 아닌 무언가를 찾을 때까지 반복 할 필요가 있습니다. 훨씬 짧습니다.

Answer 3

요소가 배열에 추가 될 때 최소값을 유지하거나 배열을 정렬 된 순서로 유지하지 않는 한 다른 해결책은 없지만 모든 구성원을 반복하여 최소값을 결정하십시오.

각 구성원을 테스트하는 '빠른'방법은 없습니다.

일반적으로 느린 것으로 입증되지 않는 한 일반적으로 무언가를 최적화하지 않는 것이 좋습니다. 프로그램의 기존 규칙은 일반적으로 코드의 10 %에 해당하는 시간의 90 %를 사용합니다. 프로그래머가 99.99 %의 코드를 최적화하는 규칙은 10 %가 아닙니다.

코드를 프로파일 링 - 코드를 프로파일 링 - 코드 음

Answer 4

이 std::min({a,b,c,d})입니다 코딩하는 가장 빠른 방법을 프로필.

더 심각한 점 : 응용 프로그램에서 많은 가치를 취하는 것과 같은 작업에 병목 현상이있는 경우 더 나은 해결책은 해당 최소 찾기 작업을 여러 부분으로 나누어 GPU로 보내는 방법을 찾는 것입니다 (또는 많은 쓰레드), 동시에 많은 최소 계산 계산을 수행 할 수 있습니다.

병렬 처리는 아마도 어셈블리에서 최소한의 함수를 작성하는 것 이상의 도움이 될 것입니다.

Answer 5

우리는 잠재적으로 인해 적은 순차적 종속성, 현대 순차적 (out-of-order) 프로세서에 min(min(a,b),min(c,d)) 대신 min(min(min(a,b),c),d)을 계산하기 위해 빠를 수, 마이크로 최적화 생각하는 경우 : 이전에 프로세서가 min(a,b)을 계산할 수 사용 가능한 충분한 실행 단위가있는 경우 min(c,d)을 독립적으로 병렬로 실행하십시오. 이것은 프로세서에 조건부 이동 명령이 있다고 가정하므로 계산 min에는 분기가 필요하지 않습니다.