Analizzando la complessità di tempo di una funzione scritta in C

Question

I stava implementando problema Longest Common Subsequence in C. desidero confrontare il tempo impiegato per l'esecuzione della versione ricorsiva della soluzione e la versione programmazione dinamica. Come posso trovare il tempo impiegato per l'esecuzione della funzione LCS in entrambe le versioni per i vari ingressi? Inoltre posso usare SciPy per tracciare questi valori su un grafico e dedurre la complessità temporale?

Grazie in anticipo,

Razor

Answer 1

Per la seconda parte della tua domanda: la risposta è sì, è possibile. È necessario per ottenere i due insiemi di dati (uno per ogni soluzione) in un formato che è conveniente per analizzare con da Python. Qualcosa di simile:

x y z

su ciascuna linea, dove x è la lunghezza della sequenza, y è il tempo impiegato dalla soluzione dinamica, z è il tempo impiegato dalla soluzione ricorsiva

Poi, 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()

Answer 2

Il modo più semplice per il tempo conto processore è utilizzare la funzione clock() da time.h:

clock_t start, elapsed;

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

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

Dal momento che si sta semplicemente confrontando diverse implementazioni, non c'è bisogno di convertire gli orologi in unità in tempo reale.

Answer 3

Ci sono vari modi per farlo. Uno dei più semplici è quello di trovare un po 'di codice che fa alta risoluzione (microsecondi o più piccolo) i tempi degli intervalli. Avvolgere le chiamate alle funzioni di start-timer e stop-timer in tutto il chiamata alla funzione LCS, quindi stampare il tempo trascorso risultante:

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

Analogamente per la funzione lcs_dynamic().

Se il tempo per una singola iterazione è troppo piccolo, poi avvolgere un anello intorno alla funzione. Io di solito mettere il codice in una funzione di temporizzazione, e quindi chiamare che un paio di volte per ottenere risultati coerenti.

I può puntare al pacchetto illustrato.

Sì, è possibile utilizzare i risultati, con cura, in un pacchetto grafico, come SciPy. Chiaramente, che avrebbe dovuto parametrizzare il formato di prova, e ora il codice più volte ad ogni taglia.