线性搜索通过vector [i] yealds 0ms响应而vector.at(i)yealds时间

Question

我必须补充一点:我称我的线性搜索为15 000次,而我所查看的最低范围是每次迭代最多50 000次.因此意味着在第一次迭代中有15 000*50 000个查找.这应该花费超过0毫秒.

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

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)

至:

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()发现快大约200ms.

为什么我用std :: vector [i]搜索给我0ms的时间？

Answer 1

当编译器可以看到执行时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;