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

Question

每当我尝试比较两个竞争算法(使用C++)的执行时间时,我std::chrono就像以前在这个问题中建议的那样使用:测量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

这很可能是由于缓存造成的。

您可以通过多次运行相同的算法轻松验证缓存的效果。您可能会注意到，第一次执行所需的时间明显长于后续执行的时间。

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

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