Analyse von Zeit Komplexität einer Funktion in C geschrieben

Question

Ich war die Umsetzung Problems der längste gemeinsame Teilsequenz in C. Ich mag die Zeit für die Ausführung der rekursiven Version der Lösung und die dynamischen Programmierung Version genommen vergleichen. Wie kann ich die Zeit für die Ausführung der LCS-Funktion in beiden Versionen für verschiedene Eingaben gemacht finden? Auch kann ich SciPy verwenden diese Werte in einem Diagramm zu zeichnen und die Zeitkomplexität ableiten?

Vielen Dank im Voraus,

Razor

Answer 1

Für den zweiten Teil Ihrer Frage: Die kurze Antwort lautet: Ja, Sie können. Sie müssen die beiden Datensätze (einen für jede Lösung) in einem Format zu erhalten, die mit von Python zu analysieren bequem ist. So etwas wie:

x y z

in jeder Zeile, wobei x die Sequenzlänge ist, y die Zeit durch die dynamische Lösung genommen wird, z ist die Zeit von der rekursiven Lösung genommen

Dann 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

Der einfachste Weg, um Kontoprozessorzeit ist die clock() Funktion von time.h zu verwenden:

clock_t start, elapsed;

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

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

Da Sie einfach unterschiedliche Implementierungen zu vergleichen, müssen Sie nicht die Uhren in Echtzeiteinheiten konvertieren.

Answer 3

Es gibt verschiedene Möglichkeiten, es zu tun. Eine der einfacheren ist etwas Code zu finden, die eine hohe Auflösung hat (Mikrosekunde oder kleiner) Timing-Intervallen. Wrap ruft die Start-Timer und Stop-Timer-Funktionen rund um den Anruf an die LCS-Funktion, dann die resultierende verstrichene Zeit drucken:

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

Ebenso für die lcs_dynamic() Funktion.

Wenn die Zeit für eine einzelne Iteration zu klein ist, wickeln Sie dann eine Schleife um die Funktion. Ich in der Regel den Timing-Code in eine Funktion setzen, und rufen Sie dann, dass ein paar Mal konsistente Ergebnisse zu erhalten.

Ich kann Sie zu dem Paket dargestellt zeigen.

Ja, könnten Sie die Ergebnisse füttern, mit Sorgfalt, in eine grafische Darstellung Paket wie SciPy. Natürlich würden Sie die Testgröße und Zeit, um den Code mehrmals in jeder Größe parametrieren müssen.