c - Cで記述された関数の時間計算量の分析

Question

Cで最長共通部分列問題を実装していました。再帰バージョンのソリューションと動的計画法バージョンの実行にかかる時間を比較したいと思います。さまざまな入力の両方のバージョンでLCS関数を実行するのにかかる時間をどのように見つけることができますか？また、SciPyを使用してこれらの値をグラフにプロットし、時間計算量を推測できますか？

前もって感謝します、

かみそり

Answer 1

あなたの質問の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()

Answer 2

プロセッサ時間を計算する最も簡単な方法は、次のclock()関数を使用することtime.hです。

clock_t start, elapsed;

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

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

単に異なる実装を比較しているだけなので、クロックをリアルタイムの単位に変換する必要はありません。

Answer 3

それを行うにはさまざまな方法があります。より簡単な方法の1つは、間隔の高解像度（マイクロ秒以下）のタイミングを実行するコードを見つけることです。開始タイマー関数と停止タイマー関数の呼び出しを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()。

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

図示されているパッケージを紹介します。

はい、SciPyなどのグラフ作成パッケージに注意して結果をフィードすることができます。明らかに、テストサイズをパラメーター化し、各サイズでコードの時間を数回指定する必要があります。