AuK/Effizienz von Programmen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Python</language>
==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?====
<!--
time module import time
def c_to_f(c):
return c*9/5+32
start clock t0 = time.clock()
call function c_to_f(100000)
step clock t1 = time.clock() - t0
print("t =", t, ": ", t1, "s, ")
-->
<run id="5f04ba6ceeac4">
import time # time-Package
def c_to_f(c): # Funktion definieren
for i in range(c):
a = 112 ** 5
t0 = time.clock() # Timer starten
c_to_f(10000000) # Funktion aufrufen
t1 = time.clock() # Zeit nach Funktionsabarbeitung
dt = t1 - t0 # Laufzeit ermitteln
print("t₀ =", t0, "s\rt₁ =", t1, "s\r\u0394t =", "{:.4f}".format(dt), "s")
</run>
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.
<code id="5f81681d8f567">
def mysum(x):
total = 0 # 1 Operation
for i in range(x): # i aus [0,x-1] 1 Operation, x-mal
total += i # 2 Operationen, x-mal
return total # --------------------
# 1 + 3x Operationen
</code>
<run id="5f81681d8f614">print(mysum(5))</run>
<!--
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
<code id="5ece797330c7b">
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
</code>
-->
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
<code id="5ece7bc251d66">
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
</code>
<run>print(search_for_element(range(10),7))</run>
* 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'''
* 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