cで記述された関数の時間の複雑さの分析

StackOverflow https://stackoverflow.com/questions/4191658

  •  10-10-2019
  •  | 
  •  

質問

私はCで最も長い一般的なサブシーケンス問題を実装していました。私は、ソリューションと動的プログラミングバージョンの再帰バージョンの実行にかかった時間を比較したいと思います。さまざまな入力に対して両方のバージョンでLCS関数を実行するのにかかった時間を見つけるにはどうすればよいですか？また、Scipyを使用してこれらの値をグラフでプロットし、時間の複雑さを推測できますか？

前もって感謝します、

かみそり

役に立ちましたか？

解決

質問の2番目の部分については、短い答えはイエスです。 Pythonから解析するのに便利な形式で、2つのデータセット（各ソリューションに1つ）を取得する必要があります。何かのようなもの：

xyz

xはシーケンスの長さである各ラインで、yは動的ソリューションが取る時間であり、zは再帰ソリューションが取る時間です

次に、Pythonで：

# Load these from your data sets.
sequence_lengths = ...
recursive_times  = ...
dynamic_times    = ...

import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
p1 = ax.plot(sequence_lengths, recursive_times, 'r', linewidth=2)
p2 = ax.plot(sequence_lengths, dynamic_times,   'b', linewidth=2)

plt.xlabel('Sequence length')
plt.ylabel('Time')
plt.title('LCS timing')
plt.grid(True)
plt.show()

他のヒント

プロセッサの時間を考慮する最も簡単な方法は、 clock() fruction time.h:

clock_t start, elapsed;

start = clock();
run_test();
elapsed = clock() - start;

printf("Elapsed clock cycles: %ld\n", (long)elapsed);

単に異なる実装を比較しているため、クロックをリアルタイムユニットに変換する必要はありません。

それを行うにはさまざまな方法があります。より簡単なのは、間隔の高解像度（マイクロ秒または小さい）タイミングを実行するコードを見つけることです。 LCS関数への呼び出しの周りで、スタートタイマーとストップタイマー関数への呼び出しをラップし、結果の経過時間を印刷します。

#include "timer.h"

Clock clk;
char elapsed[32];

clk_start(&clk);
lcs_recursive();
clk_stop(&clk);
printf("Elapsed time (recursive): %s\n",
       clk_elapsed_us(&clk, elapsed, sizeof(elapsed)));

同様に lcs_dynamic() 働き。

単一の反復の時間が小さすぎる場合は、関数の周りにループをラップします。私は通常、タイミングコードを関数に入れてから、それを数回呼び出して一貫した結果を得ます。

図解されたパッケージを指摘することができます。

はい、慎重に結果をScipyなどのグラフパッケージに送ることができます。明らかに、テストサイズをパラメーター化し、各サイズでコードを数回時間にする必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top