Laufzeitmessungen

Messungen mit Python

Laufzeitmessungen mit Python sind ganz einfach:

from time import *
print("Start")
t1 = clock()
# Ausführung des Programms ...
t2 = clock()
t = t2 - t1
print("Stopp")
print("Rechenzeit: ", t)

Hier muss nur noch das Programm eingefügt werden, dessen Laufzeit ermittelt werden soll.

Wenn man beispielsweise die Laufzeit einer Implementierung von Selectionsort ermitteln möchte, dann lässt sich mit dem oben beschriebenen Anweisungsmuster so realisieren:

from time import *
from random import randint

# Sortieralgorithmus
def selectionsort(L):
    n = len(L)
    i = 0
    while i < n-1:
        minpos = i
        m = i
        while m < n:
            if L[m] < L[minpos]:
                minpos = m
            m = m+1
        h = L[i]
        L[i] = L[minpos]
        L[minpos] = h
        i = i+1
    return L
        
# Initialisierung der Liste
print("Aufbau der Testliste")
anzahl = 100
L = []
for i in range(anzahl):
    L = L + [randint(1, 10*anzahl)]
print(L)
print("Start des Sortiervorgangs")
# Sortierung der Liste
t1 = clock()
L_sortiert = selectionsort(L)
t2 = clock()
t = t2 - t1
print("Ende des Sortiervorgangs")
# Ausgabe
print(L_sortiert)
print("Rechenzeit: ", t)

Aufgabe 1

Verwende eine Implementierung des Algorithmus Sortieren durch Auswahl und das oben gezeigte Anweisungsmuster für Laufzeitmessungen.

Problematik bei Laufzeitmessungen

Wie stabil sind die Ergebnisse von Laufzeitmessungen, wenn man ein und dieselbe Liste mehrfach mit demselben Programm sortiert? Wir probieren das mit dem folgenden Testprogramm aus.

from time import *
from random import randint

# Sortieralgorithmus
def selectionsort(L):
    # ... s.o. ...
        
# Initialisierung der Liste
print("Aufbau der Testliste")
anzahl = 4000
L0 = []
for i in range(anzahl):
    L0 = L0 + [randint(1, 10*anzahl)]
# wiederholte Sortierung
for i in range(10):
    L = L0[:]
    print("Start")
    t1 = clock()
    L_sortiert = selectionsort(L)
    t2 = clock()
    t = t2 - t1
    print("Stopp")
    print("Rechenzeit: ", t)

Man erhält z.B. folgende Messergebnisse:

>>> 
Start
Stopp
Rechenzeit:  3.27038296767
Start
Stopp
Rechenzeit:  3.23336066455
Start
Stopp
Rechenzeit:  3.25390210208
Start
Stopp
Rechenzeit:  3.2653359575
Start
Stopp
Rechenzeit:  3.24174441165
Start
Stopp
Rechenzeit:  3.25976206473
Start
Stopp
Rechenzeit:  3.2584529598
Start
Stopp
Rechenzeit:  3.26073537279
Start
Stopp
Rechenzeit:  3.23565201723
Start
Stopp
Rechenzeit:  3.23315561056

Aufgabe 2

(a) Die Messergebnisse schwanken etwas. Was könnte die Ursache hierfür sein?

(b) Teste, ob du dieselben Zahlenwerte erhältst. Warum kann es sein, dass deine Messwerte in einem anderen Zahlenbereich liegen?

(c) Die folgenden Messwerte wurden bestimmt, während ein weiterer Prozess auf dem Rechner gestartet wurde. Woran erkennt man das? Auf welche Problematik deutet das hin?

>>> 
Start
Stopp
Rechenzeit:  3.2807468547
Start
Stopp
Rechenzeit:  3.41092736647
Start
Stopp
Rechenzeit:  3.4124093984
Start
Stopp
Rechenzeit:  5.37245627587
Start
Stopp
Rechenzeit:  6.69305316737
Start
Stopp
Rechenzeit:  6.70120168904
Start
Stopp
Rechenzeit:  6.67988976253
Start
Stopp
Rechenzeit:  6.67656727321
Start
Stopp
Rechenzeit:  6.70371150523
Start
Stopp
Rechenzeit:  4.73779544607