线性搜索通过 vector[i] 获得 0ms 响应，而 vector.at(i) 获得时间 [英] Linear search throught vector[i] yealds 0ms response whilst vector.at(i) yealds time

问题描述

我必须补充:我调用了我的线性搜索 15 000 次，每次迭代我查找的最低范围高达 50 000.因此意味着在第一次迭代中有 15 000 * 50 000 次查找.这应该需要超过 0 毫秒的时间.

I must add: I am calling my linear search 15 000 times and the lowest range i am looking within is up to 50 000 with each iteration. Thus meaning there are 15 000 * 50 000 look ups on the first iteration. This should take longer than 0ms.

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

I have this basic Linear search:

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.向量素数"中大约有 600 000 个元素，因此搜索保持在范围内.

The problem here is that the time taken is 0ms. The vector 'primes' has roughly 600 000 elements in it so the search stays within range.

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

In the linear search, if I change:

if(primes[i] == number)

到:

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

然后我的搜索时间> 0.

then I get time > 0 taken for the search.

我通过以下方式将我的线性搜索与 primes.at(i) 和 std::find() 进行了比较:

I have compared my linear search with the primes.at(i) to std::find() by:

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

这比我的 .at() 查找快了大约 200 毫秒.

and this is roughly 200ms faster than my .at() find.

为什么我用 std::vector[i] 搜索给我 0 毫秒的时间?

Why is my search with std::vector[i] giving me 0ms time?

推荐答案

当编译器可以看到 linearSearch 的实现时，它可以在您使用 operator[] 时完全优化它，因为没有副作用.这就是为什么你看到零时间.

When the compiler can see into the implementation of linearSearch, it can optimize it out entirely when you use operator[], because there are no side effects. That is why you see zero time.

at(..) 另一方面，有副作用(当索引越界时抛出)，因此编译器无法优化它.

at(..), on the other hand, has a side effect (throwing when the index is out of bounds) so the compiler has no option of optimizing it out.

您可以修复您的基准以确保调用保持原位，例如，通过计算匹配的数量:

You can fix your benchmark to ensure that the call is kept in place, for example, by counting the number of matches:

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

这篇关于线性搜索通过 vector[i] 获得 0ms 响应，而 vector.at(i) 获得时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！