c - 更多位 : Efficiently implementing a binary search over a fixed-size array

Question

再一次，我遇到了一个问题，我想将其缩短到纳秒级。我有一个小的常量数组，我想搜索它以查看给定数字是否是成员*。

输入:一个 64 位数字n。

输出:如果 n 在数组中则为真，如果 n 不在数组中则为假。

如果可以针对特定元素及其分布进行优化，有什么好的技术可以快速进行二进制搜索。

细节

我有一个包含大约 136 个成员的数组(尽管见下文:有一些灵 active )来搜索。成员在整个范围内分布不均:它们聚集在范围的开头和结尾。输入数字可以假设为以均匀概率选择。利用这种不规则性可能是值得的。

这是 136 元素数组的分布示例图片。请注意，136 个元素中只有 12 个在范围的 1% 到 99% 之间；余额低于 1% 或超过 99%。

_{(来源:crg4.com)}

我假设分支预测错误将是任何实现的最大成本。我很高兴被证明是错误的。

注意事项

* 实际上，我有两个数组。事实上，我可以选择使用什么数组:效率表明第一个应该有 10-40 个成员，而第二个可以有不超过(恰好)136 个成员。我的问题在选择大小方面提供了真正的灵 active ，同时限制了精确决定使用哪些成员的自由度。如果某种方法在某些尺寸或限制下表现更好，请提及这一点，因为我可能会使用它。在所有条件都相同的情况下，我希望第二个数组尽可能大。由于与二分查找无关的原因，我可能需要将第二个数组的大小减小到 <= 135 或 <= 66(这与确定输入数的难度有关，这取决于阵列选择)。

这是可能的数组之一，如果它有助于测试想法的话。 (这很好地揭示了我的目的...!)不过，不要根据前几名成员得出毫无根据的结论。

0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 9320093220751060618, 9999984858389672876, 10259680355300795461, 10358875208395550958, 10396764270768694864, 10411236604793371085, 10416764544494255842, 10418876029572233892, 10419682545105283285, 10419990606626453414, 10420108275656914408, 10420153221227127261, 10420170388907304826, 10420176946377624668, 10420179451108406629, 10420180407830432670, 10420180773265728832, 10420180912849591277, 10420180966165882450, 10420180986530893524, 10420180994309635573, 10420180997280850646, 10420180998415753816, 10420180998849248253, 10420180999014828394, 10420180999078074380, 10420180999102232197, 10420180999111459662, 10420180999114984240, 10420180999116330509, 10420180999116844738, 10420180999117041156, 10420180999117116181, 10420180999117144838, 10420180999117155784, 10420180999117159965, 10420180999117161562, 10420180999117162172, 10420180999117162405, 10420180999117162494, 10420180999117162528, 10420180999117162541, 10420180999117162546, 10420180999117162548

我最初会在 Phenom II x4 上运行该程序，但欢迎针对其他架构进行优化。

Answer 1

如果您只对成员(member)/非成员(member)感兴趣，而不是位置，您可以通过以下安排消除一些条件分支:

bool b = false;
b |= (n == x[i]);
b |= (n == x[i+1]);
// ... etc. ...

显然，您可能不想对所有 136 个条目都执行此操作。但是可能有一个最佳点，您可以混合使用粗粒度的二分搜索来首先定位哪一批，例如。 4个元素n可以在，然后切换到上面的方法。