Beispiel: Lineare und binäre Suche


[Seminar "Einführung in Haskell"] - [Inhalt] - [zurück] - [weiter]

Übersicht:


Lineare Suche:

Die Funktion - bekommt eine unbeschränkt-genaue (arbitrary) Realzahl und liefert einen Integer zurück. Sie ist primitiver als div, kann aber nicht in Haskell implementiert werden, weil dieses nur beschränkt-genaue Realzahlen darstellen kann. Nichtsdestotrotz ist es lehrreich zu sehen, wie floor :: Float -> Integer programmiert werden kann. Das Problem ist nicht so trivial, wie es scheint, daher wird das Programm systematisch entwickelt. Es werden zwei Programme entwickelt werden, von denen eins wesentlich effizienter ist als das andere. Die Strategien hinter diesen Programmen heissen lineare und binäre Suche. Der Abschnitt endet mit einer zweiten Anwendung zur Berechnung von Wurzeln.
Zunächst die Spezifikation:

 
       floor       ::   Float -> Integer
       floor x = n ≡ n ≤ x < n + 1

Während man darüber nachdenkt, welche Gestalt das Programm für floor annehmen wird, ist es verführerisch, sofort mit einer Fallanalyse zu beginnen. Es wird überlegt was zu tun ist, wenn x positiv, negativ oder möglicherweise 0 ist. Aber die Spezifikation erwähnt keine Fälle und es wird auch keine Fallanalyse verwendet. Programme, die Fallanalysen vermeiden, sind klarer und einfacher.
Gesucht wird n und die Spezifikation suggeriert mindestens einen Weg, um die Suche durchzuführen: Gesucht wird ein n, für das gilt n ≤ x und das so lange erhöht wird, bis die Bedingung x < n + 1 ebenfalls erfüllt ist. Es kann natürlich auch ein n gesucht werden, das die Bedingung x < n + 1 erfüllt, um dann n so lange zu verkleinern, bis die Bedingung n ≤ x auch gilt. Der Gedanke, so lange zu suchen, bis eine Bedingung erfüllt wird, kann in einer Funktion until gekapselt werden:

 
       until       ::   (α -> Bool) -> (α -> α) -> α -> α
       until p f x = if p x then x else until p f (f x)

Die Suche nach einem n, das die Bedingung n ≤ x erfüllt und wo x eine fixe Zahl ist, kann mit einem beliebigen Integer beginnen, der dann so lange dekrementiert wird, bis die Bedingung erfüllt ist. Z.B. die Suche:

 
       lower    ::   Integer -> Integer
       lower    =    until (≤ x) decrease, where decrease n = n - 1

löst die Aufgabe, wenn sie auf einen beliebigen Startwert angewendet wird. Die Suche wird terminieren, weil für jedes Real x ein Integer n existiert, für das gilt n ≤ x. Der in der ersten Suche gefundene Integer n kann erheblich zu klein sein, so dass in einer zweiten Suche n solange erhöht werden muss, bis die Bedingung x < n + 1 erfüllt ist. n muss in Schritten von 1 erhöht werden, um die Bedingung n ≤ x zu behalten. Die zweite Suche kann auf zwei Arten beschrieben werden. Entweder als

 
       until (> (x - 1)) increase where increase n = n + 1

oder als decrease · upper

 
       upper  =  until (> x) increase where increase n = n + 1 

In der zweiten Lösung ist upper das Gegenteil zu lower. Die Funktion decrease · upper wird auf das Ergebnis der ersten Suche angewendet. Das komplette Programm sieht wie folgt aus:

 
       floor       ::   Float -> Integer 
       floor x     =    searchFrom 0
                        where searchFrom  =  decrease · upper · lower
                              lower      =  until(≤ x) decrease
                              upper      =  until(> x) increase
                              decrease n = n - 1
                              increase n = n + 1

Es wurde versucht, dieses Programm so klar wie möglich darzustellen. Die Namen searchFrom, increase (anstelle des äquivalenten Succ) und decrease anstelle von pred wurden ausgewählt, um den Beitrag dieser Teile zur Definition zu verdeutlichen und die Funktionen lower und upper so gegensätzlich wie möglich darzustellen. Zuletzt wurden die unterschiedlichen Hilfsfunktionen lokal zur Hauptdefinition erstellt. Das Programm ist überraschend kurz, was hauptsächlich auf das Fehlen einer Fallanalyse bzgl. des Vorzeichens von x zurückzuführen ist. Man kann einfach sehen, wie beide Fälle behandelt werden: Wenn 0 ≤ x, dann terminiert die erste Schleife sofort, während die zweite die eigentliche Arbeit macht. Ist x < 0, ist es genau andersherum.


[nach oben]

Binäre Suche:

Das obige Programm ist nicht wirklich effizient, weil es ungefähr abs x Schritte braucht, um das Resultat zu finden. Ein effizienterer Weg ist es, zuerst zwei Integer m und n zu finden, sodass m ≤ x < n, um dann m und n näher zusammen zu bringen, sodass schliesslich die Bedingung m + 1 = n erfüllt ist. Das Entkoppeln der zwei Suchen ist deshalb vorteilhaft, weil grössere Schritte benutzt werden können. Genauer gesagt, ist beispielsweise das Suchpaar zu betrachten:

 
       lower  =  until(≤ x) double
       upper  =  until(> x) double

mit double n = 2 * n. Unter der Voraussetzung, dass lower auf eine negative Zahl angewendet wird und upper auf eine positive, ist garantiert, dass die zwei Suchen ein Paar (m,n) mit m ≤ x < n finden, wobei die Anzahl der Schritte proportional ist zu log2 (abs x). Beide Suchen müssen durch eine dritte Suche ergänzt werden, die das Paar (m,n) näher zusammenbringt, bis m + 1 = n gilt. Entweder wird m in Schritten von 1 inkrementiert oder andersrum n in Schritten von 1 dekrementiert. Eine bessere Lösung betrachtet den Integer p = (m + n) div 2 als Mittelwert zwischen m und n. Daraus folgt, wenn m + 1 < n, dann ist m < p < n. Ist p ≤ x, kann m auf den Wert von p erhöht werden. Ist x < p, kann n auf p verringert werden. Daraus ergibt sich folgendes Programm:

 
       floor x     =    searchFrom (-1,1)
                        where searchFrom  =  fst · middle · cross(lower, upper)
                              lower         =  until(≤ x) double
                              upper         =  until(> x) double
                              middle        =  until done improve
                              done(m, n)    =  (m + 1 = n)
                              improve(m, n) =  if p ≤ x then (p, n) else (m, p)
                                               where p = (m + n) div 2

Die Funktion cross wurde bereits definiert. Das neue Programm benötigt eine Anzahl von Schritten, die proportional ist zu log2 (abs x). Z.B. mit x = 17,3 ergibt sich lower (-1) = -1 und upper 1 = 32. Die dritte Suche erzeugt die Zwischenwerte:

 
       (-1,32) -> (15,32) -> (15,23) -> (15,19) -> (17,19) -> (17,18)

und gibt 17 zurück. Mit x = -17,3 ist lower (-1) = -32 und upper 1 = 1. Die dritte Suche erzeugt die Zwischenwerte:

 
       (-32,1) -> (-32,-16) -> (-24,-16) -> (-20,-16) -> (-18,-16) -> (-18,-17)

und gibt -18 zurück. Die Strategie hinter diesem Programm wird als binäre Suche bezeichnet. Anstatt zwei Integer in Schritten von 1 zusammen zu bringen, kann man den Abstand manchmal auf die Hälfte zusammenkürzen.


[nach oben]

Beispiel: Berechnung von Quadratwurzeln

In einem zweiten Beispiel für die Suche soll eine Definition für die Funktion sqrt erstellt werden, um die (nicht negative) Quadratwurzel einer nichtnegativen Zahl zu berechnen. Die mathematische Spezifikation von sqrt ist, das gilt:

 
       sqrt x ≥ 0   und   square(sqrt x) = x

wenn x ≥ 0. Diese Spezifikation ist streng, weil sie keine limited-precision für arithmetische Operationen auf aktuellen Computern zulässt. Sie verlangt beispielsweise, dass:

 
       sqrt 2 = 1.4142135623...

exakt berechnet wird. Wie in Kapitel 4 und 9 gezeigt werden wird, ist es durchaus möglich, eine Funktion zu entwerfen, die eine unendliche Liste von Ziffern zurück gibt, auch wenn der Prozess des Druckens dieser Liste niemals terminiert. Der Programmierer kann dann zeigen, dass sqrt seine Spezifikation erfüllt, indem er nachweist, dass die Liste von Ziffern bis zum verlangten Genauigkeitsgrad approximiert, wenn sie nur lange genug fortgeführt wird. Für dieses Beispiel jedoch wird die Spezifikation dahingehend abgeschwächt, dass srqt :: Float -> Float

 
       sqrt x ≥ 0   und   abs(square(sqrt x) - x < eps

erüllt für ein infinitisimal kleines eps > 0. Um die geänderte Spezifikation zu verdeutlichen, soll eps = 0.0001 und x = 2 sein. Gefordert ist:

 
       abs(square(sqrt 2) - 2) < 0.0001

und aus

 
       1.4141 * 1.4141 = 1.99967881
       1.4142 * 1.4142 = 1.99996164
       1.4143 * 1.4143 = 2.00024449

folgt, dass der Wert sqrt 2 = 1.4142 eine akzeptable Antwort darstellt.
Um sqrt zu konstruieren, wird das Newton´sche Näherungsverfahren zum Finden der Wurzeln einer gegebenen Funktion angewendet. Dabei handelt es sich um eine iterative Methode, die wiederholt die Approximation der Lösung verbessert, bis der geforderte Genauigkeitsgrad erreicht ist. Im Falle der Quadratwurzeln sagt Newtons Methode, dass wenn yn eine Näherung zur √ x, dann ist:

 
       yn+1 = (yn + x / yn) / 2

die bessere Näherung. In einem Beispiel mit x = 2 und y0 = x ist:

 
       y0                        =  2
       y1 =  (2 + 2/2)/2         = 1.5
       y2 =  (1.5 + 2/1.5)/2     = 1.4167
       y3 =  (1.4167 + 2/1.4167) = 1.4142157

Durch Iteration dieses Prozesses kann Wurzel 2 bis zu jedem beliebigen Genauigkeitsgrad berechnet werden, eingeschränkt nur durch die Begrenzungen der Computer-Arithmetik. Durch die Benutzung der bereits vorgestellten Funktion until kann sqrt mit folgendem Programm implementiert werden:

 
       sqrt   ::   Float -> Float
       sqrt x =    until done improve x
                   where done y     =   abs(y * y -x) < eps
                         improve y  =   (y + x/y)/2



[Seminar "Einführung in Haskell"] - [Inhalt] - [zurück] - [weiter] - [nach oben]