c++ - 时间测量在 C++ 中不起作用

Question

我正在尝试对线性排序等简单算法进行运行时测量。问题是无论我做什么，时间测量都不会按预期工作。无论我使用多大的问题，我得到的搜索时间都是一样的。我和其他试图帮助我的人都同样感到困惑。

我有一个线性排序函数，如下所示:

// Search the N first elements of 'data'.
int linearSearch(vector<int> &data, int number, const int N) {
    if (N < 1 || N > data.size()) return 0;

    for (int i=0;i<N;i++) {
        if (data[i] == number) return 1;
    }

    return 0;
}

我尝试使用 C++11 中的 time_t 和 chrono 进行时间测量，但没有任何运气，除了更多的小数点。这就是我现在搜索时的样子。

vector<int> listOfNumbers = large list of numbers;

for (int i = 15000; i <= 5000000; i += 50000) {
    const clock_t start = clock();

    for (int a=0; a<NUMBERS_TO_SEARCH; a++) {
        int randNum = rand() % INT_MAX;
        linearSearch(listOfNumbers, randNum, i);
    }

    cout << float(clock() - start) / CLOCKS_PER_SEC << endl;
}

结果？ 0.126, 0.125, 0.125, 0.124, 0.124, ...(相同的值？)

我已经在 VC++、g++ 和不同的计算机上尝试过代码。

首先，我认为是我对搜索算法的实现出了问题。但是像上面这样的线性排序不能再简单了，显然是O(N)。即使问题规模增加了这么多，时间怎么可能相同？我不知所措。

编辑 1: 其他人可能会解释为什么会这样。但它实际上在更改后在 Release模式下工作: 如果(数据[i] == 数字)

收件人:

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

我不知道为什么会这样，但线性搜索在更改后可以正确测量时间。

Answer 1

执行时间大约恒定的原因是编译器能够优化部分代码。

具体看这部分代码:

  for (int a=0; a<NUMBERS_TO_SEARCH; a++) {
      int randNum = rand() % INT_MAX;
      linearSearch(listOfNumbers, randNum, i);
  }

当使用 g++5.2 和优化级别 -O3 进行编译时，编译器可以完全优化掉对 linearSearch() 的调用。这是因为无论是否调用该函数，代码的结果都是相同的。 linearSearch 的返回值没有在任何地方使用，而且该函数似乎没有副作用。所以编译器可以删除它。

您可以如下交叉检查和修改内循环。执行时间不应改变:

  for (int a=0; a<NUMBERS_TO_SEARCH; a++) {
      int randNum = rand() % INT_MAX;
      // linearSearch(listOfNumbers, randNum, i);
  }

循环中剩下的是对 rand() 的调用，这就是您似乎要测量的内容。当将 data[i] == number 更改为 data.at(i) == number 时，对 linearSearch 的调用不是 side- effects-free as at(i) 可能会抛出超出范围的异常。所以编译器并没有完全优化 linearSearch 代码。然而，在 g++5.2 中，它仍然会内联它而不进行函数调用。