"Mein Algorithmus hat statt $$\mathcal{O}(n^{2})$$ die Laufzeit $$\mathcal{O}(n)$$" kann man oft in der Beschreibung von neuen / neu implementierten Algorithmen lesen, aber was bedeutet das eigentlich?
Ein Algorithmus besitzt keine Laufzeit. Ein Algorithmus ist nämlich eine abstrakte Anweisung, die an sich nicht ausgeführt werden kann. Diese Anweisung kann in unterschiedlichen Formen (Medien) dargestellt werden, beispielsweise Fließtext:
Fibonacci-Reihen-Berechnung:
Nimm eine natürliche Zahl n.
Wenn die Zahl Eins oder Null ist, gib 1 zurück. Sonst gib die Summe aus den Fibonacci-Reihen-Berechnungen für
n minus Eins und n minus Zwei zurück
Alternativ kann auch Pseudo-Code genutzt werden:
fibonacci_reihe(n):
n ist 1 oder n ist 0:
gib 1 zurück
gib fibonacci_reihe(n - 1) + fibonacci_reihe(n - 2) zurück
Oder auch richtiger Code. Hier empfiehlt sich eine Sprache, die möglichst wenig "Drumherum" braucht, z.B. Python:
def fibonacci(n):
if( n in (1,0)):
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
Dabei wäre aber das Letzte auf alle Fälle bereits eine Implementation, je nach Auslegung auch das Zweite.
Eine Implementation ist die Umsetzung eines Algorithmusses (abstrakte Anweisung) in eine konkrete ausführbare Form. Eine Implementation ist stets Sprachabhängig, d.h. sie basiert auf einer Programmiersprache. Die Implementation ein und desselben Algorithmusses kann sehr unterschiedlich aussehen, je nach Sprache:
In C:
long int fibonacci(unsigned int n)
{
if(n == 1 || n == 0)
{
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
Im python3:
def fibonacci(n):
if( n in (1,0)):
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
In Haskell:
fibonacci:: Int->Integer
fibonacci 0 = 1
fibonacci 1 = 1
fibonacci n = fibonacci(n - 1) + fibonacci(n - 2)
Diese Implementationen besitzen eine Laufzeit, sobald man sie ausführt: Die Laufzeit ist die Zeit, die eine Implementation zur Ausführung braucht. Also eigentlich eine Zeit in s oder ms. Diese Laufzeit ist allerdings von sehr vielen Parametern abhängig, die man (meistens) nicht einstellen kann. Beispielsweise das Betriebssystem.
Das lässt sich sehr einfach testen: Man implementiert einen Algorithmus dessen Laufzeitverhalten (Dazu später mehr) bekannt ist, beispielsweise die Traversierung einer Liste $$\mathcal{O}(n)$$ hat ein Lineares Laufzeitverhalten, testet man die Implementation allerdings, so kann man zu doch ganz anderen Ergebnissen für die Laufzeit kommen:
In [18]:
%matplotlib inline
import matplotlib.pyplot as plt
import time
def traverse_list(length):
for i in range(length):
i = i + i
def measure_time(funct, *args):
start = time.time()
funct(*args)
stop = time.time()
return stop - start
trials = list(range(1000, 50000, 100))
results = [measure_time(traverse_list, trial) for trial in trials]
plot = plt.plot(trials, results, "r-")
Das sieht zwar wirlich aus wie eine Gerade, aber bei 10000 ist irgendwie ein Buckel reingeraten. Der Graph zeigt die Laufzeit der Implementation, nicht das Laufzeitverhalten des Algorithmusses
Ein Algorithmus besitzt ein Laufzeitverhalten, d.h. eine Vorhersage, wie sich die Laufzeit einer Implementation verhalten wird. Diese Vorhersage wird anhand einer Analyse der Algorithmusses (z.B. Rekursionen(Kaskadierend, Linear), Wiederholung, ...) bestimmt.
Dabei wird das Ordnungssymbol $$\mathcal{O}$$ genutzt.
Das Laufzeitverhalten ist, anders als oft beschrieben, keine Funktion. Es beschreibt nur die Ordnung der Funkion. Betrachtet man den Graph oben, so könnte man aus der Laufzeit eine Funktion für das Laufzeitverhalten Approximieren, ungefähr $$ \mathcal{f}(n) = 0.5 \cdot n $$
Da diese Zeiten allerdings von vielen Umweltparametern abhängen ist es sinnvoller nur die Ordnung der Funktion an zu geben:
$$ \mathcal{O}(\mathcal{f}(n)) = \mathcal{O}(n) $$Natürlich ist es, besonders bei großen Programmen/Bibliotheken nicht mehr sinnvoll die Algorithmen nach Laufzeitverhalten zu analysieren. Sinnvoller ist es das Laufzeitverhalten anhand der Laufzeit ab zu schätzen. Dafür gibt es zwei Möglichkeiten:
Indem man die Laufzeit für viele Samples misst und graphisch darstellt kann man meist relativ gut zutreffende Aussagen über die Laufzeit eines Algorithmusses machen dabei wird der Graph auf unterschiedlich skalierte Achsen aufgetragen:
In [19]:
def fibonacci(n):
if( n in (1,0)):
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
trials = list(range(25))
results = [min([measure_time(fibonacci, trial) for i in range(4)]) for trial in trials]
def plot_all(trials, results):
plt.subplot(221)
plt.title("linear")
plt.plot(trials, results, "r-")
plt.subplot(222)
plt.xscale("log")
plt.title("x log")
plt.plot(trials, results, "r-")
plt.subplot(223)
plt.yscale("log")
plt.xscale("log")
plt.title("both log")
plt.plot(trials, results, "r-")
plt.subplot(224)
plt.yscale("log")
plt.title("y log")
plt.plot(trials, results, "r-")
plot_all(trials, results)
Die Gerade in logarithmischer Darstellung weist auf ein Laufzeitverhalten von
$$\mathcal{O}(x^{n})$$hin, was Sinn macht, da pro Rekursion 2 Kaskaden erzeugt werden (Kaskadierende Rekursion).
Die Taktmessungsapproximation versucht so viele störende Umweltparameter wie möglich aus zu schalten, indem auf alles was überflüssig sein könnte verzichtet wird und die Anzahl der Prozessortakte gemessen wird, die zur Ausführung nötig sind.
Dass das bei wirklich großen Bibliotheken nicht praktikabel ist, ist klar, allerdings kann es zu Optimierung von Quellcode sinnvoll sein. Am besten ist es dann gleich auf einen emulierten Prozessor, respektive auf eine Registermaschine um zu steigen.
Dann kann die Messung sehr leicht durchgeführt werden, hier am Beispiel eines iterativen Verfahrens zur Fibonacci-Reihen Berechnung:
In [20]:
from py_register_machine2.machines.small import small_register_machine
from py_register_machine2.tools.assembler.assembler import Assembler
from io import StringIO
proc, rom, ram, flash = small_register_machine()
proc.setup_done()
fib_asm = '''\
mov r0 r1
ldi 1 r2
ldi 0 r3
loop:
mov r2 r4
add r3 r2
mov r4 r3
dec r1
jgt r1 loop
ldi 0b1 ECR
'''
stream = StringIO(fib_asm)
assembler = Assembler(proc, stream)
code = assembler.assemble()
rom.program(code)
trials = list(range(100))
results = []
for trial in trials:
proc.register_interface.write("r0", trial)
proc.run()
results.append(proc.cycles)
proc.reset()
proc.cycles = 0
plot_all(trials, results)
Man sieht eine Gerade in linearer Darstellung, was sich mit der Code-Analyse deckt. Wichtig ist allerdings zu erwähnen, dass es keine "Zacken" gibt, d.h. Es wurde die naive Laufzeit gemessen, also ohne Unterbrechungen durch Betriebssystem o.ä..
Die Geschwindigkeit mit der ein Programm/eine Implementation abläuft kann auf mehrere Arten erhöht werden:
__attribute__((cold)) im GCC)Ein Beispiel für Clever Code, wieder bei der Fibonacci-Reihe:
In [21]:
calculated = {0: 1, 1: 1}
def clever_fibonacci(n):
calculated = {0: 1, 1: 1}
return __clever_fibonacci(n)
def __clever_fibonacci(n):
if(n in calculated):
return calculated[n]
calculated[n] = __clever_fibonacci(n - 1 ) + __clever_fibonacci(n - 2)
return calculated[n]
trials = list(range(2500))
results = [min([measure_time(clever_fibonacci, trial) for i in range(4)]) for trial in trials]
plot_all(trials, results)
Zeigt eine ganz erstaunliche Laufzeit, welche allerdings hervorragend ist. Faktisch wurde zwar der Algorithmus geändert, die Änderungen sind jedoch so gering, dass man von einer Optimierung reden kann.
In [23]:
def runtime_test(function, *args, trials = 4):
res = None
times = []
for i in range(trials):
start = time.time()
res = function(*args)
stop = time.time()
times.append(stop - start)
return res, min(times)
runtime_test(fibonacci, 20)
Out[23]:
bestimmt die Laufzeit einer Funktion unter den Parametern *args
In [22]: