Sequenzielle Suche

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2010-10-01T21:31:51+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Zufallszahlen
2 Zufallslisten
3 Elementsuche
4 Effizienz der sequenziellen Suche
- 4.1 Empirische Effizienzuntersuchungen
- 4.2 Experimente
5 Aufgaben

Zufallszahlen

Wir erzeugen zunächst einzelne Zufallszahlen.

<eval id="4ba16a4491d20"> (random 100) </eval>

Dabei stellen wir fest: (random <max>) gibt eine Zufallszahl z zurück mit 0 \le z < max.
Das Würfeln einer Augenzahl z mit 1 \le z \le 6 lässt sich demzufolge mit dem nachfolgenden Prozeduraufruf simulieren:

<eval id="4ba16a4492cc0"> (+ 1 (random 6)) </eval>

Zufallslisten

Nun können wir Listen mit Zufallszahlen generieren, deren Elemente im Intervall 1 \le z \le max liegen sollen. Vervollständigen Sie dazu die Prozedur zufallsliste.

(define zufallszahl
  (lambda (max)
    (+ 1 (random max))))

(define zufallsliste
  (lambda (max anzahl)
    ...))

<eval id="4ba16a4493c5f"> (zufallsliste 100 20) </eval>

Elementsuche

Schreiben Sie nun die Prozedur suche, die nach einem Element in einer unverschachtelten Liste suchen soll.
Ist das Element in dieser Liste enthalten, soll seine Position in der Liste zurückgegeben werden. Anderenfalls ist der Rückgabewert #f:

> (suche 3 '(7 5 4 3 2 1 3 4 5))
4
> (suche 3 '(6 5 4 5))
#f

(define suche
  (lambda (el ls)
    ...))

Testen Sie die Prozedur suche mit Zufallszahlenlisten.

<eval id="4bb865f71c9ee"> (suche 57 (zufallsliste 100 100)) </eval>

In diesem Suchverfahren werden alle Listenelemente solange nacheinander untersucht, bis eine Übereinstimmung festgestellt wird.
Wir bezeichnen diesen Suchalgorithmus als lineare oder sequenzielle Suche.

Effizienz der sequenziellen Suche

Ein Algorithmus ist effizient, wenn er mit möglichst geringem Ressourcenaufwand (Zeit, Speicherbedarf) ein vorgegebenes Problem löst.
Wir wollen uns im Weiteren auf den Zeitaufwand der sequenziellen Suche konzentrieren.
Dazu nehmen wir vereinfacht an, dass jeder Vergleich der Elemente genau einem "Zeittakt" entspricht. Die Prozedur suche liefert also den erforderlichen Zeitaufwand, wenn beim Rückgabewert #f die Länge der übergebenen Liste benutzt wird.

Empirische Effizienzuntersuchungen

Wie viele Vergleiche sind im Mittel in einem vorgegebenen Intervall (Problemgröße) notwendig?
Dazu definieren wir die Prozedur suche-mehrfach, die die Suche von Zufallszahlen z mit 1 \le z \le max im Intervall [1 ; max] mehrfach durchführt und den Mittelwert aller erforderlichen Vergleiche zurückgibt:

(define suche-mehrfach
  (lambda (max anzahl)
    (letrec
        ([summe
          (lambda (ls n)
            (let* ([el (zufallszahl max)] [pos (suche el ls)])
              (cond
                [(= n 0) 0]
                [(not pos) (+ (length ls) (summe ls (- n 1)))]
                [else
                 (+ pos (summe ls (- n 1)))])))])
      (exact->inexact (/ (summe (zufallsliste max max) anzahl) anzahl)))))

<eval id="4bb865f71d98c"> (suche-mehrfach 100 10) </eval>

Experimente

Wir erweitern nun die sequenzielle Suche auf mehrere Intervalle und automatisieren diesen Prozess:

(define experiment
  (lambda (min max schrittweite anzahl)
    (if (> min max)
        ()
        (append (experiment min (- max schrittweite) schrittweite anzahl)
                (list (suche-mehrfach max anzahl))))))

<eval id="4bb8baf1e2491"> (experiment 100 1000 100 10) </eval>

Nun sollen unsere Untersuchungsergebnisse für eine größere Anzahl von Intervallen in einem Balkendigramm visualisiert werden.
Dazu benutzen wir das vom Projekt Zahlenfolgen bekannte Balkendiagramm. Die Syntax der Prozedur balkendiagramm vereinfacht sich erwartungsgemäß bei der Anwendung auf Listen:

(balkendiagramm <ls>) ;<ls> ... Liste mit Zahlenwerten</ls></ls>

Achtung! Beim Experimentieren ist etwas Geduld erforderlich!

<eval id="4bb8c084a31bd"> (balkendiagramm (experiment 200 10000 200 100)) </eval>

Ergebnis: Offensichtlich wächst der Zeitaufwand bei der sequenziellen Suche linear mit der Problemgröße.

Aufgaben

Ermitteln Sie den Proportionalitätsfaktor in der vermuteten linearen Abhängigkeit \mbox{Zeitaufwand} = f(\mbox{Problemgr\"o\ss e)}.
Nutzen Sie dazu die lineare Regression der Tabellenkalkulation oder des grafikfähigen Taschenrechners.
Die Grenzwertsuche im Projekt Zahlenfolgen ist eine typische Anwendung der sequenziellen Suche.
Nennen Sie weitere Beispiele für die sequenzielle Suche aus der angewandten Informatik.
Verallgemeinern Sie diese Beispiele zu einer Problemklasse, auf die eine sequenzielle Suche anzuwenden ist.