Effizienz von Programmen
Aus ProgrammingWiki
Inhaltsverzeichnis |
Klassifikation von Problemen
- Probleme, die sich einer Formalisierung entziehen
- Absolut unlösbare Probleme: Halteproblem, Wortproblem für Chomsky-Typ-0-Sprachen (FSuA)
- Praktisch unlösbare Probleme: „Baum aller Schachspiele“; AP-Funktion (Speicher und Zeit)
- Algorithmisch (inkl. mit Formel) lösbare Probleme
Effizienzbegriff
FALSCH: Computer sind immer schneller geworden, sodass die Effizienz von Programmen keine Rolle spielt
RICHTIG: Wir bestimmen den Aufwand (Ressourcenverbrauch: Zeit, Speicher) in Abhängigkeit von der Problemgröße $n$.
Zwei grundlegende Fragen, die wir uns in diesem Lehrgebiet stellen:
- Wie können wir für konkrete Programme bestimmen (vorhersagen, i. S. einer Vorab-Leistungsgarantie), welche Rechenzeit sie zur Lösung eines Problems bestimmter Größe benötigen werden?
- Kann man diesen erforderlichen Zeitaufwand für typische algorithmische Entwurfsmuster angeben bzw. begrenzen?
Effizienzbegriff Zeit-/Speicherbedarf. Die (Zeit-)Effizienz eines Programmes ist umso besser, je weniger Zeit es zur Lösung eines Problems benötigt.
Wir beschränken uns auf die Betrachtung der Zeiteffizienz. Begründung: Trade-off (Tauschgeschäft) zwischen Zeit- und Speichereffizienz. Beispiel „Fibonacci-Zahlen, rekursiv“: Memoizing kostet zwar Speicher aber reduziert die Rechenzeit, da Mehrfachberechnungen vermieden werden. ⇒ Es reicht, sich nur mit der Zeiteffizienz zu beschäftigen.
- Problem: große Unterschiede zwischen einzelnen Probleminstanzen in Bezug auf die Effizienzaussage (z. B. Suchverfahren, wenn das zu suchende Element ganz am Anfang einer Liste steht; Primzahlprüfung für $n$-stellige natürliche Zahlen)
- Problem: Einfache Lösungen (d. h. schnell ermittelbare Resultate für kleine Problemgrößen) skalieren nicht mit wachsender Problemgröße. D. h. kein linearer Zusammenhang.
- Problem: Wie können wir entscheiden, welche Option für ein Programm die effizienteste ist?
Wie wird Zeiteffizienz gemessen?
… mit einem Timer?
Nachteile:
- Zeitmessung ist inkonsistent
- Ziel: verschiedene Algorithmen bewerten
- Laufzeit variiert zwischen Alg., zwischen Implementationen, zwischen Computern auf denen sie laufen
- Ergebnisse sind unter Verwendung kleinerer Inputs nicht vorhersagbar.
- keine Aussage zum Verhältnis zwischen Eingabe und Rechenzeit
… durch Zählen der Operationen
Annahme, dass bestimmte elementare/atomare Operationen (z.B. math. Op., Zuweisungen, Zugriff auf Obj., Vergleiche) konstante Zeit beanspruchen. Dann zählt man die Operationen, die in Abhängigkeit von der Inputgröße ausgeführt werden.
Ergebnis: Wenn ich die Eingabe verzehnfache, verdreißigfacht sich die Zahl der Elementaroperationen.
Diese Messmethode ist besser als die erste (Zeitmessung), hat Vorteile:
- ist unabhängig vom konkreten (vernetzten) Computer, auf dem das Programm läuft
- Ergebnis ist eine Relation zwischen Input und Berechnungsaufwand (Zählung)
und Nachteile:
- ist implementationsabhängig
- keine klare Definition, welche Operationen zu zählen sind
… als funktionaler Zusammenhang $T:n\rightarrow T(n)$ und abstrakte Notation für die Aufwandsordnung
Suche eines Elements in einer (unsortierten) Liste
- Notation $\mathcal{O}(n)$ … asymptotische Ordnung … $n$ ist die Länge der Liste
- Leicht zu übertragen: z.B. zwei ineinander verschachtelte Schleifen, je 1…n: $\mathcal{O}(n^2)$
- Unabhängigkeit vom Comp., auf dem das Programm läuft
- Takte einer Turingmaschine als abstraktes Modell für die Bit-Komplexität -- kommt meist zum Einsatz
- Den Gegensatz bildet die Registermaschine, RAM, für die uniforme Komplexität, bei der die Länge der Eingabe(n), d.h. die Größe der Eingabewerte, keine Rolle spielt.
Übungsaufgaben
- Legen Sie nach dem Vorbild des AuK-Buches, S. 13 unten, eine Tabelle für die AP-Funktion an und füllen Sie sie aus. Verwenden Sie ein Programm in einer Programmiersprache Ihrer Wahl.
- Wiederholen Sie das Halteproblem und charakterisieren Sie es als unlösbares Problem.
- Skizieren Sie nach der Beschreibung im AuK-Buch, S. 13, Aufg. 1.1, den Baum der Schachspiele (Ausschnitt, beginnend mit einer imaginären Wurzel) und schätzen Sie den Speicherbedarf ab.
- Begründen Sie mit mathematischer Argumentation, dass der Berechnungsaufwand von der Wahl der Zahlenbasis (b=2, b=10 usw.) unabhängig ist. Arbeiten Sie dazu das entsprechende Textstück auf S. 17, Beispiel 1.1, im AuK-Buch durch.