AuK/Einführung SS12

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==Effizienzbegriff==

===Qualitative Beschreibung von Effizienz===
;Ein Algorithmus heißt effizient, wenn er ein vorgegebenes Problem mit möglichst geringem Ressourcenaufwand (Zeit, Speicher) löst.

Diese Beschreibung hält einer quantitativen Bewertung effizienter Algorithmen nicht stand und muss von daher präzisiert werden. Außerdem ist zu beachten, dass Zeit und Speicher ineinander "umwandelbar" sind. D.h., wenn man bei der Modellierung möglichst knappen Speicher wählt, kann es sein, dass dies die Berechnungskomponente des Algorithmus' belastet: Ein Zusatzaufwand kann erforderlich sein, da gewisse Daten zwischengerechnet werden müssen, weil sie nicht direkt zur Verfügung stehen.

Wir werden uns im Folg. im Wesentl. der Zeiteffizienz von Algorithmen widmen.

===Problem und Instanzen eines Problems===

Es ist bekannt, dass ein betrachtetes Programm für verschiedene Eingaben verschiedene Rechenzeiten zur Bestimmung der entsprechenden Ausgaben benötigt. Wenn wir an einen Primzahltest durch Probeteiler für eine zu untersuchende natürliche Zahl $n$ denken, ist das nicht verwunderlich: Für sehr große Primzahlen ist das wesentlich aufwändiger als für kleine Zahlen, denn es gibt viel mehr Teilerkandidaten. 

Häufig ist es außerdem so, dass die Bearbeitungen "vergleichbarer" Eingaben völlig verschiedene Zeitaufwände erfordern. In unserem Primzahltest-Beispiel erfordert die Untersuchung der Zahl $49$ bereits vier Probeteiler, nämlich $2,3,5,7$, während für $50$ schon im ersten Schritt klar ist, dass sie keine Primzahl sein kann, weil sie gerade ist.

Das Beispiel zeigt, dass es ''falsch'' wäre zu sagen, dass der Berechnungsaufwand mit zunehmender Problemgröße $n$ steigt. Es gibt vielmehr "solche und solche" Kandidaten nahezu gleicher ''Größe''. Als Größe legen wir die Stelligkeit der gewählten Darstellung, z.B. zweistellige Zahlen im Dezimalsystem, fest.

Deshalb macht es Sinn, die Eingabewerte in Gruppen gleicher Größe einzuteilen. Im Beispiel untersuchen wir also den Aufwand für den Primzahltest für $n$-stellige Zahlen. Für jede Gruppe, z.B. $n=10, 100, 1000, 10000, 100000, 1000000$, wählen wir z.B. $k=5$ Kandidaten zufällig aus und ermitteln die zugehörigen Zeitaufwände. Die folgende Tabelle zeigt den Kern unserer experimentellen Vorgehensweise.

{| class="wikitable"
|-
! $n$         !! 1 !! 2 !! 3 !! 4 !! 5 !! $T(n)$
|-
| 10 || ... || ... || ... || ... || ... || .?. 
|-
| 100 || ... || ... || ... || ... || ... || .?. 
|-
| 1000 || ... || ... || ... || ... || ... || .?. 
|-
| 10000 || ... || ... || ... || ... || ... || .?. 
|-
| 100000|| ... || ... || ... || ... || ... || .?. 
|-
| 1000000|| ... || ... || ... || ... || ... || .?. 
|}

Wenn wir uns nun vorstellen, dass die Pünktchen durch die ermittelten Rechenzeiten (z.B. als Takte einer abstrakten Maschine; s. weiter unten) ersetzt wurden, bleibt die Frage nach dem Ersatz des jeweils zugehörigen Fragezeichens. 

Je nach Analysetyp macht es Sinn entweder das Maximum, das Minimum bzw. den Durchschnitt zu bestimmen:

:'''worst-case-Analyse''': liefert eine (sichere) Aussage zum schlechtestmöglichen Aufwandsverhalten.
$$T(n)=\max_k\{T(i)\mid i\in I_n\}$$
:'''best-case-Analyse''': gibt die bestmögliche Performance-Erwartung (eher unpraktikel).
$$T(n)=\min_k\{T(i)\mid i\in I_n\}$$
:'''average-case-Analyse''': Wenn die Differenz zwischen worst- und best-case-Analyse sehr groß ist, gibt die average-case-Analyse mehr Aufschluss.
$$T(n)=\frac{1}{k}\sum\limits_{i\in I_n}T(i)$$

In obigen Ausdrücken steht $I_n$ für die Menge der Instanzen der Problemgröße $n$ und $k$ bezeichnet die Anzahl der Instanzen der Größe $n$, d.h. $k=|I_n|$.




==Beispiel: Dublettensuche in einer Liste==
Vereinfachend nehmen wir an, dass es sich um Listen mit Zufallszahlen handelt. Sobald ein doppeltes Listenelement gefunden wurde, soll das Verfahren mit der Ausgabe dieses Elements stoppen, anderenfalls stoppt der Algorithmus ohne Ausgabe eines Wertes. 

Das Programm aus dem ersten Lösungsvorschlag arbeitet mit quadratischem Aufwand:

<code id="4ba10f22f3796" hidden>
;;; Zufallszahlgenerator
(define random-maker
  (let* ((multiplier 48271)
         (modulus 2147483647)
         (apply-congruence
          (lambda (current-seed)
            (let ((candidate (modulo (* current-seed multiplier) modulus)))
              (if (zero? candidate)
                  modulus
                  candidate))))
         (coerce
          (lambda (proposed-seed)
            (if (integer? proposed-seed)
                (- modulus (modulo proposed-seed modulus))
                19860617))))  ;; an arbitrarily chosen birthday
  (lambda (initial-seed)
    (let ((seed (coerce initial-seed)))
      (lambda args
        (cond ((null? args)
               (set! seed (apply-congruence seed))
               (/ (- modulus seed) modulus))
              ((null? (cdr args))
               (let* ((proposed-top
                       (ceiling (abs (car args))))
                      (exact-top
                       (if (inexact? proposed-top)
                           (inexact->exact proposed-top)
                           proposed-top))
                      (top
                       (if (zero? exact-top)
                           1
                           exact-top)))
                 (set! seed (apply-congruence seed))
                 (inexact->exact (floor (* top (/ seed modulus))))))
              ((eq? (cadr args) 'reset)
               (set! seed (coerce (car args))))
              (else
               (display "random: unrecognized message")
               (newline))))))))

;(define random 
;  (let ((seed (time-nanosecond (current-time))))
;    (display seed)
;    (random-maker seed)))

(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)   ; stellt current-time usw. bereit

(define random (random-maker (time-nanosecond (current-time))))
</code>

Die folgende Prozedur stellt eine Liste mit <math>n=30</math> Zufallszahlen aus dem Intervall <math>[0,m[</math> bereit, <math>m=100</math>.
<code id="4ba112fcb41e1">
(define zliste
  (lambda (n m)
    (if (= n 0) 
        '()
        (cons (random m) (zliste (- n 1) m)))))
</code>
<run id="4ba10f230009b">(zliste 30 100)</run>

Die Dublettensuche wird durch zwei verschachtelte Laufanweisungen berechnet. Die darin enthaltene Variable <nowiki>escape</nowiki> sorgt dafür, dass der Zyklus verlassen wird, sobald eine Dublette gefunden wurde.

<run id="4ba11bad8f665">
(let* ((n 20)(a (list->vector (zliste (+ n 1) 300)))(escape #f) (vergleiche 0))
  (display a)(newline)
  (do ((i 1 (+ i 1)))
    ((or escape (= i n)) vergleiche)
    (do ((j (+ i 1) (+ j 1)))
      ((or escape (> j n)) 'stop)
      (set! vergleiche (+ vergleiche 1))
      (if (= (vector-ref a i) (vector-ref a j))
          (begin
            (set! escape #t)
            (display (vector-ref a i))
            (newline))))))
</run>

Die Anzahl der Vergleiche beträgt höchstens <math>(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}</math>. Für <math>n=20</math> sind das also höchstens 190 Vergleiche. Die Dublettenermittlung erfolgt also mit quadratischem Aufwand.

Eine aus dem Hashing bekannte Idee liefert ein wesentlich schnelleres Dublettsuchverfahren. Es braucht allerdings auch viel mehr Speicher. Das ist keine Seltenheit: Gibt man mehr Speicher, kann der darüber organisierte Prozess Rechenzeit einsparen. Umgekehrt haben Speichersparmaßnahmen negative Auswirkungen auf die Performance.

Die Idee besteht darin, für jedes Element <math>A[i]</math> des Zufallsvektors in einem zweiten Vektor <math>B[A[i]]</math> dessen Existenz zu vermerken. Der Wert des Elements ist also der betreffende Index von <math>B</math>. Vektor <math>B</math> wird mit <math>false</math> initialisiert, was so viel bedeutet, wie das das betrachtete Element beim Durchlaufen des Vektors noch nicht vorkam. Für jedes Element wird <math>true</math> in <math>B[A[i]]</math> vermerkt, wenn der vorherige Wert <math>false</math> war. Ist der ursprüngliche Wert jedoch <math>true</math>, so ist klar, dass der betrachtete Wert schon vorhanden ist, d.h. eine Dublette wurde gefunden.

Die Bestimmung des Maximums der in der Liste zusammengefassten Zufallszahlen kann bei der Listenbildung erledigt werden und wird deshalb aufwandsmäßig nicht zusätzlich veranschlagt.

<run id="4ba12503dc1ea">
(let* ((n 20)(a-list (zliste (+ n 1) 300))(a (list->vector a-list))
       (b (make-vector (+ 1 (apply max a-list)) #f))(escape #f)(vergleiche 0))
  (display a)(newline)
  (do ((i 1 (+ i 1)))
    ((or escape (= i n)) vergleiche)
    (set! vergleiche (+ vergleiche 1))
    (if (vector-ref b (vector-ref a i))
        (begin 
          (set! escape #t)
          (display (vector-ref a i))(newline))
        (vector-set! b (vector-ref a i) #t))))
</run>

Es finden maximal <math>n-1</math>, bei <math>n=20</math> also <math>19</math> Vergleiche statt.

==Polynomialer vs. exponentieller Aufwand==

Polynomialer Aufwand:
<math>T(n)=a_r n^r + a_{r-1} n^{r-1} + \ldots + a_1 n^1 + a_0~</math>,
<math>\mbox{mit } r\in\mathbb{N}_0,~a_r,\ldots, a_0\in\mathbb{R}_0^+,~a_r\neq 0.</math>

Hierzu zählen auch die Aufwandsfunktionen, die sich mit Logarithmen der folgenden Form beschreiben lassen. Man spricht von ''quasipolynomialen'' Aufwänden.
<math>T(n)=a\cdot\log_c n</math>

Exponentieller Aufwand:
<math>T(n)=c\cdot z^n</math>, wobei <math>z,~c\in\mathbb{R},~c\neq0\mbox{ und } z>1</math>.

Auch die Fakultätsfunktion beschreibt einen exponentiellen Zusammenhang, wie die Stirlingsche Formel zeigt:
<math>n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n</math>.

Aufgrund des gegebenen Definitionsbereiches bestehen die Graphen der Funktionen eigentlich aus Punkten. Zur besseren Visualisierung werden sie jedoch als geschlossene Linienzüge dargestellt.


==Vergleich verschiedener polynomialer und pseudopolynomialer Aufwände==

<gnuplot>
plot [n=0:5] sqrt(n), log(n), n*log(n), n
</gnuplot>

==Asymptotische Aufwandsordnungen==

Kleine Zeitaufwände zu vergleichen ist nicht sinnvoll. Schon Computer geringer Leistungsfähigkeit rechnen in diesem Bereich sehr schnell. Dem gegenüber kann es für große und sehr große Werte für $n$ dazu kommen, dass auch für sehr leistungsstarke Prozessoren unakzeptable Rechenzeiten beansprucht werden.

Dabei ist es im Allg. nicht von Interesse, welche Koeffizienten in dem konkreten Funktionsausdruck für $T$ vorkommen. 

Insbesondere haben zwei Funktionen $f,t:\mathbb{N}\mapsto\mathbb{R}_0^+$ die gleichen Wachstumsraten, wenn es zwei positive reelle Konstanten $c$ und $d$ gibt, so dass für alle hinreichend großen $n$ gilt $c\leq\frac{f(n)}{t(n)}\leq d$, d.h. wenn $f$ schneller wächst als $t$ und für alle positiven reellen Konstanten $c$ gilt $f(n)\geq c\cdot t(n)$.

Für die mathematische Beschreibung dieses Sachverhalts wird die "Groß-O"-Notation verwendet:
\begin{eqnarray*}
% \nonumber to remove numbering (before each equation)
  O(f) &=& \{t:\mathbb{N}\mapsto\mathbb{R}_0^+$\mid \exists c\in\mathbb{R}^+$ \exists n_0\in\mathbb{N}\forall n\geq n_0\qquad t(n)\leq c\cdot f(n)\} \\
  \Omega(f) &=& \{t:\mathbb{N}\mapsto\mathbb{R}_0^+$\mid \exists c\in\mathbb{R}^+$ \exists n_0\in\mathbb{N}\forall n\geq n_0\qquad t(n)\geq c\cdot f(n)\}
\end{eqnarray*}