比较算法的执行时间:为什么执行顺序很重要? [英] Comparing algorithms' execution time: why does the order of execution matter?
问题描述
每当我尝试比较两种竞争算法的执行时间(使用 C++)时，我都会使用 std::chrono 就像以前在这个问题中建议的那样:在 C++ 中测量函数的执行时间
Whenever I try to compare the execution time of two competing algorithms (using C++), I use std::chrono as formerly suggested for example in this question: Measuring execution time of a function in C++
然而，我总是注意到被比较的算法的执行顺序对执行时间有显着影响.它甚至经常改变哪个竞争算法被认为是最快的.例如，假设我有两个算法 algo1 和 algo2.
However, I always notice that the order of execution of the algorithms being compared significantly impacts on the execution times. It often even alters which of the competing algorithms is to be considered the fastest. For instance, suppose I have two algorithms algo1 and algo2.
我的意思是下面的代码:
What I mean is that the code below:
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();
从下面的代码给出不同的结果:
Gives different results from the code below:
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.
And that for almost any algorithms 1 and 2 that I might want to compare.
所以，我的问题有两个方面:1)为什么会这样，即为什么顺序很重要?2) 是否有更好的方法来比较两种算法的执行时间，即应该如何进行更好和更准确的比较?
So, my question is two-folded: 1) why is that the case, i.e. why does the order matter? 2) Is there a better way of comparing two algorithms in what regards their execution time, i.e. how should one proceed for better and more accurate comparisons?
PS:当然，我总是在所有编译器优化的情况下进行测试.
PS: of course, I always test with all compilers' optimizations on.
推荐答案
这很可能是由于缓存造成的.
This is most likely to be due to caching.
您可以通过多次运行 SAME 算法轻松验证缓存的效果.您可能会注意到，第一次执行所用的时间明显长于后续执行.
You can easily verify the effect of caching by running the SAME algorithm multiple times. You will likely notice that the time taken of the very first execution takes significantly longer than subsequent executions.
当我不得不为我的博士论文比较两种算法时，我最终将每种算法连续执行 10 次，丢弃第一个结果，然后对剩余的 9 个结果求平均值，这 9 个结果非常一致.
When I had to compare two algorithms for my PhD thesis I ended up executing each algorithm 10 times in a row, discarded the very first result, then averaged the remaining 9 results, and those 9 results were very consistent.
被丢弃的第一个结果是否重要是有争议的，但对我来说并不重要，因为我更感兴趣的是比较两种算法的相对性能(因此正在寻找每个算法的一致运行时间算法)，而不是衡量缓存的影响或每种算法在不同情况下的绝对性能.
It is arguable whether the first result that was discarded is important or not, but for me it wasn't, because I was more interested in comparing the relative performances of the two algorithms (thus was looking for consistent run times of each algorithm) rather than measuring the impact of caching or the absolute performances of each algorithm under different circumstances.
这篇关于比较算法的执行时间:为什么执行顺序很重要?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
