线性搜索向量[i]的响应时间为0ms，而向量.at(i)的响应时间为0ms

Question

我必须补充:我正在调用我的线性搜索15,000次，我正在寻找的最低范围是每次迭代高达50,000。这意味着在第一次迭代中有15000 * 50000次查找。这应该比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。向量'prime '大约有60万个元素，所以搜索保持在范围内。

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

if(primes[i] == number)

:

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

那么我得到时间> 0的搜索。

我将我的线性搜索与质数。at(I)与std::find()进行了比较:

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

，这比我的。at() find.

快了大约200ms。

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

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;

Answer 2

在编写这样的比较代码时确实需要小心;一定要确保你有一个严谨的统计方法来解释你的数据。假设你有这个，这里有一个解释:

[i]不需要检查i是否在向量的边界内，而at(i) 必须检查。

这解释了速度上的差异:你的编译器能够为[]生成更快的代码。

Answer 3

我觉得你是在比较苹果和橘子。您要求查找"rand()"元素，因此每次运行时它都是不同的数字

像这样查找元素(假设你有N个素数):质数[N/10]，质数[N/2]，质数(3*N/4)，…对于要找到的元素(如果你想找不到项目，请加上+1)

注意，如果您的素数数组是按递增顺序排序的，那么如果primes[i]> number而不是遍历整个数组(甚至进行二分搜索)，您可能希望返回false，除非您只是查看。at()求值