线性搜索与二进制搜索效率

Question

我目前正在研究不同的搜索算法，并且做了一些程序来看看效率上的差异。二进制搜索应该比线性搜索更快，但是时间的确显示了其他情况。我在代码中犯了一些错误还是这是一种特殊情况？

#include <chrono>
#include <unistd.h>

using namespace std;

const int n=1001;
int a[n];

void assign() {
    for (int i=0; i<n; i++) {
        a[i]=i;
    }
}

void print() {
    for (int i=0; i<n; i++) {
        cout << a[i] << endl;
    }
}

bool find1 (int x) {
    for (int i=0; i<n; i++) {
        if (x==a[i]){
            return true;
        } 
    } return false;
}

bool binsearch(int x) {
    int l=0,m; 
    int r=n-1;
    while (l<=r) {
        m = ((l+r)/2);
        if (a[m]==x) return true;
        if (a[m]<x) l=m+1;
        if (a[m]>x) r=m-1;

    }
    return false;
}

int main() {

    assign();
    //print();
    auto start1 = chrono::steady_clock::now();
    cout << binsearch(500) << endl;
    auto end1 = chrono::steady_clock::now();

    auto start2 = chrono::steady_clock::now();
    cout << find1(500) << endl;
    auto end2 = chrono::steady_clock::now();
    cout << "binsearch: " << chrono::duration_cast<chrono::nanoseconds>(end1 - start1).count()
        << " ns " << endl;
    cout << "linsearch: " << chrono::duration_cast<chrono::nanoseconds>(end2 - start2).count()
        << " ns " << endl;

    return 0;
}

Answer 1

您的测试数据集太小（1001个整数）。填充后，它将完全适合最快的（L1）缓存；因此，您受分支复杂性的约束，而不是内存的约束。二进制搜索版本显示出更多的分支错误预测，与简单的线性遍历相比，导致更多的管道停顿。

我增加n了1000001并且还增加了测试通过的次数：

auto start1 = chrono::steady_clock::now();
for (int i = 0; i < n; i += n/13) {
    if (!binsearch(i%n)) {
        std::cerr << i << std::endl;
    }
}
auto end1 = chrono::steady_clock::now();

auto start2 = chrono::steady_clock::now();
for (int i = 0; i < n; i += n / 13) {
    if (!find1(i%n)) {
        std::cerr << i << std::endl;
    }
}
auto end2 = chrono::steady_clock::now();

我得到不同的结果：

binsearch: 10300 ns
linsearch: 3129600 ns

还要注意，您不应该cout在定时循环中进行调用，但是您确实需要使用查找的结果，以免对其进行优化。

Answer 2

To my mind N=1001 is enough to notice that binary search has a better performance. Specific realizations of linear search could be faster only for small N (approximately < 100). However, in your case the reason of such strange results is incorrect profiling measurements. All your data has been successfully cached during calculations of the first algorithm (binary search), which dramatically improved performance of the second (linear search).

If you just swap their calls, you will get an opposite result:

binsearch: 6019 ns 
linsearch: 77587 ns 

For precise measurements you should use special frameworks (google benchmark, for example), which ensures the 'fair conditions' for both algorithms.

Other online benchmarking tool (it runs the testing code on a pool of many AWS machines whose load is unknown and returns average result) gives these charts for your code without changes (with the same n=1001 as well):