최소 세 숫자

Question

나는 min() 함수를 사용하여 세 개의 숫자 중 가장 작은 숫자를 찾는 알고리즘을 연구하고 있습니다. 프로그램은 C/C++ 언어로 작성됩니다. 일시적으로 나는

분 (숫자 1, 분 (번호 2, 번호 3))

를 사용하지만 CPU 시간의 약 90 %를했다. 이 문제의 가장 빠른 해결책은 무엇입니까? 어쩌면 어떤 비트 트릭이나 뭐?

Answer 1

당신의 컴파일러가 최적화되어 있다면 아마 당신이 얻는 것만 큼 좋을 것입니다.

#include <algorithm> 

int test(int i, int j, int k) 
{ 
    return std::min(i, std::min(j, k)); 
} 

내가

cmpl %edi, %esi 
movl %edx, %eax 
cmovg %edi, %esi 
cmpl %edx, %esi 
cmovle %esi, %eax 
ret 

컴파일 할 때 아마 당신이 어떤 최적화 플래그를 통과하지 못한 얻을 g++ -S -c -O3 test.cpp 컴파일?

Answer 2

확인 this 솔루션은 참조 위의 코드를 아래에 인용 당신에게

을 할 수있는 경우는

int x; // we want to find the minimum of x and y 
int y; 
int r; // the result goes here 

r = y^((x^y) & -(x < y)); // min(x, y) 

같은 제목 아래 또 하나의 트릭은

r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y) 

당신은 제거 할 수 있습니다 -1 트릭 2에서입니다 일부 시스템에서만 작동하며 이식 가능하지 않습니다.

이 아이디어를 확장하여 최소 3 개의 숫자를 찾을 수 있습니다.

static inline int min3(int x, int y, int z) 
{ 
    register int r, d; 
    d = x - y; 
    r = y + (d & (d >> (sizeof(int) * CHAR_BIT))); /* add -1 if required */ 
    d = r - z; 
    r = z + (d & (d >> (sizeof(int) * CHAR_BIT))); /* add -1 if required */ 
    return r; 
} 

숫자의 범위가 너무 작 으면 일부 조회를 사용하거나 더 효율적이지만 해킹 할 수 있습니다.