-1

つまり、あるアルゴリズムでパフォーマンスを測定するには、ある単位で測定する必要があります。したがって、基本的に、オブジェクトの宣言と定義を無視して操作のみを考慮する場合、実行時に各操作にかかる時間をどのように推定しますか?

4

4 に答える 4

1

ライブラリc++11があります（std :: chronoを参照）。それ以外の場合は、を使用できます（boost :: chronoを参照）。これらの2つは、開始できる非常に基本的な時間測定ライブラリです。std::chronoboost::chrono

編集：c ++ 0xにはclock()関数がありますが、コメントセクションに記載されているように、これはあまり正確な測定ではありません。さらに、ほとんどのプラットフォームは、クロノ関連の操作のためのある種のAPIも提供します。

パフォーマンスの測定方法は、コンテキストによって異なります。まず、十分に大きく多様なサンプルデータのパフォーマンスを比較する必要があります。十分に大きいということは、少なくとも数秒で測定可能であることを意味します。十分に多様であるということは、すべての実行シナリオの繰り返しを均一に、またはおそらく別々にカバーすることを意味します（少なくとも、サンプルデータが何を表すかを知っている必要があります）。

十分に単純な場合、最初に実行したいのは、アルゴリズムを必要な数のセグメントに分割し、それらを呼び出しましょうA_1,...,A_N（またはA_1...A_N、同じ問題に対する異なる解決策である場合でも、概念は保持されます）。実行したいのは、同じサンプルデータで各パーティションに費やされた時間を測定することです。擬似コードの場合：

times <- (0,...,0) //vector of size N
for each input in sample data:
    start = now()
    //Run A_1 on input
    end = now()
    times[1] <- times[1] + (end-start)
    ...
    ...
    ...
    start = now()
    //Run A_N on input
    end = now()
    times[N] <- times[N] + (end-start)

この実行の最後に、各要素に費やした時間を示す時間ベクトルが残ります。これが最も基本的なアプローチです。しかし、プロファイリングの重要な要素は次のとおりです。カエルを解剖する方法はたくさんあります。また、アルゴリズムの多くのパーティションから呼び出すことができる特定の操作に費やしている時間を確認することもできます。ロード/ストア操作の数、キャッシュパフォーマンスなどを確認することを選択できます。バリエーションは多数あり、多くの場合、予期しないソースから大きな報酬が得られます（少なくとも不注意なオブザーバーには）。

より高度なプロファイリングには、サードパーティのプロファイリングフレームワークを使用できます（一部のIDEにはプロファイリング機能が組み込まれています）。

于 2013-02-18T19:21:35.580 に答える
0

最新のマシンでは、コンテキストに大きく依存します。ほとんどの命令は 1 クロックで実行されます。一部のマシンでは、クロックごとに複数の命令を取得することさえできます。一方、メモリ アクセス時間は、アクセスされる場所がキャッシュ内、メイン メモリ内、またはスワップ アウト内のいずれであるかによって、大きく異なる可能性があります。OS がメモリをマップするためにディスクにアクセスする必要がある場合は、アクセスには約ミリ秒かかりますが、データが最上位のキャッシュにあるかのように、ほぼ即時にアクセスできます。(つまり、数百ピコ秒と 10 ミリ秒の話です。) これが、局所性についてよく耳にする理由です。

于 2013-02-18T19:19:13.867 に答える
0

パフォーマンスを測定する方法はたくさんありますが、「正しい」測定方法は、実際に何をしているかによって大きく異なります。多くの場合、パフォーマンスを判断する簡単な方法は、アプリケーションに通常の動作をさせ、時間を測定することです。時間がかかる場合は、ストップウォッチを使用するだけです (たとえば、携帯電話用のアプリ、実際の腕時計または類似のもの) はうまく機能します。短期間の場合は、他の方法が必要になる場合があります-「TSC」で「CPUクロックサイクル」を使用するまで、CPU自体のタイムスタンプカウンター。

短時間しかかからないものの、アプリケーションが多くのことを行う場合、同じコードを何度も実行します。

他のアプリケーションでは、費やされた時間は実際には CPU クロック サイクルを使用して費やされていないため、より困難になります。残りの時間は、ハードディスクがそこにある実際のディスクからデータを取得するのを待つために費やされます。

アプリケーションがネットワークを使用している場合、CPU はおそらく、1 GB のネットワーク リンクを介してデータのパケットを送信するのにかかる時間の数パーセントしか使用しません。

データの種類と、データの整理、並べ替え、使用方法も重要です。既にソートされているソースからソートするものを挿入すると、ソートされていないアイテムのリストとはまったく異なる動作をする可能性があります。驚くべきことに、データがどのように保存/ソートされているかによって、良くも悪くもなります。

「コードを見て」そのパフォーマンスを判断するのは非常に難しい場合があります。コードに影響を与える要因は、「コードがどのように見えるか」以外にもたくさんあります。

動作する既存のアプリケーションがある場合は、そのパフォーマンスを測定し、プロファイリング ソフトウェアを使用して、どのくらいの時間が費やされているかを確認することをお勧めします。

于 2013-02-18T19:34:46.083 に答える
0

これらの答えはすべて、アルゴリズムを実行しているハードウェアに依存して測定されています。アルゴリズムの複雑さの一般的な測定が必要な場合は、big O および big Omega 分析を実行する必要があります。

これについてさらに質問がある場合はお知らせください。ただし、質問のタイトルによると、特定のハードウェアに基づいてパフォーマンスを測定するのではなく、アルゴリズムがデータ入力の関数として実行する命令の数を探す必要があります。

于 2013-02-18T19:41:37.647 に答える