c++ - 如何找到 C++ 代码的运行时效率

Question

我正在尝试查找我最近在 stackoverflow 上发布的程序的效率。

How to efficiently delete elements from a vector given an another vector

为了比较我的代码与其他答案的效率，我正在使用 chrono 对象。

这是检查运行时效率的正确方法吗？

如果没有，请通过示例提出一种方法。

Code on Coliru

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <ctime>
using namespace std;

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    if(!vDestination.empty() && !vSource.empty())
    {
        for(auto i: vSource) {
            vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end());
        }
    }
}

int main() {
    vector<int> v1={1,2,3};
    vector<int> v2={4,5,6};
    vector<int> v3={1,2,3,4,5,6,7,8,9};
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    remove_elements(v3,v1);
    remove_elements(v3,v2);
    std::chrono::steady_clock::time_point end= std::chrono::steady_clock::now();
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() <<std::endl;
    for(auto i:v3)
        cout << i << endl;
    return 0;
}

输出

Time difference = 1472
7
8
9

Answer 1

Is it a correct way to check the runtime efficiency?

看起来不是最好的方法。我发现您的方法存在以下缺陷:

1. 值已排序。 Branch prediction使用相同的算法测试排序值和未排序值时，可能会暴露出荒谬的效果。可能的解决方法:测试已排序和未排序并比较结果。
2. 值是硬编码的。 CPU 缓存是 tricky thing它可能会在硬编码值的测试和现实生活中的测试之间引入细微的差异。在现实世界中，您不太可能对硬编码值执行这些操作，因此您可以从文件中读取它们或生成随机值。
3. 值太少。您的代码执行时间远小于计时器精度。
4. 您只运行一次代码。如果您修复所有其他问题并运行代码两次，由于缓存预热，第二次运行可能会比第一次快得多:后续运行往往会更少 cache misses比第一个。
5. 您对固定大小的数据运行一次代码。最好至少运行四次正确的测试以涵盖以下参数的笛卡尔积:
   • 已排序数据与未排序数据
   • v3 适合 CPU 缓存与 v3 大小超过 CPU 缓存。还要考虑 (v1.length() + v3.length()) * sizeof(int) 是否适合缓存的情况，(v1.length() + v2.length() + v3.length()) * sizeof(int) 是否适合缓存等所有组合。