通过向量 [i] 进行线性搜索会产生 0 毫秒响应，而向量.at(i) 会产生时间

我必须补充一点：我调用线性搜索 15 000 次，每次迭代我查找的最低范围最多为 50 000 次。因此，这意味着第一次迭代有 15 000 * 50 000 次查找。这应该需要比 0ms 更长的时间。

我有这个基本的线性搜索：

bool linearSearch(std::vector<int>&primes, int number, int range) {

    for (int i = 0; i < range; i++) {
        if (primes[i] == number)
            return true;
    }
    return false;
}

我花时间使用：

void timeLinearSearch(std::vector<int>& primes) {
    clock_t start, stop;
    size_t NRND = 15000;    //  15000 primes per clock

    for (int N = 50000; N <= 500000; N += 50000)    // increase by 50k each iteration
    {
        for (int repeat = 0; repeat < 5; repeat++) {
            start = clock();
            for (int j = 0; j < NRND; j++) {
                linearSearch(primes, rand(), N);
            }
            stop = clock();
            std::cout << stop - start << ", " << N << std::endl;
        }

    }
}

这里的问题是花费的时间是0ms。向量“primes”大约包含 600 000 个元素，因此搜索保持在范围内。

在线性搜索中，如果我改变：

if(primes[i] == number)

to:

if(primes.at(i) == number)

然后我得到搜索时间> 0。

我将线性搜索与 primes.at(i) 和 std::find() 进行了比较：

for (int j = 0; j < NRND; j++) {
    std::find(primes.begin(), primes.begin() + N, rand());
}

这比我的 .at() 发现快大约 200 毫秒。

为什么我使用 std::vector[i] 进行的搜索给了我 0 毫秒的时间？

当编译器可以看到执行时linearSearch，当你使用时它可以完全优化它operator[]，因为没有副作用。这就是为什么你看到零时间。

at(..)另一方面，它有一个副作用（当索引越界时抛出），因此编译器没有选择对其进行优化。

您可以修复基准以确保调用保持在适当的位置，例如，通过计算匹配数：

int count = 0;
for (int j = 0; j < NRND; j++) {
    count += linearSearch(primes, rand(), N);
}
std::cout << stop - start << ", " << N << " " << count << std::endl;