정수가 기존의 값 집합을 가진 두 정수(포함) 사이에 있는지 여부를 확인하는 가장 빠른 방법

정수가 기존의 값 집합을 가진 두 정수(포함) 사이에 있는지 여부를 확인하는 가장 빠른 방법

요?x >= start && x <= end두 정수 사이에 정수가 있는지 테스트하기 위해 C 또는 C++를 사용합니다.

업데이트: 특정 플랫폼은 iOS입니다.이는 특정 사각형 내의 원으로 픽셀을 제한하는 박스 블러 기능의 일부입니다.

업데이트: 승인된 답변을 시도한 후 코드 한 줄에서 정상보다 속도가 크게 향상되었습니다.x >= start && x <= endwayway.disclosed.를 클릭합니다.

업데이트: 다음은 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]서, snowledge.D = upper - lower.number하한 이하: 음수, 상한 초과: 보다 큽니다.

가변 범위 확인의 경우:

if (x >= minx && x <= maxx) ...

비트 연산을 사용하는 것이 더 빠릅니다.

if ( ((x - minx) | (maxx - x)) >= 0) ...

이렇게 하면 두 가지를 하나로 줄일 수 있다.

safe 타입에 관심이 있는 경우:

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

더 많은 가변 범위 검사를 함께 결합할 수 있습니다.

if (( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

이렇게 하면 4개의 지점이 1개로 줄어듭니다.

gcc의 이전 버전보다 3.4배 빠릅니다.

이처럼 소규모로 코딩하기 위해 상당한 최적화를 수행할 수 있는 경우는 드뭅니다.더 높은 수준에서 코드를 관찰하고 수정함으로써 큰 성능 향상을 얻을 수 있습니다.범위 검정의 필요성을 완전히 제거하거나 O(n^2) 대신 O(n)만 수행할 수 있습니다.부등식의 한쪽이 항상 암시되도록 검정의 순서를 변경할 수 있습니다.알고리즘이 이상적이라고 해도 이 코드가 범위를 1000만 번 테스트하는 방법을 확인하고 SSE를 사용하여 여러 테스트를 병렬로 수행할 수 있는 방법을 찾으면 이득이 발생할 가능성이 높아집니다.

이 답변은 승인된 답변으로 수행된 테스트를 보고하는 것입니다.정렬된 랜덤 정수의 큰 벡터에 대해 클로즈드 레인지 테스트를 실시했는데 놀랍게도 (낮음 <= num & num <= high)의 기본방법이 실제로 위의 승인된 답변보다 더 빠릅니다!테스트는 HP Pavilion g6 (AMD A6-3400APU, 6GB RAM 탑재)에서 실시했습니다.테스트에 사용되는 핵심 코드는 다음과 같습니다.

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의 어떤 사이즈에서도 첫 번째 방법은 두 번째 방법보다 우선합니다.

이게 왜 중요한지 정확히 말해줄 수 있어MMU를 시뮬레이트하고 있다고 가정해 봅시다.메모리 주소가 페이지 세트와 함께 존재하는지 항상 확인해야 합니다.그 작은 부분들이 아주 빠르게 합쳐지는 이유는 당신이 항상 이렇게 말했기 때문이다.

• 이 주소가 유효한가요?
• 이 주소는 어느 페이지의 것입니까?
• 이 페이지는 어떤 권한을 가지고 있습니까?

동일한 데이터에 대해 검정을 수행하는 횟수에 따라 달라집니다.

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

매우 한정된 값 집합에 대해 이 작업을 수행하는 경우 룩업 테이블을 만들 수 있습니다.인덱싱 수행은 비용이 더 많이 들 수 있지만 전체 테이블을 캐시에 넣을 수 있으면 코드에서 모든 분기를 제거할 수 있으므로 작업 속도가 빨라집니다.

128^3 = 2,097,070 = 1,097,070 ==다 。세중를 제어할 수 에는 모든 고려합니다.start = N한 번에 작업 세트의 크기가128^2 = 16432대부분의 최신 캐시에 적합한 바이트입니다.

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

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

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

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