Teile und Herrsche 2 WS13-14

Aus ProgrammingWiki

< AuK
Wechseln zu: Navigation, Suche

Loading
Autoren:


Inhaltsverzeichnis

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:

Die Nachteile dieses Suchalgorithmus liegen auf der Hand:

  • Mit wachsender Anzahl 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:

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 in einer aufsteigend sortierten Liste 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 $\mathbb{Z}$:

$L=(e_{1}, e_{2}, \dots ,e_{n})$
mit $e\in\mathbb{Z}$ und $n\in\mathbb{N}$

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

$k=\left\lfloor\frac{n}{2}\right\rfloor$
mit $a_k$ als mittlerem Listenelement der Liste $L$

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

$L_{l}=(e_{1}, e_{2}, \dots , e_{k})$
$L_{r}=(e_{k+1}, e_{k+2}, \dots , e_{n})$

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

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

$$ \mathit{BiSu(L)} = \begin{cases} \mathit{BiSu}\left(L_{l}\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}\ x = e_{k} \\ \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 $17$ ($\approx \log_2 140000$) Wortvergleichen jedes Wort zu finden.

Scheme-Implementierung der binären Suche

Um eine Implementierung in Scheme zu realisieren, wird die bereits im Kapitel über Mergesort thematisierte Funktion "teillisten2" benötigt.

Scheme-Implementierung der binären Suche:

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.

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.

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

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

Vergleich sequenzielle und binäre Suche

Warum ist also die binäre Suche effizienter als die sequenzielle Suche von $x$ in einer aufsteigend sortierten Liste $G$?

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

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

$\mathit{\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äre Suche vorzuziehen ist.


Effizienzanalyse binäre Suche

Bevor auf die Effizienz eingegangen wird, sei kurz erwähnt, dass die binäre Suche nur bei vorsortierten Listen anwendbar ist. Der Sortieraufwand fällt nur ein einziges mal an, im Beispiel unseres Dudens in der Duden-Redaktion.

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

$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

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

unabhängig von der Anzahl $n$.

Best Case

Im besten Fall kommen beide Suchalgorithmen im ersten Schritt zum Ergebnis. Dabei ist das gesuchte Element bei der sequenziellen Suche das erste Listenelement und bei der binären Suche das erste Element der rechten Teilliste. Beide Suchen erreichen somit einen konstanten Aufwand

$T(n)=\mathcal{O}(c)$

der unabhängig von $n$ ist.

Average- und Worst Case

Die sequenzielle Suche benötigt im schlechtesten Fall $n$ Durchläufe, d.h. $T(n)=\mathcal{O}(n)$. Im mittleren Fall gilt das genauso. Geht man davon aus, das alle Listenelemente mit $x$ mit gleicher Wahrscheinlichkeit übereinstimmen, ist der Aufwand der sequenziellen Suche

$T(n) = \frac {1} {n} \cdot \sum\limits_{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 $\log_2 n$. Für die Vergleichsoperationen in den einzelnen Zwischenschritten wird ein konstanter Aufwand $\mathcal{O}(c)$ angenommen. Dadurch ergibt sich für die binäre Suche im mittleren und schlechtesten Fall ein Gesamtaufwand von $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 sequenziellen 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 der Aufwand der binären Suche wesentlich geringer ist:

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

Multiplikation großer ganzer Zahlen

Die Multiplikation großer ganzer Zahlen nach Karatsuba und Ofman (1960) ist ein typisches Teile-und-Herrsche-Verfahren. Dabei wird die Verringerung des Rechenaufwandes im Vergleich zu der Schulmethode angestrebt, die mit einem quadratischen Aufwand arbeitet. Hierzu werden einige Multiplikationsvorgänge durch Additionsverfahren und Verschiebungen ersetzt, die linear arbeiten.

Um das Verfahren von Karatsuba und Ofman anwenden zu können, müssen zunächst einige Voraussetzungen gegeben sein:

$x$ und $y$ haben die gleiche Stelligkeit $n$
$n$ ist eine gerade Zahl
$x$ und $y$ werden in einen High-Teil $x_1$, bzw. $y_1$ und einen Low-Teil $x_0$, bzw. $y_0$ halbiert
$b$ ist die Basis der Zahlendarstellung, üblicherweise $10$ (Dezimales Zahlensystem)

dadurch gilt

${x = x_1 b^{\frac{n}{2}} + x_0}$
${y = y_1 b^{\frac{n}{2}} + y_0}$

Beide High- bzw. Low-Teile sind durch die Halbierung gleich lang. Die Multiplikation der beiden Zahlen sähe nun folgendermaßen aus:

$x\cdot y = \left(x_{1}\cdot y_{1}\right)b^{n} + \left(x_{0}\cdot y_{1} + x_{1}\cdot y_{0}\right)b^{\frac{n}{2}} + x_{0} \cdot y_{0}$

Als Ergebnis liegen nun, statt einer Multiplikation zweier $n$-stelliger Zahlen, vier gleichartige Multiplikationen zweier $\frac{n}{2}$-stelliger Zahlen zuzüglich dreier Additionen von je zwei Zahlen, die keinesfalls mehr als $n$-stellig sind, vor.

Der Gesamtaufwand beträgt $T(n)=4\cdot T(\frac{n}{2})+\Theta(n)$

Darauf kann die Meistermethode angewandt werden:

$x=4$
$y=2$
$f(n)=n^{log_y x}$
$f(n)=n^{log_2 4}$
$=n^{\frac{\log 4}{\log 2}}$
$=n^{2}$

Damit ergibt sich $T(n)=\mathcal{O}(n^{2})$.

Verglichen mit der Schulbuchmethode ist hier keine Verbesserung eingetreten, da nach wie vor ein quadratischer Aufwand vorliegt. Die Verbesserung erfolgt in den nächsten Schritten. Durch die äquivalente Umformung

$x_{0}\cdot y_{1}+ x_{1}\cdot y_{0}$
$=x_{1}\cdot y_{1}+ x_{0}\cdot y_{0} -\left(x_{0} - x_{1}\right) \cdot \left(y_{0} - y_{1}\right)$

kann der resultierende Term in die obrige Formel eingesetzt werden. Das Resultat ist

$x \cdot y = x_{1} \cdot y_{1}b^{n} + \left( x_{1} \cdot y_{1} + x_{0} \cdot y_{0} - \left( x_{0} - x_{1} \right) \cdot \left( y_{0} - y_{1} \right)\right)b^{\frac{n}{2}} + x_{0} \cdot y_{0}$

Die Produkte $p := x_0 \cdot y_0$ und $q := x_1 \cdot y_1$ kommen jeweils zweimal vor. Sie werden mit einem Aufwand von $T\left(\frac{n}{2}\right)$ jeweils genau einmal berechnet und anschließend eingesetzt:

$x \cdot y = q b^n + \left(q + p - \left(x_0-x_1\right) \cdot \left(y_0 - y_1 \right) \right)b^{\frac{n}{2}} + p$

Zu den beiden Multiplikationen von $p$ und $q$ kommt noch die Multiplikation von $\left( x_0-x_1\right) \cdot \left(y_0 - y_1 \right)$, zwei je $\frac{n}{2}$-stelligen Zahlen sowie deren Addition (in $\Theta\left(n\right)$) hinzu.

Der daraus resultierende Gesamtaufwand beträgt:

$T\left(n\right) = 3 \cdot T \left( \frac{n}{2}\right) + \Theta\left( n\right)$

Nun führt die Anwendung der Meistermethode zu folgendem Ergebnis:

$x=3$
$y=2$
$f(n)=n^{log_y x}$
$f(n)=n^{log_2 3}$
$=n^{\frac{\log 3}{\log 2}}$
$=n^{1.58496}$

In $\mathcal{O}$-Notation:

$T\left( n\right) = \mathcal{O}\left( n^{log_2 3}\right) \approx \mathcal{O}\left( n^{1.58496}\right)$

Die Multiplikation zweier $10^8$-stelliger Zahlen nach dieser Methode dauert mit einer 3GHz-CPU ($= 3 \cdot 10^9$) weniger als eine halbe Stunde:

$(10^8)^{1.582} / 3 \cdot 10^9 / 60 = 26.57219927$

Die gleiche Berechnung nach der Schulmethode dauert mehr als 38 Tage:

$(10^8)^{2} / 3 \cdot10^9 / 60 \approx 55555.555 \ / 60 / 24 \approx 38.5802469$

Übungen

Multiplizieren Sie schriftlich und ohne Taschenrechner die Zahlen $579\ 244$ und $314\ 658$ nach der Methode von Karatsuba. Als Basis verwenden Sie $b = 10$.

Von „https://programmingwiki.de/AuK/Teile_und_Herrsche_2_WS13-14“
Persönliche Werkzeuge