3.9 Laufzeitanalyse
Jeder Algorithmus benötigt für seine Ausführung eine bestimmte Laufzeit. Unter Laufzeit versteht man diejenige Zeit, die zwischen Programmstart und Programmende vergeht: Δt = t2 – t1.
Python stellt in dem Modul time die Funktion time() zur Verfügung, mit der Sie die Laufzeit eines Algorithmus messen können. Dieses Messverfahren ist aber einerseits von der individuellen Hardware abhängig und berücksichtigt andererseits nicht die Struktur des Algorithmus – die Messung sagt schlicht aus, wie lange die Berechnung auf Ihrem Computer dauert.
3.9.1 Messen der Laufzeit
Für den Algorithmus aus Listing 3.12 soll exemplarisch die Laufzeit für die Addition von zwei n×n-Matrizen gemessen werden. Dabei soll n die Werte 100, 200, 400, 800 und 1600 annehmen. Mit Listing 3.21 können Sie die Laufzeit dieser Werte messen und grafisch darstellen. Die Matrizen werden durch verschachtelte Listen repräsentiert. Eventuell müssen Sie diese Werte verkleinern, damit das Programm auch auf Ihrem Computer läuft (Zeile 06).
01 #21_laufzeit_messen.py
02 import time as t
03 import random as rnd
04 import numpy as np
05 import matplotlib.pyplot as plt
06 liste=[100,200,400,800,1600]
07 for k in liste:
08 n=k
09 a=[[rnd.randint(2,9)]*n for i in range(n)]
10 b=[[rnd.randint(2,9)]*n for i in range(n)]
11 c=[[0]*n for i in range(n)]
12 t1=t.time()
13 for i in range(n): #Zeilen
14 for j in range(n):#Spalten
15 c[i][j]=a[i][j] + b[i][j]
16 t2=t.time()
17 delta_t=(t2-t1)*1e3 #ms
18 #Ausgabe
19 print("%4d : %5.3f ms" %(k,delta_t))
20 plt.plot(k,delta_t,'rx',markersize=8)
21 #Parabel zeichnen
22 x=np.arange(0,liste[-1],0.1)
23 c=delta_t/liste[-1]**2
24 y=c*x**2
25 print("Konstante c =",c)
26 plt.plot(x,y,lw=0.8)
27 plt.xticks(liste)
28 plt.xlabel('Anzahl der Eingaben')
29 plt.ylabel('Laufzeit in ms')
30 plt.show()
Listing 3.21 Messen der Laufzeit für die Addition von zwei quadratischen Matrizen
Ausgabe
100 : 1.688 ms
200 : 6.626 ms
400 : 27.508 ms
800 : 109.921 ms
1600 : 444.353 ms
Konstante c = 0.00017357543110847474
Abbildung 3.6 Laufzeit für die Addition von zwei quadratischen Matrizen
Analyse
Die Auswertung der Messreihe ergibt, dass sich die Laufzeiten etwa vervierfachen, wenn sich die Anzahl der Matrix-Zeilen n (Zeile 08) verdoppelt. Zu bedenken ist, dass sich bei jedem neuen Programmstart die Laufzeiten ändern und abhängig von der individuellen Hardware stark abweichen können.
In den Zeilen 02 bis 05 werden die benötigten Module importiert. Die Module numpy und matplotlib.pyplot werden im nächsten Kapitel besprochen. Das Modul time stellt die Funktion time() zur Verfügung, mit der die Laufzeit in der Einheit Sekunden gemessen werden kann.
Die Liste liste in Zeile 06 enthält die Werte für die Anzahl der Zeilen einer n×n-Matrix.
In den Zeilen 09 und 10 befüllt die Funktion randint(2,9) jeweils eine n×n-Liste mit ganzzahligen Zufallszahlen. Die Matrizen werden durch verschachtelte Listen repräsentiert.
In Zeile 12 ermittelt die Python-Funktion time() die Anfangszeit t1.
In den Zeilen 13 bis 15 wird die Summe aus den beiden Listen a[i][j] und b[i][j] berechnet.
Nach Abschluss der Matrizenoperation wird in Zeile 16 die Zeit t2 ermittelt.
Die Differenz aus t2 und t1 entspricht der Laufzeit delta_t (Zeile 17). Der Faktor 1e3 bewirkt, dass die ermittelte Zeitdifferenz in ms umgewandelt wird.
In den Zeilen 19 und 20 werden die Laufzeiten ausgegeben und als Funktionsplot gezeichnet. Damit deutlich wird, dass die Laufzeit einen parabelförmigen Verlauf hat, wird in Zeile 23 die Konstante c berechnet, sodass in Zeile 24 die Funktionsgleichung der Parabel y=c*x**2 definiert und in Zeile 26 gezeichnet werden kann. Die Konstante c hat einen sehr kleinen Wert von etwa 0.0002. Bei der Bestimmung der Komplexitätsklasse von Algorithmen (siehe Abschnitt 3.9.2) werden Konstanten nicht berücksichtigt. Die Einzelheiten zu der Matplotlib-Funktionen plot() werden im nächsten Kapitel besprochen. Der Index -1 in den Zeilen 22 und 23 bewirkt, dass das letzte Element der Liste ausgelesen wird.
Wenn Sie mehr über Laufzeitmessungen in Python-Programmen erfahren wollen, besuchen Sie die Seite:
https://gertingold.github.io/pythonnawi/profiling.html
3.9.2 Komplexitätsklassen
Um Algorithmen unabhängig von der Hardware vergleichen zu können, wurde der Begriff der Laufzeitkomplexität (kurz: Komplexität) eingeführt. Darunter versteht man das Wachstum der Laufzeit in Abhängigkeit von der Anzahl n der Eingaben. Die Laufzeitkomplexität wird mit der sogenannten O-Notation (auch Landau-Notation, nach dem Mathematiker Edmund Landau) beschrieben. Sie teilt Algorithmen in bestimmte Klassen ein: Es gibt Algorithmen, deren Zeitbedarf logarithmisch, linear, quadratisch, kubisch und exponentiell mit der Anzahl der Eingaben wächst.
Bei der Einordnung von Algorithmen in eine bestimme Komplexitätsklasse wird grundsätzlich immer der ungünstigste Fall angenommen (engl. worst case), den ein Algorithmus benötigt, um alle notwendigen Operationen auszuführen. Das Verhalten des Algorithmus wird für sehr große n → ∞ untersucht. Es ist also nur sein asymptotisches Verhalten von Interesse.
Die O-Notation kann wie folgt definiert werden [Richter: 13]:
Es sei g(n) eine Funktion mit g → ∞ für n → ∞. Dann ist f ∈ O(g) genau dann, wenn
Die Funktion f wird auch als Komplexitätsfunktion bezeichnet. Für die Eingabegröße n ∈ ℕ sind auch die Bezeichnungen Problemgröße oder Eingabe gebräuchlich. Nur dann, wenn der Grenzwert aus f(n) / g(n) existiert, d. h. eine obere Schranke nachgewiesen werden kann, ist f ein Element einer bestimmten Komplexitätsklasse O. Man spricht dann: »f ist von der Ordnung Groß-O von g«.
Logarithmische Komplexität
Bei der binären Exponentiation (Listing 3.17) ist die Anzahl der Rechenschritte proportional zu O(log2n). Die Problemgröße ist hier der Exponent n. Dieser Algorithmus wird in die Komplexitätsklasse O(log n) eingeordnet. Dabei wird von der Basis des Logarithmus abstrahiert. Man spricht allgemein vom logarithmischen Laufzeitverhalten.
Lineare Komplexität
Bei dem Algorithmus für die Berechnung des Skalarprodukts (Listing 3.11, Zeile 07) werden n Multiplikationen und n – 1 Additionen, also insgesamt 2n – 1 Operationen ausgeführt. Die Problemgröße ist hier die Anzahl der Operationen n. Obwohl eine Multiplikation mehr Rechenzeit als eine Addition benötigt, werden beide Operationen als gleichrangig eingestuft. Auch werden der Faktor 2 und die Konstante –1 nicht berücksichtigt. Man legt allgemein fest: Dieser Algorithmus gehört zur Komplexitätsklasse O(n).
Als Faustregel formuliert, gilt: Werden Berechnungen innerhalb einer Schleife ausgeführt, gehört der Algorithmus zur Komplexitätsklasse O(n).
Quadratische Komplexität
Bei dem Algorithmus für die Berechnung der Summe von zwei quadratischen Matrizen (Listing 3.12) werden n2 – 1 Additionen benötigt. Konstante –1 wird nicht berücksichtigt, also wird dieser Algorithmus in die Komplexitätsklasse O(n2) eingeordnet. Die Problemgröße ist hier die Größe der Matrix.
Es gilt die Faustregel: Werden Berechnungen innerhalb der inneren Schleife von zwei ineinander verschachtelten Schleifen ausgeführt, gehört der Algorithmus zur Komplexitätsklasse O(n2).
Kubische Komplexität
Das Matrixprodukt einer quadratischen Matrix (Listing 3.13) wird in der inneren Schleife von drei ineinander verschachtelten Schleifen berechnet. Dieser Algorithmus benötigt n3 Multiplikationen und n2(n – 1) Additionen, also insgesamt 2n3 – n2 Operationen.
Er wird in Komplexitätsklasse O(n3) eingeordnet, weil nur die höchste Potenz von n für n → ∞ dominiert und der Faktor 2 nicht berücksichtigt wird. Die Problemgröße ist hier wieder die Größe der Matrix.
Der formale Nachweis, ob eine Komplexitätsfunktion f eine obere Schranke hat, kann mit dem Grenzwert
ermittelt werden.
Mit dem SymPy-Programm (Listing 3.22) können Sie überprüfen, ob eine Komplexitätsfunktion f (Zeile 04) von der Ordnung O(n3) ist. Wenn Sie in Zeile 05 den Exponenten 2 einsetzen, gibt das Programm False aus.
01 #22_o_notation.py
02 from sympy import *
03 n=symbols('n')
04 f=2*n**3-n**2
05 g=n**3
06 schranke=limit(f/g,n,oo)
07 print("obere Schranke:",schranke)
08 O_n=O(f,(n,oo)),f in O(g,(n,oo))
09 print(f,"\nist von der Ordnung ", O_n[0])
10 print(O_n[1])
Listing 3.22 Überprüfen der Komplexitätsklasse
Ausgabe
obere Schranke: 2
2*n**3 - n**2
ist von der Ordnung O(n**3, (n, oo))
True
Als Faustregel gilt: Werden Berechnungen innerhalb der inneren Schleife von drei ineinander verschachtelten Schleifen ausgeführt, gehört der Algorithmus zur Komplexitätsklasse O(n3).
Vergleich der Komplexitätsklassen
Abbildung 3.7 veranschaulicht die logarithmische, die lineare, die quadratische und die kubische Laufzeitkomplexität.
Abbildung 3.7 Vergleich der Laufzeitkomplexitäten
Abbildung 3.7 hilft Ihnen nur bei einer qualitativen Einschätzung der Laufzeitkomplexitäten. Die Laufzeit hat hier keinen konkreten Wert mehr, es wird davon abstrahiert, ob die Zeit in Nanosekunden, Millisekunden oder Sekunden gemessen wird. Welche konkreten Werte die Laufzeit für verschiedene Komplexitätsklassen annehmen kann, können Sie der Tabelle 3.9 entnehmen. Dort habe ich für 1.000 Datenelemente die Laufzeiten angegeben, die der Rechner für Algorithmen mit linearer, quadratischer und kubischer Laufzeitkomplexität benötigt. Es wird angenommen, dass der Rechner für eine Operation 1 ns (Nanosekunde) benötigt.
|
Komplexitäts-klasse |
Zeit für eine Operation in Sekunden |
Anzahl der Datenelemente |
Laufzeit |
Beispiel |
|---|---|---|---|---|
|
O(log(n)) |
10–9 |
103 |
≈10 ns |
binäre Exponentiation |
|
O(n) |
10–9 |
103 |
1 µs |
Summenalgorithmus |
|
O(n2) |
10–9 |
103 |
1 ms |
Addition von zwei quadratischen Matrizen |
|
10–9 |
103 |
1 sec |
Multiplikation von zwei quadratischen Matrizen |
Tabelle 3.9 Auswirkung der Komplexitätsklasse auf die Laufzeit
Es ist deutlich zu erkennen, dass sich mit aufsteigender Komplexitätsklasse die Laufzeit jeweils um das Tausendfache erhöht. Ab einer bestimmten Anzahl von Operationen auf Datenelemente würde auch die leistungsfähigste Hardware bei der Komplexität O(n3) scheitern. Das gilt besonders für die Komplexitätsklassen O(2n) und O(n!).