Grundlagen der funktionsorientierten Programmierung mit SCHEME/Sequenzielle Suche
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
<code id="4bd4971f736f1" hidden>
;-- M. Hielscher / Chr. Wagenknecht --
(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)) 19880214))))
(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))))))))
(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)
(define random (random-maker (time-nanosecond (current-time))))
</code>
== Zufallszahlen ==
Wir erzeugen zunächst einzelne Zufallszahlen.
<eval id="4ba16a4491d20">
(random 100)
</run>
Dabei stellen wir fest: <tt>(random <max>)</tt> gibt eine Zufallszahl <math>z</math> zurück mit <math>0 \le z < max</math>.<br />
Das Würfeln einer Augenzahl <math>z</math> mit <math>1 \le z \le 6</math> lässt sich demzufolge mit dem nachfolgenden Prozeduraufruf simulieren:
<eval id="4ba16a4492cc0">
(+ 1 (random 6))
</run>
== Zufallslisten ==
Nun können wir Listen mit Zufallszahlen generieren, deren Elemente im Intervall <math>1 \le z \le max</math> liegen sollen. Vervollständigen Sie dazu die Prozedur <tt>zufallsliste</tt>.
<code id="4bb865f71aaf3">
(define zufallszahl
(lambda (max)
(+ 1 (random max))))
(define zufallsliste
(lambda (max anzahl)
...))
</code>
<eval id="4ba16a4493c5f">
(zufallsliste 100 20)
</run>
== Elementsuche ==
Schreiben Sie nun die Prozedur <tt>suche</tt>, die nach einem Element in einer unverschachtelten Liste suchen soll.<br />
Ist das Element in dieser Liste enthalten, soll seine Position in der Liste zurückgegeben werden. Anderenfalls ist der Rückgabewert <tt>#f</tt>:
> (suche 3 '(7 5 4 3 2 1 3 4 5))
4
> (suche 3 '(6 5 4 5))
#f
<code id="4ba16a4490d81">
(define suche
(lambda (el ls)
...))
</code>
<check>
(and (= (suche 3 '(7 5 4 3 2 1 3 4 5)) 4) (= (suche 3 '(7 5 4 2 1 9 4 5 3)) 9) (not (suche 3 '(6 5 4 5))))
</check>
Testen Sie die Prozedur <tt>suche</tt> mit Zufallszahlenlisten.
<eval id="4bb865f71c9ee">
(suche 57 (zufallsliste 100 100))
</run>
In diesem Suchverfahren werden alle Listenelemente solange nacheinander untersucht, bis eine Übereinstimmung festgestellt wird.<br />
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.<br />
Wir wollen uns im Weiteren auf den ''Zeitaufwand'' der sequenziellen Suche konzentrieren.<br />
Dazu nehmen wir vereinfacht an, dass jeder Vergleich der Elemente genau einem "Zeittakt" entspricht.
Die Prozedur <tt>suche</tt> liefert also den erforderlichen Zeitaufwand, wenn beim Rückgabewert <tt>#f</tt> die Länge der übergebenen Liste benutzt wird.<br />
=== Empirische Effizienzuntersuchungen ===
Wie viele Vergleiche sind im Mittel in einem vorgegebenen Intervall (Problemgröße) notwendig?<br />
Dazu definieren wir die Prozedur <tt>suche-mehrfach</tt>, die die Suche von Zufallszahlen <math>z</math> mit <math>1 \le z \le max</math> im Intervall <math>[1 ; max]</math> mehrfach durchführt und den Mittelwert aller erforderlichen Vergleiche zurückgibt:
<code id="4bb8baf1df5be">
(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)))))
</code>
<eval id="4bb865f71d98c">
(suche-mehrfach 100 10)
</run>
=== Experimente ===
Wir erweitern nun die sequenzielle Suche auf mehrere Intervalle und automatisieren diesen Prozess:
<code id="4bb8baf1e0564">
(define experiment
(lambda (min max schrittweite anzahl)
(if (> min max)
()
(append (experiment min (- max schrittweite) schrittweite anzahl)
(list (suche-mehrfach max anzahl))))))
</code>
<eval id="4bb8baf1e2491">
(experiment 100 1000 100 10)
</run>
Nun sollen unsere Untersuchungsergebnisse für eine größere Anzahl von Intervallen in einem Balkendigramm visualisiert werden.<br />
Dazu benutzen wir das vom [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Projekt Zahlenfolgen|Projekt Zahlenfolgen]] bekannte Balkendiagramm. Die Syntax der Prozedur <tt>balkendiagramm</tt> vereinfacht sich erwartungsgemäß bei der Anwendung auf Listen:
(balkendiagramm <ls>) ;<ls> ... Liste mit Zahlenwerten
'''Achtung!''' Beim Experimentieren ist etwas Geduld erforderlich!<br />
<canvas w="400" h="300"></canvas>
<code id="4be134c406acb" hidden>
(define rand 50)
(define maxbreite (- 400 (* 2 rand)))
(define maxhoehe (- 300 (* 2 rand)))
(define minmax
(lambda (ls)
(letrec
([extremsuche
(lambda (extrem ls op)
(cond
[(null? ls) extrem]
[(op extrem (car ls)) (extremsuche (car ls) (cdr ls) op)]
[else
(extremsuche extrem (cdr ls) op)]))])
(cons (extremsuche 0 ls >)
(extremsuche 0 ls <)))))
(define balken
(lambda (hoehe breite)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite) (left turtle 90)
(forward turtle hoehe) (left turtle 90)
(forward turtle breite)))
(define balkendiagramm
(lambda (ls)
(let* ([breite (/ maxbreite (length ls))]
[extremwerte (minmax ls)]
[min (car extremwerte)] [max (cdr extremwerte)])
(letrec
([zeichnen
(lambda (min max ls)
(if (null? ls)
'ok
(begin
(balken (* (/ (car ls) (- max min)) maxhoehe) breite)
(zeichnen min max (cdr ls)))))])
(clear canvas)
(hide turtle)
(move turtle rand (+ rand (* (/ max (- max min)) maxhoehe))) (right turtle 90)
(zeichnen min max ls)))))
</code>
<eval id="4bb8c084a31bd">
(balkendiagramm (experiment 200 10000 200 100))
</run>
'''Ergebnis:''' Offensichtlich wächst der Zeitaufwand bei der sequenziellen Suche ''linear'' mit der Problemgröße.
== Aufgaben ==
<ol>
<li>
Ermitteln Sie den Proportionalitätsfaktor in der vermuteten linearen Abhängigkeit
<math>\mbox{Zeitaufwand} = f(\mbox{Problemgr\"o\ss e)}</math>.<br />
Nutzen Sie dazu die lineare Regression der Tabellenkalkulation oder des grafikfähigen Taschenrechners.
</li>
<li>
Die Grenzwertsuche im [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Projekt Zahlenfolgen|Projekt Zahlenfolgen]] ist eine typische Anwendung der sequenziellen Suche.<br />
Nennen Sie weitere Beispiele für die sequenzielle Suche aus der angewandten Informatik.<br />
Verallgemeinern Sie diese Beispiele zu einer Problemklasse, auf die eine sequenzielle Suche anzuwenden ist.
</li>
</ol>