logo标签列表

在现代CPU上，二分搜索在哪个n值时比线性搜索更快？

algorithmsearchpremature-optimization
22

由于分支预测的神奇作用，对于整数数组的线性搜索，二分查找可能会更慢。在典型的台式机处理器上，当这个数组变得多大时，使用二分查找会更好？假设该结构将被用于许多查找。

1
这将取决于对所涉及数据进行比较的成本。 - bdonlan
10
OP明确而明显地指出，他正在谈论一个整数数组——你还担心什么其他变化？！ - Alex Martelli
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;
}

我的一些在Core Duo上的时间记录：

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

无论如何，它们都是相当可重复的...

楼主说：Alex，我编辑了你的程序，只用1到n填充数组，没有运行std::sort，并进行了大约1000万（mod整数除法）次搜索。 在Pentium 4上，二分查找在n = 150时开始跑赢线性查找。对于图表颜色感到抱歉。

二分查找与线性查找 http://spreadsheets.google.com/pub?key=tzWXX9Qmmu3_COpTYkTqsOA&oid=1&output=image

这是-O -- -O3使线性搜索变得稍微糟糕了一点，大约178毫秒左右，而二进制搜索则变得更好了，大约222毫秒左右。 - Alex Martelli
5
我认为分支预测不应该有影响，因为线性搜索也有分支。就我所知，没有 SIMD 可以为您执行线性搜索。
话虽如此，一个有用的模型是假设二分搜索的每一步都有一个乘数成本C。
C log2 n = n
这样，在不实际进行基准测试的情况下，您可以猜测 C，并将 n 四舍五入到下一个整数。例如，如果您猜测 C=3，则在 n=11 时使用二分搜索会更快。 alt text
@joeforker，如果有117个元素，二分查找会更快。 - Unknown
看起来很遗憾要+1，因为你的声望值是一个如此整洁的数字（10,000）。 - Rich Seller
@ Rich Seller，我今天已经达到了上限。当声望计数器在格林威治标准时间晚上12点重置时，请明天给我点赞。 - Unknown
5
@Unknown 的秘密是，在线性搜索中，分支会被正确地预测，直到找到目标项为止。 - joeforker
5
分支数量并不重要，重要的是分支被执行的概率。在线性搜索中，程序总是按照相同的方式执行（始终会执行或始终不会执行），直到找到匹配项。而在二分搜索中，由于经常执行相同的分支（无论是执行还是不执行），每个步骤都有50％的可能性被错误预测。 - doug65536
2

没有太多 - 但很难准确地说出来，需要进行基准测试。

就个人而言，我倾向于使用二分查找，因为两年后，当其他人将您的小数组大小增加四倍时，您不会损失太多性能。当然，除非我非常明确地知道它现在是瓶颈，我需要尽可能快地运行。

话虽如此，请记住还有哈希表；您可以问一个类似的问题，比较哈希表和二分查找。

1
是的，哈希表在元素数量达到数千个之前非常慢。 楼主的问题非常重要。 - Elliott
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接