알려진 값 세트를 사용하여 정수가 두 정수 (포함) 사이에 있는지 판별하는 가장 빠른 방법

알려진 값 세트를 사용하여 정수가 두 정수 (포함) 사이에 있는지 판별하는 가장 빠른 방법

---

x >= start && x <= end정수가 두 정수 사이에 있는지 테스트하는 C 또는 C ++ 보다 빠른 방법이 있습니까?

업데이트 : 내 특정 플랫폼은 iOS입니다. 이것은 주어진 사각형에서 픽셀을 원으로 제한하는 상자 흐림 기능의 일부입니다.

업데이트 : 허용 된 답변을 시도한 후 정상적인 x >= start && x <= end방법으로 한 줄의 코드에서 속도가 크게 향상되었습니다 .

업데이트 : 다음은 XCode의 어셈블러가 포함 된 전후 코드입니다.

새로운 방식

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

옛날 방식

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

분기를 줄이거 나 없애는 것이 어떻게 그렇게 빠른 속도를 제공 할 수 있는지 놀랍습니다.

---

하나의 비교 / 분기 로이 작업을 수행하는 오래된 트릭이 있습니다. 실제로 속도를 향상 시킬지 여부는 의문의 여지가 있지만, 그렇게해도주의하거나 신경 쓰지 않아도 될 것 같지만 두 번의 비교만으로 시작하면 크게 개선 될 가능성이 거의 없습니다. 코드는 다음과 같습니다.

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

전형적인 현대 컴퓨터 (즉, 2의 보수를 사용하는 것)를 사용하면 부호없는 것으로의 변환은 실제로는 전혀 문제가되지 않습니다. 동일한 비트를 보는 방식의 변화 일뿐입니다.

일반적인 경우 upper-lower(추정 된) 루프 외부에서 사전 계산할 수 있으므로 일반적으로 큰 시간이 걸리지 않습니다. 분기 명령 수를 줄이면서 분기 예측도 향상시킵니다. 이 경우 숫자가 범위의 하단 아래 또는 상단에 있는지 여부에 관계없이 동일한 분기가 수행됩니다.

이것이 어떻게 작동하는지에 대한 기본 아이디어는 매우 간단합니다. 부호없는 숫자로 볼 때 음수는 양수로 시작한 것보다 큽니다.

실제로이 방법 number은 간격을 원점으로 변환 하고 number간격 [0, D]이 어디에 있는지 확인합니다 D = upper - lower. 경우 number아래 하한은 네거티브 상부 위에 결합하는 경우, 그리고 : 보다 크다D .

---

이러한 소규모로 코딩하기 위해 상당한 최적화를 수행 할 수있는 경우는 거의 없습니다. 코드를 더 높은 수준에서 관찰하고 수정하면 성능이 크게 향상됩니다. 범위 테스트의 필요성을 완전히 제거하거나 O (n ^ 2) 대신 O (n) 만 수행 할 수 있습니다. 불평등의 한 측면이 항상 암시되도록 테스트 순서를 다시 지정할 수 있습니다. 알고리즘이 이상적 임에도 불구하고이 코드의 범위가 천만 번 테스트되는 방식을보고이를 일괄 처리하고 SSE를 사용하여 여러 테스트를 병렬로 수행하는 방법을 찾으면 이득이 더 많이 올 것입니다.

---

동일한 데이터에 대해 몇 번의 테스트를 수행 할 것인지에 따라 다릅니다.

테스트를 한 번 수행하는 경우 알고리즘 속도를 높이는 의미있는 방법이 없을 수 있습니다.

매우 유한 한 값 세트에 대해이 작업을 수행하는 경우 찾아보기 테이블을 작성할 수 있습니다. 인덱싱을 수행하는 데 비용이 더 많이들 수 있지만 전체 테이블을 캐시에 맞출 수 있으면 코드에서 모든 분기를 제거하여 속도를 높일 수 있습니다.

데이터의 조회 테이블은 128 ^ 3 = 2,097,152입니다. 세 가지 변수 중 하나를 제어 할 수 있으므로 start = N한 번에 모든 인스턴스를 고려 하면 작업 세트의 크기가 128^2 = 16432바이트로 줄어듦으로써 대부분의 최신 캐시에 잘 맞습니다.

분기없는 조회 테이블이 명백한 비교보다 충분히 빠른지 확인하려면 실제 코드를 벤치마킹해야합니다.

---

이 답변은 승인 된 답변으로 수행 된 테스트에 대해보고하는 것입니다. 나는 정렬 된 임의의 정수로 구성된 큰 벡터에 대해 폐쇄 범위 테스트를 수행했으며 놀랍게도 (낮은 <= num & & num <= high)의 기본 방법은 실제로 위의 허용 된 답변보다 빠릅니다! 테스트는 HP Pavilion g6 (6GB 램이있는 AMD A6-3400APU)에서 수행되었습니다. 테스트에 사용되는 핵심 코드는 다음과 같습니다.

int num = rand();  // num to compare in consecutive ranges.
chrono::time_point<chrono::system_clock> start, end;
auto start = chrono::system_clock::now();

int inBetween1{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (randVec[i - 1] <= num && num <= randVec[i])
        ++inBetween1;
}
auto end = chrono::system_clock::now();
chrono::duration<double> elapsed_s1 = end - start;

위의 허용되는 답변 인 다음과 비교하십시오.

int inBetween2{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
    if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1]))
        ++inBetween2;
}

randVec은 정렬 된 벡터입니다. MaxNum의 모든 크기에 대해 첫 번째 방법은 내 컴퓨터의 두 번째 방법을 능가합니다!

---

정수에 대해 비트 단위 연산을 수행 할 수 없습니까?

0에서 128 사이 여야하므로 8 번째 비트가 설정되면 (2 ^ 7) 128 이상입니다. 포괄적 인 비교를 원하기 때문에 에지 케이스는 고통이 될 것입니다.

참고 : https://stackoverflow.com/questions/17095324/fastest-way-to-determine-if-an-integer-is-between-two-integers-inclusive-with