Wikipedia · einfach zusammengefasst · Stand
Laufzeit (Informatik)
Der Begriff Laufzeit (englisch runtime) beschreibt in der Informatik einerseits die Zeitdauer, die ein Programm, ausgeführt durch einen Rechner, …
Inhalt6 Abschnitte
Grundbedeutungen von Laufzeit
Der Begriff Laufzeit, englisch runtime, hat in der Informatik zwei wichtige Bedeutungen. Erstens bezeichnet er die Zeitdauer, die ein von einem Rechner ausgeführtes Programm benötigt, um eine Aufgabe zu bewältigen. Zweitens bezeichnet er allgemein die Programmlebensphase der Ausführung, also die Phase nach der Kompilierung, der sogenannten Übersetzungszeit.
Beide Bedeutungen sind für die Informatik wichtig: Bei der ersten geht es darum, wie schnell ein Programm oder Algorithmus arbeitet. Bei der zweiten geht es darum, was während der tatsächlichen Ausführung eines Programms geschieht und welche Bedingungen dabei eine Rolle spielen.
Dauer der Ausführung
Die genaue Zeitspanne, die ein Programm zur Lösung einer Aufgabe benötigt, lässt sich oft nur durch Ausprobieren bestimmen. Ein Grund dafür ist, dass ein Befehl in einer höheren Programmiersprache vom Compiler in eine vorher nicht zwingend bekannte Anzahl von Maschinenbefehlen übersetzt wird.
Außerdem hängt die Ausführungsdauer von vielen technischen Bedingungen ab. Dazu gehören die Hardware, Verzögerungen beim Austausch von Daten zwischen Hauptspeicher und Cache, das Einlagern von Daten von der Festplatte in den Speicher durch Paging, das Betriebssystem, die CPU-Taktrate, die Größe des Hauptspeichers und die Übertragungsrate des internen Bus-Systems.
Wichtig ist auch, wie sich ein Programm verhält, wenn sich die Größe der Eingabe ändert. Solche Eingaben heißen Instanzen. Man möchte zum Beispiel abschätzen, wie stark die Laufzeit wächst, wenn mehr Daten verarbeitet werden müssen.
Asymptotische Laufzeit
In der Informatik gibt man Laufzeiten von Algorithmen meist nicht in Sekunden oder anderen Zeiteinheiten an. Stattdessen sucht man eine obere Schranke für die Anzahl einfacher Operationen, sogenannter Elementarschritte, abhängig von der Größe der Instanz. Dafür verwendet man die Landau-Notation.
Bei einem Programm, das n Zahlen sortiert, beschreibt O(n) lineares Wachstum. Das Programm macht pro eingegebener Zahl nur eine konstante Anzahl von Rechenschritten. Werden doppelt so viele Zahlen eingegeben, verdoppelt sich ungefähr auch die Ausführungsdauer.
O(n²) bedeutet quadratisches Wachstum. Das Sortierprogramm macht pro eingegebener Zahl eine konstante Anzahl von Durchläufen durch die ganze Liste. Verdoppelt sich die Eingabegröße, vervierfacht sich ungefähr die Ausführungsdauer.
O(2^n) bedeutet exponentielles Wachstum. Im Beispiel würde sich mit jeder weiteren Zahl die Laufzeit ungefähr verdoppeln. Schon bei relativ kleinen Eingabegrößen kann das zu extrem langen Laufzeiten führen. Ein Sortierprogramm erreicht einen solchen Zeitverbrauch zum Beispiel, wenn es alle möglichen Reihenfolgen der Zahlen daraufhin testet, ob sie sortiert sind.
Gewünschte Laufzeiten
Verfahren mit exponentieller Laufzeit versucht man nach Möglichkeit zu vermeiden. Ob das überhaupt immer möglich ist, gehört zu den Fragen der Theoretischen Informatik, insbesondere der Komplexitätstheorie und des Themenbereichs NP-vollständig.
Angestrebt werden Verfahren mit polynomieller Laufzeit, also O(n^k) für eine geeignete natürliche Zahl k, oder noch besser mit logarithmischer Laufzeit O(log n). Heute gebräuchliche Sortierverfahren erreichen meist eine worst case Laufzeit von O(n log n) oder O(n²). Worst case bedeutet dabei der ungünstigste Fall, der bei einer Eingabe auftreten kann.
Zu beachten ist, dass ein Programm grundsätzlich aus Eingabe, Verarbeitung und Ausgabe besteht. In Bezug auf die asymptotische Laufzeit lässt sich vor allem der mittlere Teil, also die Verarbeitung, optimieren. Ein- und Ausgabe haben in der Regel lineares Zeitverhalten, weil jeder einzelne Wert eingelesen oder ausgegeben werden muss.
Profiling
Die konkrete Bestimmung der Laufzeit von Programmen und besonders einzelner Programmteile heißt in der Softwareentwicklung Profiling. Dabei wird untersucht, wie viel Zeit bestimmte Teile eines Programms tatsächlich benötigen.
Eine Software, die Profiling unterstützt, heißt Profiler. Ein Profiler ergänzt das zu untersuchende Programm mit Code zur Laufzeiterfassung; dieser Vorgang heißt Instrumentierung. Anschließend bereitet der Profiler die Ergebnisse der Laufzeitbestimmung auf. Profiler sind häufig Teil einer integrierten Entwicklungsumgebung.
Laufzeit als Programmphase
Laufzeit bezeichnet auch die Phase, in der ein Programm in einem bestimmten Laufzeitkontext ausgeführt wird. Zu diesem Kontext gehören unter anderem unterschiedliche Hardwareeigenschaften, Eingabeparameter und Benutzer-Interaktion. Das Programm läuft dabei oft in einer genauen Konstellation, die der Entwickler vorher nicht vollständig vorhersagen konnte, höchstens näherungsweise durch Dynamische Code-Analyse.
Während der Ausführung können bestimmte Programmeigenschaften, besonders Fehler, erstmals auftreten. Dadurch erhält der Entwickler häufig Hinweise darauf, welche Änderungen am Programm nötig sind. In einem weiteren Sinn kann deshalb auch die reguläre Ausführung eines Programms als Teil des Entwicklungsprozesses angesehen werden.
Weitere Phasen neben der Laufzeit sind die Übersetzungszeit, englisch compile time, also die Phase bis zur automatischen Übersetzung des Quelltextes, und die link time. Link time bezeichnet den Zeitpunkt, zu dem das Programm aus seinen binären Programmkomponenten zu einer ausführbaren Einheit zusammengeführt wird. Manchmal wird die Phase des eigentlichen Programmierens und Modellierens als precompile time bezeichnet.
