我如何以一种最好的可移植方式对任意排序的数组执行(几乎)无分支的二进制搜索? (例如,帮助编译器生成 CMOV 指令的代码对此非常有用。)
“几乎”是指“包含尽可能少的分支”。
最佳答案
这是 std::lower_bound
的一个版本当我使用 Visual C++ 2012(64 位)对其进行测试时,它只有 1 个分支(即 begin != end
测试):
template<class FwdIt, class T, class P>
FwdIt branchless_lower_bound(FwdIt begin, FwdIt end, T const &val, P pred)
{
while (begin != end)
{
FwdIt middle(begin);
std::advance(middle, std::distance(begin, end) >> 1);
FwdIt middle_plus_one(middle);
++middle_plus_one;
bool const b = pred(*middle, val);
begin = b ? middle_plus_one : begin;
end = b ? end : middle;
}
return begin;
}
支持 SSE2 的 32 位可能也可以使用条件移动指令,以获得类似的速度。
现在速度应该与小型数组的线性搜索相比具有竞争力......但它可能值得检查。
有趣的是,我发现对于 vector<int>
在我的 CPU 上最大(大约)45,线性搜索仍然更快!不知道为什么,或者我的测量是否准确......
另外事实证明,这并不比我的 i5 CPU 上的分支二进制搜索快。
关于c++ - 如何对任意排序的数据执行(几乎)无分支的二进制搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14454592/