Анализ временной сложности функции, написанной на C - PullRequest
Новая
       18

Анализ временной сложности функции, написанной на C

3 голосов
/ 16 ноября 2010

Я реализовывал задачу Longest Common Subsequence в C. Я хочу сравнить время, затрачиваемое на выполнение рекурсивной версии решения и версии динамического программирования. Как найти время, необходимое для запуска функции LCS в обеих версиях для разных входов? Также я могу использовать SciPy, чтобы вывести эти значения на график и определить сложность времени?

Заранее спасибо,

Бритва

Ответы [ 3 ]

3 голосов
/ 16 ноября 2010

Для второй части вашего вопроса: краткий ответ - да, вы можете. Вам нужно получить два набора данных (по одному для каждого решения) в формате, который удобно анализировать из Python. Что-то вроде:

x y z

в каждой строке, где 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()
2 голосов
/ 16 ноября 2010

Существуют различные способы сделать это. Одним из более простых является поиск кода, который выполняет синхронизацию интервалов с высоким разрешением (микросекунда или меньше). Оберните вызовы функций таймера запуска и останова вокруг вызова функции 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. Очевидно, что вам придется параметризовать размер теста и время кода несколько раз для каждого размера.

2 голосов
/ 16 ноября 2010

Самый простой способ учесть процессорное время - это использовать функцию clock() из time.h: 

clock_t start, elapsed;

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

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

Поскольку вы просто сравниваете различные реализации, вам не нужно преобразовывать часы вединицы реального времени.

...