比较算法的执行时间：为什么执行顺序很重要？

Question

每当我尝试比较两种竞争算法（使用 C++）的执行时间时，我都会使用 std::chrono，就像以前在这个问题中建议的那样：Measuring execution time of a function in C++

但是，我总是注意到被比较算法的执行顺序对执行时间有显着影响。它甚至经常改变哪些竞争算法被认为是最快的。例如，假设我有两个算法 algo1 和 algo2.

我的意思是下面的代码：

std::chrono::high_resolution_clock::time_point start0, start1;
std::chrono::high_resolution_clock::time_point end0, end1;

start1 = std::chrono::high_resolution_clock::now();
algo1();
end1 = std::chrono::high_resolution_clock::now();

start2 = std::chrono::high_resolution_clock::now();
algo2();
end2 = std::chrono::high_resolution_clock::now();

auto time_elapsed1 = std::chrono::duration_cast<std::chrono::nanoseconds>(end1 - start1).count();
auto time_elapsed2 = std::chrono::duration_cast<std::chrono::nanoseconds>(end2 - start2).count();

给出与以下代码不同的结果：

std::chrono::high_resolution_clock::time_point start0, start1;
std::chrono::high_resolution_clock::time_point end0, end1;

start2 = std::chrono::high_resolution_clock::now();
algo2();
end2 = std::chrono::high_resolution_clock::now();

start1 = std::chrono::high_resolution_clock::now();
algo1();
end1 = std::chrono::high_resolution_clock::now();

auto time_elapsed1 = std::chrono::duration_cast<std::chrono::nanoseconds>(end1 - start1).count();
auto time_elapsed2 = std::chrono::duration_cast<std::chrono::nanoseconds>(end2 - start2).count();

而且对于我可能想要比较的几乎所有算法 1 和 2。

所以，我的问题有两个方面：1) 为什么会这样，即为什么顺序很重要？ 2) 是否有更好的方法来比较两种算法的执行时间，即应该如何进行才能更好、更准确地进行比较？

PS：当然，我总是测试所有编译器的优化。

Answer 1

这很可能是由于缓存。

您可以通过运行多次使用SAME算法轻松验证缓存的效果。您可能会注意到第一次执行所花费的时间比后续执行花费的时间要长得多。

当我不得不为我的博士论文比较两个算法时，我最终连续执行每个算法 10 次，丢弃第一个结果，然后对剩余的 9 个结果进行平均，这 9 个结果非常一致。

被丢弃的第一个结果是否重要是有争议的，但对我来说并不重要，因为我更感兴趣的是比较两种算法的相对性能（因此一直在寻找一致的[=每个算法的 18=] 次）而不是测量缓存的影响或每个算法在不同情况下的绝对性能。