Как выполнить бинарный поиск (почти) без ветвей по произвольно отсортированным данным?
Как мне выполнить (почти) ветвистый поиск без ветвей произвольно отсортированных массивов предпочтительно переносимым способом? (например, код, который помогает компиляторам генерировать инструкцию CMOV, отлично подходит для этого.)
Под «почти» я подразумеваю «содержащий как можно меньше ветвей».
Решение
Вот версия std::lower_bound который имел только 1 ветвь (а именно, begin != end test), когда я тестировал его с помощью Visual C ++ 2012 (64-разрядная версия):
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;
}
32-битный с поддержкой SSE2, вероятно, также сможет использовать команду условного перемещения, чтобы получить аналогичную скорость.
Теперь скорость должен быть конкурентоспособным с линейным поиском небольших массивов … но это может стоить проверить.
Интересно, что я обнаружил, что для vector<int> до размера (приблизительно) 45 на моем процессоре, линейный поиск все еще быстрее! Хотя не уверен, почему, или если мои измерения были точными …
Также выясняется, что это не быстрее, чем бинарный поиск на моем процессоре i5.
Другие решения
Других решений пока нет …