-4

プログラムの実行時間の複雑さを特定する標準的な方法を探しています。hereで説明されているように、プログラムの実行時に他のパラメーターを使用するのではなく、コードを見て同じことを分析するためのソリューションを探しているわけではありません。

ユーザーが 2 進文字列を 10 進数に変換する必要があるプログラムを考えてみましょう。このようなプログラムの時間計算量は、各 2 進数が一度に処理される場合、最悪でも O(n) になります。ある程度の知性があれば、実行時間を O(n/4) に減らすことができます (一度にバイナリ文字列から 4 桁を処理し、バイナリ文字列がすべての k=1,2,3 に対して 4k 桁であると仮定します...)

このプログラムは C で作成し、time コマンドと gettimeoftheday を使用する関数 (両方) を使用して、64 ビットのクアッド コア プロセッサ (各コアが 800 MHZ) を搭載した Linux ボックスでの実行時間を 2 つのカテゴリで計算しました。

  1. システムに通常の負荷がかかっている場合 (コア使用率 5 ～ 10%)
  2. システムの負荷が高い場合 (コア使用率 80 ～ 90%)

以下は、O(n) アルゴリズムの測定値です。バイナリ文字列の長さは、通常の負荷で 100000 です。

Time spent in User (ms) - 216
Time Spent in Kernel (ms) - 8
Timed using gettimeofday (ms) - 97

以下は、O(n) アルゴリズムの測定値です。バイナリ文字列の長さは 200000 で、負荷が高い場合:

Time spent in User (ms) - 400
Time Spent in Kernel (ms) - 48
Timed using gettimeofday (ms) - 190

私が探しているもの：

  1. time コマンドを使用している場合、どの出力を考慮する必要がありますか? リアル、ユーザー、またはシステム?
  2. プログラムの実行時間を計算する標準的な方法はありますか?
  3. これらのコマンドを実行するたびに、異なる読み取り値が得られます。コードが変更されない場合、平均が常に同じになるように何回サンプリングする必要がありますか。
  4. 複数のスレッドを使用し、そのようなプログラムで execve を呼び出して各スレッドで時間を測定したい場合はどうすればよいでしょうか。

私が行った調査から、標準的なアプローチに出くわすことはありませんでした。また、使用しているように見えるコマンド/メソッドは、毎回異なる出力を提供します（これは、コンテキストスイッチとCPUサイクルが原因であることを理解しています）。ここでは、マシンに依存するソリューションでも実行できると想定できます。

4

1 に答える 1

0

質問に答えるには:

  1. コードの実行内容に応じて、出力の各コンポーネントtimeが重要になる場合があります。この質問は、それらのコンポーネントの意味を扱います。タイミングを計っているコードがシステム コールを利用していない場合は、「ユーザー」時間の計算でおそらく十分です。私はおそらく「リアルタイム」を使用するだけです。
  2. 何が問題なのtimeですか? より細かい粒度が必要な場合 (つまり、プログラム全体ではなくコードのセクションの時間を計りたいだけの場合) は、プロファイリングしているコード ブロックの前にいつでも開始時間を取得し、コードを実行してから終了時間を取得してから計算することができます。ランタイムを提供する違い。時間が単調に増加しないため、絶対に使用しないでください。gettimeofdayシステム時刻は、管理者または NTP プロセスによって変更できます。clock_gettime代わりに使用する必要があります。
  3. 実行ごとのランタイムの違いを最小限に抑えるために、特に非常に異なる結果が得られる場合は、CPU 周波数のスケーリングがオフになっていることを確認します。これは以前に私を捕まえました。
  4. 複数のスレッドを使い始めたら、プロファイラーを検討することをお勧めします。gprof は、開始するのに適した場所です。
于 2013-05-15T08:30:41.787 に答える