自作の二部探索がstd::binary_search()より遅い

Question

勉強のために二分探索のコードを書いたのですが、どちらもミリ秒未満とはいえstd::binary_search()と比べると倍近く遅いようです。
これは、STDのコードがカリカリにチューニングされていたり高度な?書き方をしていることに由来するのでしょうか?
それとも、私の下記のコードには何かボトルネックになる要素があるのでしょうか?

#include <algorithm>
#include <functional>
#include <vector>
typedef std::vector<int>::const_iterator Iterator;

template<class Compare>
Iterator BinarySearch(Iterator begin, Iterator end, Compare comp) {
  auto it = begin;
  auto not_found = end;

  while (std::distance(it, end) > 0) {
    auto mid = it;
    std::advance(mid, std::distance(it, end) / 2);
    auto comp_result = comp(*mid);

    if (comp_result == 0) {
      return mid;
    } else if (comp_result < 0) {
      it = mid;
      ++it;
    } else {
      end = mid;
    }
  }
  return not_found;
}

コード全文 [Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ

Answer 1

comp が負、ゼロ、正の 3つの値を返しますよね。
そのため、内部で比較が 2回必要な場合があります。

std::binary_search の comp は
comp(const T& a, const T& b) { return a < b; } だから、速いのではありませんか？

もうひとつ。

バイナリサーチでは、結果が求まるまで何回か比較を行います。
comp_result == 0 は最後まで true にならないので、
comp_result == 0 と comp_result < 0 の 2回の比較が常に行われます。

std::binary_search では comp が less なので、
if (key < *mid) end = mid;
else if (*mid < key) it = mid, ++it;
else return mid;
になっていて、比較が 1回で済む場合があるのではないでしょうか？

Answer 2

std::distance(it, end)を何度も呼ぶよりも最初にカウントしたら
あとはその結果から計算していった方が高速です。

Comments

[退会済みユーザー]

下記のように試してみると、たまにクラッシュするようになったのですがどこかおかしいでしょうか?
コメント欄でのやり取りに相応しくなければ、新たな質問を立てます。

template<class Compare>
Iterator BinarySearch(Iterator begin, Iterator end, Compare comp) {
auto it = begin;
auto not_found = end;
auto dist = std::distance(it, end);

while (dist > 0) {
dist /= 2;
auto mid = it;
std::advance(mid, dist);
auto comp_result = comp(*mid);

if (comp_result == 0) {
return mid;
} else if (comp_result < 0) {
it = ++mid;
} else {
end = mid;
}
}
return not_found;
}

[yudedako67]

mid == endになる場合があります。そのときcomp(*mid)を呼び出してるんでしょう。

[退会済みユーザー]

なるほど、その場合auto comp_result = comp(*mid);の前を修正すると思うのですが、どうすれば良いでしょうか?

[asm]

{0,1,2,3}に対して、3を検索した時などがおかしいようです。
> it = ++mid;

midが+1されているのに残り要素を減らしていないのが問題ですね。

[退会済みユーザー]

mid, distの加減を試しても上手くいかなかったので、その部分のバグについての質問を挙げました。
もしよろしければそちらも回答していただけると嬉しいです。

https://teratail.com/questions/256050

Answer 3

原因を割り出すために吐かれるコードを見てみましたが、比較回数はあまり関係なさそうに見えます。

ところで検証のためにgoogle/benchmarkを使うように書き換えてたんですがなんか実行結果がおかしい。何を見落としているんだろうか・・・
http://quick-bench.com/WgvpPrDFyfr6YYKxLrCFsAqBXPg

---

別におかしくなさそう。

http://quick-bench.com/S5EQOuyWmqTIBILOXAO03kxDp-8
https://godbolt.org/z/V5nGSE

Comments

[asm]

my::BinarySearchの返り値を使ってないのでO3で消されてる感じですね
benchmark::DoNotOptimizeに返り値渡してやるといいかと思います