AuK/Effizienz von Algorithmen SS09

Wiki-Quelltext dieser Seite.

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

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

Diese Formulierung muss weiter präzisiert werden. Außerdem ist zu beachten, dass Zeit und Speicher ineinander "umwandelbar" sind, d.h. wenn man bei der Modellierung knappen Speicher wählt, kann es sein, dass der Algorithmus Zusatzaufwand betreiben muss, da gewisse Daten zwischengerechnet werden müssen und eben nicht direkt zur Verfügung stehen.

===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>
<eval id="4ba10f230009b">(zliste 30 100)</eval>

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.

<eval 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)) 'stoppp)
    (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)))))))
</eval>

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.