Das Kefk Network Wiki befindet sich im Testbetrieb.
Laufzeit (Informatik)
Aus Kefk.
Der Begriff Laufzeit beschreibt in der Informatik im Wesentlichen die Zeitspanne, während der ein Programm von einem Rechner ausgeführt wird. Die Länge dieser Zeitspanne lässt sich aber häufig nur durch Ausprobieren bestimmen. Jeder Befehl eines Programms in einer höheren Programmiersprache wie z. B. Java wird vom Compiler in eine unbekannte Anzahl von Maschinenbefehlen übersetzt. Die Ausführung eines Befehls kann, je nach Hardware, weitere Verzögerungen ergeben – wenn z. B. Daten zwischen Hauptspeicher und Cache (das ist auf der ersten Ebene ein in die CPU eingebauter, sehr kleiner Zwischenspeicher für sehr oft benötigte Daten; auf tieferen Ebenen ist es ein spezieller Speicher auf dem Mainboard („second-level-cache“)) ausgetauscht werden, oder wenn die Daten erst von der Festplatte wieder in den Speicher eingelagert werden müssen (Paging). Weitere Abhängigkeiten ergeben sich von Betriebssystem, CPU-Taktrate, Größe des Hauptspeichers, Übertragungsrate des internen Bus-Systems (leitet Daten zwischen den diversen Bestandteilen eines Computers hin und her), etc.
In der Informatik versucht man daher gar nicht, konkret auszurechnen, wie viele Sekunden ein Programm auf einem bestimmten Computersystem ausgeführt wird. Stattdessen liefert die „O-Notation“, auch Landau-Notation genannt, immerhin eine ungefähre Angabe, wieviel Zeit zwischen Programmstart und -ende vergehen würde (vgl. hierzu Asymptotische Laufzeit). Diese Größe beachtet keine Einflussgrößen außer der Eingabegröße mehr, und beschreibt ein ungefähres Wachstumsverhalten der Laufzeit für größere Eingaben.
Einige Beispiele anhand eines Programms, das n Zahlen sortiert:
- „O (n)“ beschreibt ein lineares Wachstum der Eingabe. Solch ein Programm macht pro eingegebener Zahl nur eine konstante Anzahl von Rechenschritten.
- „O (n²)“ bedeutet quadratisches Wachstum. Das Sortierprogramm macht pro eingegebener Zahl eine konstante Anzahl von Durchläufen durch die ganze Liste; die Laufzeit insgesamt ist ein Wert in der Größenordnung x · n² + y · n + z, wobei sich allerdings x, y und z nicht exakt bestimmen lassen.
- „O (2n)“ würde schließlich exponentielles Wachstum bedeuten. Im Beispiel des Sortierprogramms würde sich mit jeder weiteren Zahl die Laufzeit (ungefähr) verdoppeln, was bereits bei 100 Zahlen mehrere hundert Millionen Jahre dauern kann. Solch einen Zeitverbrauch erreicht ein Sortierprogramm beispielsweise, indem es alle möglichen Reihenfolgen der Zahlen daraufhin testet, ob sie sortiert sind.
Verfahren mit exponentieller Laufzeit versucht man daher nach Möglichkeit zu vermeiden – ob das überhaupt geht, ist eine der Fragen, die man sich in der Theoretischen Informatik stellt (vgl. dazu Komplexitätstheorie, „NP-vollständige“ Probleme (NP-vollständig). Angestrebt werden Verfahren mit polynomieller Laufzeit, also salopp gesagt „n hoch irgendwas“. Man beachte dabei, dass ein Programm im Grunde dreigeteilt ist – Eingabe, Verarbeitung, Ausgabe – und dass sich nur der mittlere Teil in dieser Hinsicht optimieren lässt.
Laufzeit als Teil des Entwicklungsprozesses
Während der Entwicklung des Computerprogramms werden verschiedene Zustandsklassen des Programms unterschieden: hier beschreibt die Laufzeit (runtime) die Ausführung und auch die spätere Nutzung des kompilierten Programmes durch den Verbraucher, während die Kompilierzeit (compiletime) den Zeitpunkt der Komponentenkompilierung, die linktime den Zeitpunkt des Zusammenführens der Programmkomponenten zu einer ausführbaren Einheit und die precompiletime das eigentliche Programmieren und Modellieren beschreibt. In jedem Zustand können unterschiedliche Fehlerklassen auftreten, die aus einem anderen Zustand möglicherweise nicht sichtbar sind.
