Effizienz von Programmen

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Klassifikation von Problemen

  1. Probleme, die sich einer Formalisierung entziehen
  2. Absolut unlösbare Probleme: Halteproblem, Wortproblem für Chomsky-Typ-0-Sprachen (FSuA)
  3. Praktisch unlösbare Probleme: „Baum aller Schachspiele“; AP-Funktion (Speicher und Zeit)
  4. 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:

  1. 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?
  2. 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.

  1. 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)
  2. 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.
  3. 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

  1. 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.
  2. Wiederholen Sie das Halteproblem und charakterisieren Sie es als unlösbares Problem.
  3. 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.
  4. 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.
Persönliche Werkzeuge