Teile und Herrsche 2 WS13-14

Aus ProgrammingWiki

Archivierte Version vom 2013-10-26T10:13:46+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Binäres Suchen

Autoren:

Binäres Suchen

Wann immer ein Gegenstand oder eine Information gesucht werden muss, gibt es verschiedene Herangehensweisen. Um einen Eintrag im Duden oder eine Abfahrtszeit im Bahnfahrplan zu finden, kann durch einen Vergleich der vorangehenden oder nachfolgenden Einträge bereits nach einem Ausschlussverfahren vorgegangen werden. Hierbei handelt es sich allerdings schon um "sortierte Listen". Sucht man dagegen etwas in einer "unsortierten Liste", wie etwa eine Schraube in einer "Restekiste" mit diversen Schrauben, prüft man elementeweise, ob das gesuchte Element (die Schraube) in der Liste (die Schraubenrestekiste) vorhanden ist. Ist im ungünstigsten Fall die gesuchte Schraube das letzte Element, ist der Aufwand \mathcal{O}(n). Entsprechend hat die Suche einen linearen Aufwand und ist für besonders große Listen (Nadel im Heuhaufen) nicht zu empfehlen. Implementiert in Scheme würde eine solche Suche folgendermaßen aussehen:

(define lineareUnsortierteSuche
  (lambda (element liste)
    (cond
      ((null? liste) "Element ist nicht in der Liste enthalten")
      ((= element (car liste)) "Das Element ist in der Liste enthalten")
      (else
       (lineareUnsortierteSuche element (cdr liste))))))

(lineareUnsortierteSuche 21 '(89 5 2 55 13 1 143 3 21 34 8 232))

Die Nachteile dieses Suchalgorithmus liegen auf der Hand:

Mit wachsender zahl der Elemente steigt der Aufwand linear
Ist das Element nicht enthalten, wird in jedem Fall die Liste komplett durchsucht

In einer aufsteigend sortierten Liste erlaubt eine kleine Modifikation des Algorithmus den Abbruch der Suche, falls das Element nicht in der Liste vorhanden ist:

(define lineareSortierteSuche
  (lambda (element liste)
    (cond
      ((null? liste) "Element ist nicht in der Liste enthalten")
      ((< element (car liste)) "Element ist nicht in der Liste enthalten")
      ((= element (car liste)) "Das Element ist in der Liste enthalten")
      (else
       (lineareSortierteSuche element (cdr liste))))))

(lineareSortierteSuche 13 '(1 2 3 5 8 13 21 34 55 89 143 232))

Nach wie vor zeigt der Worst case (Das gesuchte Element ist immer das Letzte oder nicht vorhanden), dass hier ein linearer Aufwand vorliegt.

Um also einen geringeren Aufwand zu erreichen, soll bei der Suche nun systematisch vorgegangen werden. In dem Beispiel mit der Suche eines Wortes im Duden wird der Duden mittig aufgeschlagen und anschließend je nach Anfangsbuchstaben des gesuchten Wortes der Vordere oder hintere Teil des Dudens erneut halbiert bis die Zielseite gefunden ist. Der Suchraum wird auf diese Weise immer halbiert und die Zielseite wird deutlich schneller gefunden.

Für die binäre Suche reduzieren wir das Suchproblem auf eine Liste mit n Elementen aus dem Zahlenbereich der ganzen Zahlen \mathcal{\mathbb{Z}}:

\mathcal{L=\{e_{1}, e_{2}, \dots ,e_{n}\}}

mit \mathcal{e\in\mathbb{Z}}

und \mathcal{n\in\mathbb{N}}

Zuerst muss die Liste in zwei Teillisten geteilt werden. Bei einer ungeraden Anzahl von Listenelementen wird abgerundet (floor).

\mathcal{k=\lfloor\frac{n}{2}\rfloor}

mit \mathcal{k} als mittlestem Listenelement der Liste \mathcal{L}

Anschließend gibt es eine linke und eine rechte Teilliste:

\mathcal{L_{l}=\{e_{1}, e_{2}, \dots , e_{k}\}}

\mathcal{L_{r}=\{e_{k+1}, e_{k+2}, \dots , e_{n}\}}

Ist \mathcal{x} das gesuchte Element, wird \mathcal{x} mit dem ersten Element der rechten Teilliste verglichen \mathcal{x < e_{k+1}}. Das Ergebnis entscheidet darüber, ob mit der rechten oder linken Teilliste fortgefahren wird. Die neue Teilliste wird so lange rekursiv verarbeitet, bis \mathcal{x} gefunden wurde oder alle Teillisten untersucht wurden. Bestenfalls ist das erste Element \mathcal{e_{k+1}} der Teilliste \mathcal{L_{r}} bereits das gesuchte Element \mathcal{x}.

Die rekursive Bildungsvorschrift zur binären Suche kann folgendermaßen angegeben werden:

\mathcal{ \mathit{BiSu} = \begin{cases} {\mathit{BiSu}}\left(L_{1}\right), \ \mbox{$wenn$}\ x < e_{k+1} \\ \mathit{BiSu}\left(L_{r}\right), \ \mbox{$wenn$}\ x > e_{k} \\ \mathit{print}\left(e_{k}\right), \ \mbox{$wenn$}\ k = e_{k} \\ \mathit{nicht\ Enthalten}, \ \mbox{$wenn$}\ k < 0\ \mbox{$oder$}\ k > n \\ \mathit{nicht\ Enthalten}, \ \mbox{$sonst$}\end{cases} }

Mit der binären Suche ist es möglich, in einem Duden mit 140.000 Stichwörtern und 1216 Seiten mit höchstens \mathcal{17} (\mathcal{\approx \log_2 140000}) Wortvergleichenvergleichen jedes Wort zu finden.

Das Verfahren

Nicht nur bei der Suche von Schrauben in einer Kiste, sondernauch für die Suche von Informationen (z.B. Duden, Telefonbuch, Bahnfahrplan) ist eine effiziente Suche sehr vorteilhaft, da durch ineffiziente Verfahren sehr viele Ressourcen unnötig gebunden werden können.

In einer aufsteigend sortierten Gesamtliste

\mathcal{G = \left( a_1,a_2,\dots, a_k, a_{k+1},\dots,a_n \right)}

erfolgt die Suche von \mathcal{x} durch die Suche in den beiden Teillisten \mathcal{L = \left( a_1,a_2,\dots, a_k \right)} und \mathcal{R = \left(a_{k+1}, a_{k+2},\dots, a_n \right)}. Ausgehend von \mathcal{n} als Zweierpotenz erfolgt die Zerlegung mit \mathcal{k = n\div2}. In der Implementierung wird \mathcal{k = \lfloor \frac{n}{2} \rfloor} verwendet.

Im Suchvorgang wird \mathcal{x} stets mit dem ersten Element \mathcal{a_{k+1}} aus der rechten Teilliste \mathcal{R} verglichen. Stimmt \mathcal{x} mit \mathcal{a_{k+1}} überein, ist das Ergebnis der Suche \mathcal{a_{k+1}}. Andernfalls wird bei \mathcal{x<a_{k+1}} die Suche in der linken Teilliste \mathcal{L }, bzw. bei \mathcal{x> a_{k+1} } in der rechten Teilliste \mathcal{R} unter der Voraussetzung, dass die zu durchsuchende Teilliste nicht leer ist, fortgesetzt.

Scheme-Implementierung

Um eine Implementierung in Scheme zu realisieren, benötigen wir die bereits im Kapitel über mergesort thematisierte Funktion "teillisten2".

Scheme-Implementierung der binären Suche:

(define binSuche
  (lambda (element liste)
    (call-with-values
     (lambda () (teillisten2 liste))
     (lambda (lls rls)
       (cond
         ((null? rls) "Element ist nicht in der Liste enthalten")
         ((= element (car rls)) "Element ist in der Liste enthalten")
         ((< element (car rls))
             (binSuche element lls))
         (else
          (if (null? (cdr rls))
              "Element ist nicht in der Liste enthalten"
              (binSuche element rls))))))))

Zur Demonstration der Korrekten Arbeitsweise des Algorithmus ist hier eine Liste explizit angegeben. Es können auch Prozeduren verwendet werden, die eine Liste mit Zufallszahlen ausgeben.

(binSuche 34 '(1 2 3 5 8 13 21 34 55 89 143 232))

Um nicht nur zu erfahren, dass das gesuchte Element gefunden wurde, sondern zusätzlich dessen Position ausgegeben zu bekommen, muss der Algorithmus erneut angepasst werden. Auch die Anzahl der Rekursionsschritte ist für eine Aufwandsanalyse sehr aussagekräftig, weshalb auch diese berücksichtigt wird. Zuerst müssen daher Zähler für die Aufrufe und Rekursionsschritte definiert und in den vorhandenen Code integriert werden.

(define aufrufe 0)

(define rekursionsschritte 0)

(define binSuche2
  (lambda (element liste)
    (call-with-values
     (lambda () (teillisten2 liste))
     (lambda (lls rls)
       (cond
         ((null? rls) "Nicht gefunden!")
         ((= element (car rls)) 
          (and (and (set! rekursionsschritte (+ rekursionsschritte (length lls)))
                    (and (string-append "Gefunden - [Stelle: "
                                        (number->string rekursionsschritte) "] - [rekursive Aufrufe: "
                                        (number->string aufrufe) "]")))))
         ((< element (car rls))
          (if (null? lls)
              "Nicht gefunden"
              (and (set! aufrufe (+ aufrufe 1))
                   (binSuche2 element lls))))
         (else
          (if (null? (cdr rls))
              (string-append "Nicht gefunden. [Rekursionen: " 
                             (number->string aufrufe) "]")
              (and (set! aufrufe (+ aufrufe 1))
                   (and 
                    (set! rekursionsschritte (+ rekursionsschritte (length lls)))
                    (binSuche2 element rls))))))))))

Eine weitere Prozedur wird zum Aufruf der binären Suche verwendet:

(define binSucheAufruf
  (lambda (element liste)
    (set! aufrufe 0)
    (set! rekursionsschritte 0)
    (binSuche2 element liste)))

Ein Aufruf unserer neuen binären Suche ergibt dann das gewünschte Ergebnis.

(binSucheAufruf 55 '(1 2 3 5 8 13 21 34 55 89 143 232))

Vergleich sequenzielle und binäre Suche

Da im vorangegangenen Teilabschnitt die Grundlage für eine empirische Analyse der binären Suche geschaffen wurde, soll das hier nun auch für die sequentielle Suche getan werden. So wird die Möglischkeit geschaffen, die Aufwände der beiden Suchen zu vergleichen.

Zu implementieren ist eine Variable für die Anzahl der Aufrufe, die als Index verwendet werden kann:

(define sortierteSequenzielleSuche
  (lambda (element liste)
    (cond
      ((null? liste) "Das gesuchte Element ist nicht in der Liste enthalten")
      ((< element (car liste)) "Das gesuchte Element ist nicht in der Liste enthalten")
      ((= element (car liste)) 
       (string-append "Das gesuchte Element ist in der Liste enthalten und befindet sich an der Position "
                      (number->string aufrufe) "."))
      (else       
       (set! aufrufe (+ aufrufe 1))
       (sortierteSequenzielleSuche element (cdr liste))))))

Es wird eine Prozedur benötigt, die die Variable "aufrufe" zurücksetzt:

(define sortierteSequenzielleSuche2
  (lambda (element liste)
    (set! aufrufe 0)
    (sortierteSequenzielleSuche element liste)))

Nun funktioniert folgender Aufruf:

(sortierteSequenzielleSuche2 89 '(1 2 3 5 8 13 21 34 55 89 144 233))

Effizienzanalyse binäre Suche

Die Länge der Teillisten wird schrittweise halbiert. Besonders gut funktioniert das, wenn die Anzahl \mathcal{n} der Elemente von \mathcal{G} eine Zweierpotenz ist. Die Anzahl der rekursiven Aufrufe entspricht der Anzahl der Halbierungsschritte, also \mathcal{log_2\ n} Stück. Wird für den in jedem Schritt stattfindenden Vergleich ein konstanter Aufwand \mathcal{\mathcal{O}\left( c \right)} angenommen, beträgt der Gesamtaufwand

\mathcal{T\left(n\right) = \mathcal{O}\left(log_2 \ n\right)}.

Dies trifft für den average sowie für den worst case zu. Der best case benötigt dagegen nur einen einzigen Vergleich und arbeitet mit konstantem Aufwand

\mathcal{T\left(n\right) = \mathcal{O}\left(c\right)}

unabhängig von der Anzahl \mathcal{n}.

Vergleich zur sequenziellen Suche

Es ist nur schwer zu erkennen, dass die Binärsuche effizienter sein soll, als die sequenzielle Suche von \mathcal{x} in einer aufsteigend sortierten Liste \mathcal{G}.

Bei der sequenziellen Suche vergleicht man \mathcal{x} mit den aus \mathcal{G} stammenden Elementen, beginnend beim Kleinsten. Dies wird so lange durchgeführt, bis \mathcal{x} gefunden wurde. Würde man den Fall \mathcal{x \notin G} miteinbeziehen, so könnte die Suche im Fall, dass das erste Element \mathcal{a_{i}} größer ist als \mathcal{x}, (erfolglos) beendet werden.

Wir gehen dabei wieder von paarweise verschiedenen Listenelementen aus:

(define seq-suche
  (lambda (element liste)
    (cond
      ((null? liste) "Element ist nicht in der Liste enthalten")
      ((= element (car liste)) "Element ist in der Liste enthalten")
      ((< (car liste) element )(seq-suche element (cdr liste)))
      (else "Element ist in der Liste enthalten"))))

(seq-suche 5 '(1 2 3 4 5 6 7 8 9 0))

Für den Best Case, \mathcal{x = a_{1}} gilt \mathcal{T(n) = O(1)}. Im Worst- sowie im Average-Case werden \mathcal{n} Durchläufe nötig, womit \mathcal{T(n) = O(n)} gilt. Sollte jedes Element aus \mathcal{G} mit gleicher Wahrscheinlichkeit mit \mathcal{x} übereinstimmen, so könnte man den Aufwand wie folgt beschreiben:

$\mathcal{\begin{array} {ccl}

T(n) = \frac {1} {n} \cdot \sum\limits_{i=1}^{n} i = \frac {n} {2n} (n+1) = \mathcal{O}(n) \end{array}}$

Damit wird deutlich, weshalb der sequenziellen Suche die Binärsuche vorzuziehen ist.

Best Case

Im besten Fall kommen beide Suchalgorithmen im ersten Schritt zum Ergebnis. Dabei ist das gesuchte Element bei der sequentiellen Suche das erste Listenelement und bei der binären Suche das erste Element der rechten Teilliste. Beide Suchen erreichen somit einen konstanten Aufwand \mathcal{T(n)=\mathcal{O}(c)}, der unabhängig von n ist.

Average- und Worst-Case

Die sequentielle Suche benötigt im schlechtesten Fall \mathcal{n} Durchläufe, d.h. \mathcal{T(n)=\mathcal{O}(c)}. Im mittleren Fall gilt das genauso. Geht man jetzt davon aus, das alle Listenelemente mit \mathcal{x} mit gleicher Wahrscheinlichkeit übereinstimmen, ist der Aufwand der sequentiellen Suche \mathcal{T(n)=\frac{1}{n}\sum_{i=1}^{n}i=\frac{n}{2n}(n+1)=\mathcal{O}(n)}

Bei der binären Suche ist aufgrund der Arbeitsweise des Algorithmus erkennbar, dass sich die Länge der Teillisten in jedem Schritt halbiert, besonders dann, wenn die Anzahl der Listenelemente gerade ist. In diesem Fall stimmt die Anzahl der rekursiven Aufrufe mit der Anzahl der Halbierungen überein, also genau \mathcal{\log_2 n}. Für die Vergleichoperationen in den einzelnen Zwischenschritten wird ein konstanter Aufwand \mathcal{\mathcal{O}(c)} angenommen. Dadurch ergibt sich für die binäre Suche im mittleren und schlechtesten Fall ein Gesamtaufwand von \mathcal{T(n)=\mathcal{O}(\log_2 n)}

Fazit

In der Praxis kann nie vom Best Case ausgegangen werden, weshalb bei der Betrachtung der Algorithmen diese Fälle unbeachtet bleiben. Da der Aufwand der sequentiellen Suche linear- und der Aufwand der binären Suche logarithmisch ist, ist die binäre Suche der sequentiellen Suche vorzuziehen.

Folgende Gegenüberstellung soll verdeutlichen, weshalb vor allem bei großen \mathcal{n} der Aufwand der binären Suche wesentlich geringer ist:

\begin{array}{|c|l r|r|r|r|r|} \hline f(n) & n= & 32 & 256 & 8192 & 2097152 & 17179869184\\ \hline\\ log_2 n & & 5 & 8 & 13 & 21 & 34\\ \hline\\ n & & 32 & 256& 8192 & 2097152 & 17179869184\\ \hline \end{array}