Effizienz von Programmen

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.

       def mysum(x):
           total = 0                   1 Operation
           for i in range(x+1):        1 Operation, x-mal                                            
               total += i              2 Operationen, x-mal
       return total                    ---------------------
                                       1 + 3x Operationen

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 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

   def search_for_element(L,e):    # Bester Fall: e ist 1. Listenelement 
                                   # --> 1 x Zyklus --> konst. Zeit
           for i in L:             # Schlechtester Fall: e steht ganz am Ende                       
                                   # --> |L| x Zyklus --> lineare Zeit
               if i == e:
                   return True
           return False

• 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