3

I was implementing Longest Common Subsequence problem in C. I wish to compare the time taken for execution of recursive version of the solution and dynamic programming version. How can I find the time taken for running the LCS function in both versions for various inputs? Also can I use SciPy to plot these values on a graph and infer the time complexity?

Thanks in advance,

Razor

Jacob Relkin
  • 161,348
  • 33
  • 346
  • 320
razor35
  • 333
  • 3
  • 4
  • 11
  • Measuring elapsed time to determine time complexity of an algorithm is dangerous, as it requires a comprehensive set of input values, ranging not only in size, but also including pathalogical cases, in order to yield good results. Even measuring relative complexity of two algorithms, you have to remove constant scaling, and determine whether they have similar pathological cases. – SmacL Nov 16 '10 at 07:41

3 Answers3

3

For the second part of your question: the short answer is yes, you can. You need to get the two data sets (one for each solution) in a format that is convenient to parse with from Python. Something like:

x y z

on each line, where x is the sequence length, y is the time taken by the dynamic solution, z is the time taken by the recursive solution

Then, in 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()
mpenkov
  • 21,621
  • 10
  • 84
  • 126
2

The simplest way to account processor time is to use the clock() function from time.h:

clock_t start, elapsed;

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

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

Since you are simply comparing different implementations, you don't need to convert the clocks into real time units.

caf
  • 233,326
  • 40
  • 323
  • 462
  • I tried this. Each time I execute the function I get Elapsed clock cycles as 0. Is there way for increase the precision of the time elapsed? – razor35 Nov 21 '10 at 07:52
  • @razor35: The most accurate way to do so is to iterate over the function to be tested N times, then divide the result by N (where N could be, say, 1000000). – caf Nov 21 '10 at 09:33
2

There are various ways to do it. One of the simpler is to find some code that does high resolution (microsecond or smaller) timing of intervals. Wrap calls to the start-timer and stop-timer functions around the call to the LCS function, then print the resulting elapsed time:

#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)));

Similarly for the lcs_dynamic() function.

If the time for a single iteration is too small, then wrap a loop around the function. I usually put the timing code into a function, and then call that a few times to get consistent results.

I can point you to the package illustrated.

Yes, you could feed the results, with care, into a graphing package such as SciPy. Clearly, you'd have to parameterize the test size, and time the code several times at each size.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • +1: I basically would say the same thing, except I usually prefer using cycle register instead of timer like I do in this question : http://stackoverflow.com/questions/2786899/fastest-sort-of-fixed-length-6-int-array – kriss Nov 16 '10 at 07:46