22

分岐予測の素晴らしさにより、バイナリ検索は整数の配列を介した線形検索よりも遅くなる可能性があります。一般的なデスクトップ プロセッサでは、二分探索を使用する前に、その配列をどのくらい大きくする必要がありますか? 構造が多くのルックアップに使用されると仮定します。

4

3 に答える 3

15

C++ のベンチマークを少し試してみましたが、驚いたことに、線形検索は最大で数十個の項目に普及しているようで、それらのサイズで二分検索が優れているケースは見つかりませんでした。gcc の STL がうまく調整されていないのではないでしょうか? しかし、それでは -- いずれかの種類の検索を実装するために何を使用しますか?-) だから、ここに私のコードを示します。

#include <vector>
#include <algorithm>
#include <iostream>
#include <stdlib.h>

int data[] = {98, 50, 54, 43, 39, 91, 17, 85, 42, 84, 23, 7, 70, 72, 74, 65, 66, 47, 20, 27, 61, 62, 22, 75, 24, 6, 2, 68, 45, 77, 82, 29, 59, 97, 95, 94, 40, 80, 86, 9, 78, 69, 15, 51, 14, 36, 76, 18, 48, 73, 79, 25, 11, 38, 71, 1, 57, 3, 26, 37, 19, 67, 35, 87, 60, 34, 5, 88, 52, 96, 31, 30, 81, 4, 92, 21, 33, 44, 63, 83, 56, 0, 12, 8, 93, 49, 41, 58, 89, 10, 28, 55, 46, 13, 64, 53, 32, 16, 90
             };

int tosearch[] = {53, 5, 40, 71, 37, 14, 52, 28, 25, 11, 23, 13, 70, 81, 77, 10, 17, 26, 56, 15, 94, 42, 18, 39, 50, 78, 93, 19, 87, 43, 63, 67, 79, 4, 64, 6, 38, 45, 91, 86, 20, 30, 58, 68, 33, 12, 97, 95, 9, 89, 32, 72, 74, 1, 2, 34, 62, 57, 29, 21, 49, 69, 0, 31, 3, 27, 60, 59, 24, 41, 80, 7, 51, 8, 47, 54, 90, 36, 76, 22, 44, 84, 48, 73, 65, 96, 83, 66, 61, 16, 88, 92, 98, 85, 75, 82, 55, 35, 46
                 };

bool binsearch(int i, std::vector<int>::const_iterator begin,
                      std::vector<int>::const_iterator end) {
  return std::binary_search(begin, end, i);
}

bool linsearch(int i, std::vector<int>::const_iterator begin,
                      std::vector<int>::const_iterator end) {
  return std::find(begin, end, i) != end;
}

int main(int argc, char *argv[])
{
  int n = 6;
  if (argc < 2) {
    std::cerr << "need at least 1 arg (l or b!)" << std::endl;
    return 1;
  }
  char algo = argv[1][0];
  if (algo != 'b' && algo != 'l') {
    std::cerr << "algo must be l or b, not '" << algo << "'" << std::endl;
    return 1;
  }
  if (argc > 2) {
    n = atoi(argv[2]);
  }
  std::vector<int> vv;
  for (int i=0; i<n; ++i) {
    if(data[i]==-1) break;
    vv.push_back(data[i]);
  }
  if (algo=='b') {
    std::sort(vv.begin(), vv.end());
  }
  bool (*search)(int i, std::vector<int>::const_iterator begin,
                        std::vector<int>::const_iterator end);
  if (algo=='b') search = binsearch;
  else search = linsearch;
  int nf = 0;
  int ns = 0;
  for(int k=0; k<10000; ++k) {
    for (int j=0; tosearch[j] >= 0; ++j) {
      ++ns;
      if (search(tosearch[j], vv.begin(), vv.end()))
        ++nf;
    }
  }
  std::cout << nf <<'/'<< ns << std::endl;

  return 0;
}

コアデュオでの私のタイミングのいくつか：

AmAir:stko aleax$ time ./a.out b 93
1910000/2030000

real    0m0.230s
user    0m0.224s
sys 0m0.005s

AmAir:stko aleax$ time ./a.out l 93
1910000/2030000

real    0m0.169s
user    0m0.164s
sys 0m0.005s

とにかく、それらはかなり再現可能です...

OP : アレックス、私はあなたのプログラムを編集して、配列を 1..n で埋め、std::sort を実行せず、約 1,000 万回 (mod 整数除算) の検索を行いました。Pentium 4 では、n=150 で二分探索が線形探索から引き離され始めます。グラフの色については申し訳ありません。

バイナリ検索と線形検索 http://spreadsheets.google.com/pub?key=tzWXX9Qmmu3_COpTYkTqsOA&oid=1&output=image

于 2009-08-14T05:00:01.600 に答える
5

線形検索にも分岐があるため、分岐予測は重要ではないと思います。私の知る限り、線形検索を実行できる SIMD はありません。

そうは言っても、有用なモデルは、二分探索の各ステップに乗数コスト C があると仮定することです。

C log 2 n = n

代替テキスト

したがって、実際にベンチマークせずにこれを推論するには、C について推測し、n を次の整数に丸めます。たとえば、C=3 と推測した場合、n=11 で二分探索を使用する方が高速です。

于 2009-08-14T02:45:16.940 に答える
2

多くはありませんが、ベンチマークせずに正確に言うのは難しいです.

個人的には、二分探索を好む傾向があります。なぜなら、2 年後に誰かがあなたの小さな配列のサイズを 4 倍にしても、パフォーマンスはそれほど低下していないからです。もちろん、それが現在ボトルネックであり、できるだけ速くする必要があることを非常に具体的に知っていない限り.

そうは言っても、ハッシュ テーブルもあることに注意してください。それらと二分探索について同様の質問をすることができます。

于 2009-08-14T02:38:30.300 に答える