Анализ сложности времени функции, написанной в C
-
10-10-2019 - |
Вопрос
Я реализовал самую длительную проблему подпоследовательности в C. Я хочу сравнить время, занятое для выполнения рекурсивной версии решения и динамического программирования. Как я могу найти время для запуска функции LCS в обеих версиях для различных входов? Также могу ли я использовать Scipy для построения этих значений на графике и вывести временную сложность?
Заранее спасибо,
Бритва
Решение
Для второй части вашего вопроса: короткий ответ - да, вы можете. Вам необходимо получить два набора данных (по одному для каждого решения) в формате, который удобен для разбора с Python. Что-то типа:
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()
функция из time.h
:
clock_t start, elapsed;
start = clock();
run_test();
elapsed = clock() - start;
printf("Elapsed clock cycles: %ld\n", (long)elapsed);
Поскольку вы просто сравниваете различные реализации, вам не нужно преобразовать часы в единицы в реальном времени.
Есть различные способы сделать это. Одним из самых простых является найти какой -то код, который выполняет время с высоким разрешением (микросекунд или меньше) интервалов. Оберните вызовы в функции начала TIMER и Stop-Timer вокруг вызова к функции 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. Очевидно, что вам придется параметризовать размер теста, и время кода несколько раз в каждом размере.