x >= start && x <= end
整数が 2 つの整数の間にあるかどうかをテストするのに、C や C++ よりも速い方法はありますか?
更新: 私の特定のプラットフォームは iOS です。これは、ピクセルを特定の正方形内の円に制限するボックスぼかし機能の一部です。
更新:試した後受け入れられた回答通常の方法で実行した場合と比べて、1 行のコードで桁違いの高速化を実現しました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
分岐を削減または排除することで、劇的な速度向上が実現できるというのは、実に驚くべきことです。
ベストアンサー1
比較/分岐を 1 つだけ使用してこれを行う古いトリックがあります。速度が本当に向上するかどうかは疑問の余地があり、向上したとしても、おそらく気付いたり気にしたりするほどではないでしょう。しかし、比較を 2 つだけから始める場合、大幅な改善が期待できる可能性はかなり低いです。コードは次のようになります。
// 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