アルゴリズムの実行時間の比較：実行の順序が重要なのはなぜですか？

Question

私は（C++を使用して）2つの競合するアルゴリズムの実行時間を比較してみてくださいたびに、私はstd::chronoを使用するが、のように、以前この質問に例えば提案：しかし、私は常にアルゴリズムの実行順序があることことに気づくMeasuring execution time of a function in C++

実行時間に大きな影響を与えました。競合するアルゴリズムのどれが最速と見なされるかを変更することさえあります。たとえば、2つのアルゴリズムalgo1とalgo2があるとします。私が比較したい場合があり、ほぼすべてのアルゴリズム1と2の

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(); 

そしてそれ：

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(); 

以下のコードは異なる結果を与える：私は何を意味

は、以下のコードは、ということです。

私の質問は2つ折りです：1）その理由は何ですか？つまり、注文はなぜ問題なのですか？ 2）実行時間に関して2つのアルゴリズムを比較するより良い方法がありますか？つまり、より正確でより正確な比較を行うにはどうすればよいでしょうか？

PS：もちろん、私は常にすべてのコンパイラの最適化をテストします。

Answer 1

これはキャッシュの可能性が高いためです。

SAMEアルゴリズムを複数回実行することで、キャッシュの効果を簡単に確認できます。非常に最初の実行に要した時間は、その後の実行よりもかなり長くかかることに気付くでしょう。

私は博士論文のアルゴリズムを2つ比較しなければならなかったが、各アルゴリズムを10回連続して実行し、最初の結果を破棄し、残りの9つの結果を平均して9つの結果が非常に一致した。

私は2つのアルゴリズムの相対的なパフォーマンスを比較することにもっと興味があったので、廃棄された最初の結果が重要かどうかは議論の余地があります。それぞれのアルゴリズム）、異なる状況下でのキャッシュの影響や各アルゴリズムの絶対的なパフォーマンスを測定するのではなく、