c++ - 线性搜索 vs 二进制搜索效率

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，但您确实需要使用查找的结果，以免它被优化掉。