Effizienz von Programmen

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2020-10-10T07:51:57+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Klassifikation von Problemen
2 Effizienzbegriff
- 2.1 Wie wird Zeiteffizienz gemessen?

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?

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

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 mys(x):
   for x in range(x):
      print(x)

mys(5)

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