0

Visual C++ 2010 で実装され、正常に動作する 2 つのアルゴリズムがあります。複雑さの 1 つは n*log(n) であり、もう 1 つは n^2 であることがわかっています。しかし、それぞれの実行に必要な時間を実際に「測定」するにはどうすればよいでしょうか。問題は、数マイクロ秒のように非常に高速に実行されることです。その精度で測定できますか? または、たとえば、それぞれに必要な CPU サイクルをカウントできますか? それらの各ループに遅延を追加するのは正しいですか?

4

2 に答える 2

1

入力が小さい場合、実行時間の漸近的な測定はスクワットを意味します。これは、定数が無視できない可能性があり、考慮に入れる必要があるためです。

ビッグ O 表記は便利で、入力サイズが大きい場合 (アルゴリズム ペアごとn>Nの定数のすべての入力サイズの場合) にのみ、「どのアルゴリズムが優れているか」を正しく予測します。N

2 つのアルゴリズムのどちらが優れているかを測定するには、経験的および統計的アプローチを試す必要があります。
数千 (またはそれ以上) の異なるテスト ケースを (自動的に) 生成し、テスト ケースでアルゴリズムを実行します。ベンチマークの実行を開始する前に、システムをウォームアップすることを忘れないでください。

テスト ケースごとにアルゴリズムにかかった時間 (ナノ秒) を見つけ、統計的手段を使用して 2 つを比較します。平均時間を確認できます。

また、 Wilcoxon 検定などの統計検定を実行して、実行時間の差に統計的有意性があるかどうかを確認する必要があります。

重要:マシンが異なれば、または入力の分布が異なると、結果が異なる場合があることに注意してください。このテストにより、特定のマシンおよびテスト ケースの分布に対する信頼が得られます。

于 2013-02-22T16:00:09.507 に答える
0

典型的な「テストベッド」(C から継承) は次のようになります。

#define n 20
#define itera 10000000

int main(int argc, char* argv[])
{
    clock_t started;
    clock_t stopped;
    double duration;

    started = clock();

    for (unsigned long i = 0; i < itera; i++)
    {   
      for (unsigned k = 0; k < n; k++)
      {
         ....
      }
    }

    stopped = clock();

    duration = (double)(stopped - started) / CLOCKS_PER_SEC;

}

よくある落とし穴:

コンパイラは、結果が誤解を招くような方法でコードを最適化する場合があります。(たとえば、変数を割り当て、後でその変数を使用しない場合、計算と割り当てが省略される可能性があります)

テストを実行している間、システムは他のことでビジー状態になっている可能性があります。十分な頻度でテストを繰り返します。

キャッシュ効果が速度に影響を与える可能性があります。これは、ディスク アクセス時間が重要な役割を果たしている場合や、大量のメモリが関係している場合に特に当てはまります。

アルゴリズムのパフォーマンスは、多くの場合、テスト データに依存します。

テストベッドの外側のループは、実際のアルゴリズムよりも時間がかかる場合があります。この影響を考慮して、空のループを測定します。

于 2013-02-22T16:21:53.883 に答える