Laufzeitmessungen

Die Laufzeit messen

Das folgende Testprogramm zeigt, wie man in Python die Laufzeit messen kann. Beachte, dass die Funktion primfaktoren(n) im Modul faktorisierung.py definiert ist.

from faktorisierung import primfaktoren

from time import *

n = 4563421773
t1 = clock()
ergebnis = primfaktoren(n)
t2 = clock()
t = t2 - t1

print("Zahl:        ", n)
print("Primfaktoren:", ergebnis)
print("Rechenzeit:  ", t)

Aufgabe 1

Führe selbst auf diese Weise Laufzeitmessungen durch.

Systematisch testen

Um Gesetzmäßigkeiten herauszufinden, sollte man beim Testen systematisch vorgehen.

Zunächst ist es günstig, sich auf Zahlen eines bestimmten Typs zu beschränken. Viele Probedivisionen muss das Verfahren durchführen, wenn die zu verarbeitende Zahl eine Primzahl ist. Dann muss die zu verarbeitende Zahl durch alle Zahlen von 2 bis zur Wurzel der Zahl dividiert werden.

Interessiert man sich für den Zusammenhang zwischen der Größe der vorgegebenen Zahl und der Laufzeit, sollte man die zu untersuchenden Zahlen systematisch vergrößern. Wir werden im Folgenden die vorgegebene Zahl immer (in etwa) um eine 10er-Potenz (d.h. eine Dezimalstelle) vergrößern. Als Testzahlen werden der Reihe nach die jeweils kleinsten Primzahlen genommen, die größer als die nächste 10er-Potenz ist.

from faktorisierung import primfaktoren

from time import *

testzahlen = [
11,
101,
1009,
10007,
100003,
1000003,
10000019,
100000007,
1000000007,
10000000019,
100000000003,
1000000000039,
10000000000037,
100000000000031,
1000000000000037,
10000000000000061,
100000000000000003,
1000000000000000003,
10000000000000000051,
100000000000000000039,
1000000000000000000117,
10000000000000000000009,
100000000000000000000117,
1000000000000000000000007,
10000000000000000000000013,
100000000000000000000000067,
1000000000000000000000000103,
10000000000000000000000000331,
100000000000000000000000000319]

for z in testzahlen:
    
    t1 = clock()
    ergebnis = primfaktoren(z)
    t2 = clock()
    t = t2 - t1

    print("Zahl:        ", z)
    print("Primfaktoren:", ergebnis)
    print("Rechenzeit:  ", t)
    print()

Aufgabe 2

Führe die Laufzeitmessungen durch. Entscheide selbst, wann du die Ausführung der Berechnungen abbrichst. Warum solltest du während der Messreihe keine anderen Programme starten und verwenden?

Gesetzmäßigkeiten herausfinden

Folgende Messergebnisse erhält man, wenn man systematische Laufzeitmessungen durchführt. Beachte, dass die Messergebnisse vom benutzten Rechner abhängen. Deine Messergebnisse werden sich daher wohl von den hier gezeigten unterscheiden.

>>> 
Zahl:         11
Primfaktoren: [11]
Rechenzeit:   8.93968367488e-06

Zahl:         101
Primfaktoren: [101]
Rechenzeit:   1.31301603975e-05

Zahl:         1009
Primfaktoren: [1009]
Rechenzeit:   2.6260320795e-05

Zahl:         10007
Primfaktoren: [10007]
Rechenzeit:   6.67682624468e-05

Zahl:         100003
Primfaktoren: [100003]
Rechenzeit:   0.000212317487278

Zahl:         1000003
Primfaktoren: [1000003]
Rechenzeit:   0.000668520719812

Zahl:         10000019
Primfaktoren: [10000019]
Rechenzeit:   0.00217876853064

Zahl:         100000007
Primfaktoren: [100000007]
Rechenzeit:   0.00702519454288

Zahl:         1000000007
Primfaktoren: [1000000007]
Rechenzeit:   0.0223148472781

Zahl:         10000000019
Primfaktoren: [10000000019]
Rechenzeit:   0.0867154903766

Zahl:         100000000003
Primfaktoren: [100000000003]
Rechenzeit:   0.286610449093

Zahl:         1000000000039
Primfaktoren: [1000000000039]
Rechenzeit:   0.906267137304

Zahl:         10000000000037
Primfaktoren: [10000000000037]
Rechenzeit:   2.88270213114

Zahl:         100000000000031
Primfaktoren: [100000000000031]
Rechenzeit:   9.1279123464

Zahl:         1000000000000037
Primfaktoren: [1000000000000037]
Rechenzeit:   28.5701070946

Zahl:         10000000000000061
Primfaktoren: [10000000000000061]
Rechenzeit:   91.2736900919

Aufgabe 3

Kannst du anhand der Zahlen bereits erste Zusammenhänge erkennen? Kannst du anhand der Zusammenhänge Prognosen erstellen, wie lange man wohl bis zum nächsten Ergebnis warten muss.

Gesetzmäßigkeiten beschreiben

Die Messergebnisse weisen (in etwa) folgende Regelmäßigkeit auf: Wenn man die Anzahl der Stellen der Ausgangszahl um 2 erhöht, dann erhöht sich die Laufzeit um den Faktor 10. Jede zusätzliche Stelle bei der Ausgangszahl führt also dazu, dass die Laufzeit mit dem Faktor √10 multipliziert wird.

Es handelt sich hier um ein exponentielles Wachstumsverhalten, das man mathematisch mit einer Exponentialfunktion beschreiben kann: Wenn k die Anzahl der Stellen der Ausgangszahl angibt, dann erhält man eine Laufzeit vom Typ L(k) = c*(√10)^k mit einer Konstanten c.

Prognosen erstellen

Wie lange dauert es im ungünstigsten Fall, wenn man eine natürliche Zahl mit 100 Stellen in ihre Primfaktoren zerlegen möchte?

Wenn man das Laufzeitverhalten eines Algorithmus / Programms mit einer Gesetzmäßigkeit beschreiben kann, dann lässt sich diese Gesetzmäßigkeit benutzen, um Prognosen zu erstellen.

Beim vorliegenden Programm zur Primfaktorzerlegung benötigt man etwa 1 Sekunde, um eine 12-stellige Zahl im ungünstigten Fall zu faktorisieren. Wenn die Zahl 100 Stellen haben soll, also 88 Stellen mehr als eine 12-stellige Zahl, so benötigt man nach der gefundenen Gesetzmäßigkeit 10⁴⁴-mal so lange wie bei der 12-stelligen Zahl - also etwa 10⁴⁴ Sekunden. Das ist eine Zeit, die weit jenseits jeglicher Vorstellungsmöglichkeiten liegt.