确定一个整数是否在两个具有已知值集的整数（含）之间的最快方法

Question

有没有比x更快的方法

更新：我的特定平台iOS。这是框模糊函数的一部分，该函数将像素限制在给定正方形中的一个圆上。

更新：在尝试了被接受的答案之后，我在一行代码上获得了一个数量级的加速比，超过了正常的x

更新：以下是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

非常令人惊讶的是，减少或消除分支可以提供如此惊人的速度。




Answer 1

这取决于要对相同的数据执行多少次测试。

如果您只执行一次测试，可能没有有意义的方法来加快算法。

如果对非常有限的一组值执行此操作，则可以创建一个查找表。执行索引可能更昂贵，但如果可以将整个表放入缓存中，则可以从代码中删除所有分支，这将加快速度。

对于您的数据，查找表为128^3=2097152。如果你能控制三个变量中的一个，那么你可以一次考虑所有的实例：<代码>开始= n< /代码>，然后工作集的大小下降到<代码> 128 ^ 2＝16432 < /代码>字节，这应该适合于大多数现代缓存。

您仍然需要对实际代码进行基准测试，以查看无分支查找表是否比明显的比较快。

Answer 2

很少能够对如此小规模的代码进行重大优化。大的性能提升来自于从更高的级别观察和修改代码。您可以完全不需要范围测试，或者只做O（n）而不是O（n^2）。您可以重新排序测试，以便总是隐含不等式的一面。即使算法是理想的，当你看到这段代码如何1000万次进行范围测试，并找到一种方法将它们批量化并使用SSE并行进行许多测试时，收益也更有可能到来。

Answer 3

只有一个比较/分支就可以实现这一点。它是否真的能提高速度可能是个问题，即使它真的能提高速度，也没什么值得注意或关心的，但是当你仅仅从两个比较开始的时候，取得巨大进步的机会非常渺茫。代码如下所示：

// 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);

对于典型的现代计算机（即任何使用二进制补码的计算机），向无符号的转换实际上是一个nop——只是查看相同比特的方式发生了变化。

请注意，在典型的情况下，您可以在（假定的）循环之外预计算上-下，这样通常不会贡献任何重要的时间。随着分支指令数量的减少，这也（通常）提高了分支预测。在这种情况下，无论数字是在范围的底端以下还是在顶部以上，都取相同的分支。

至于这是如何工作的，基本的想法很简单：负数，当被视为无符号数时，将大于任何开始为正数的数字。

在实践中，此方法将编号和间隔转换到原点，并检查编号是否在间隔[0，D]内，其中D=上-下。如果number低于下限：负值，如果高于上限：大于D。