X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=diplomarbeit.tex;h=24ae12526350160e6890ea7eb50378bb096aadc1;hb=a27ff619b95d84323ec966f03e3419959d82f29f;hp=ca9e68abbdb03a56bbc3e7c72557b0707537f5f3;hpb=139bdffa4a9f016aa25f18af4c8414612141a0a7;p=diplomarbeit.git diff --git a/diplomarbeit.tex b/diplomarbeit.tex index ca9e68a..24ae125 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -9,6 +9,7 @@ \usepackage{listings} \usepackage{graphicx} \usepackage{url} +\usepackage[table]{xcolor} %\usepackage{longtable} \usepackage{subfigure} \usepackage{icomma} @@ -43,6 +44,9 @@ \newcommand{\bm}[1]{\ensuremath{\operatorname{BM}\left(#1\right)}} \newcommand{\oet}[1]{\ensuremath{\operatorname{OET}\left(#1\right)}} +\newcommand{\gcell}{\cellcolor{green!10}} +\newcommand{\Gcell}{\cellcolor{green!10!white!95!black}} + \newtheorem{definition}{Definition} \newtheorem{satz}{Satz} @@ -266,8 +270,8 @@ Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden. Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der Komplexitätsklasse -$\mathcal{O}\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, -ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\mathcal{O}(2^n)$ +$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, +ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$ verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen, ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt, @@ -454,7 +458,7 @@ $\operatorname{OET}(3)$ sortiert. Das \emph{Odd-Even-Transpositionsort}-Netzwerk ist weder in Bezug auf die Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n -(n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. +(n-1)} = \Theta(n^2)$~Komparatoren, die in $n$~Schichten angeordnet sind. Die im Folgenden vorgestellten Sortiernetzwerke benötigen deutlich weniger Komparatoren, ($\Theta(n \log (n)^2)$), die in weniger Schichten, ($\Theta(\log (n)^2)$), angeordnet sind. @@ -570,7 +574,7 @@ Statt an eine Treppe erinnert das Muster nun an einen Trichter. Da sich die Anzahl der Leitungen in jedem Rekursionsschritt halbiert, endet die Rekursion nach $\log(n)$~Schritten. In jedem Rekursionsschritt werden $\frac{n}{2}$~Komparatoren eingefügt, so dass der gesamte Mischer aus -$\frac{1}{2} n \log(n) = \mathcal{O}\left(n \log(n)\right)$~Komparatoren +$\frac{1}{2} n \log(n) = \Theta\left(n \log(n)\right)$~Komparatoren besteht, die in $\log(n)$~Schichten angeordnet werden können. \subsubsection{Das bitone Mergesort-Netzwerk} @@ -742,7 +746,7 @@ in Abbildung~\ref{fig:oe-post-recursive} dargestellt. \end{figure} Da die Teilfolgen $U$ und $V$ in jedem Rekursionsschritt etwa halbiert werden, -bricht die Rekursion nach $\mathcal{O}\left(\log (n) + \log (m)\right)$ +bricht die Rekursion nach $\Theta\left(\log (n) + \log (m)\right)$ Schritten ab. Die exakte Anzahl der benötigten Rekursionsschritte (und damit Schichten im Mischer-Netzwerk), hängt von der längeren der beiden Eingabefolgen ab und beträgt $1 + \lceil \log\left(\max(n, m)\right) \rceil$. @@ -760,7 +764,7 @@ Länge der Eingabefolgen, $n$ und $m$ ab: \end{displaymath} Leider ist es schwierig, diese allgemeine Formel in einer geschlossenen Form anzugeben. Aus der Anzahl der Rekursionsschritte ist jedoch leicht erkennbar, -dass $K(n,m)$ in $\mathcal{O}(N \log (N))$ enthalten ist. +dass $K(n,m)$ in $\Theta(N \log (N))$ enthalten ist. Für den wichtigen Spezialfall, dass $n = m = 2^{t-1}$ beträgt, lässt sich die Anzahl der Komparatoren im Vergleich zum \emph{bitonen Mischer} angeben: Der @@ -1248,10 +1252,20 @@ die bei Sortiernetzwerken verfolgt werden können: \item Möglichst wenige Schichten („schnell“) \end{itemize} -Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. Das -effizienteste bekannte Sortiernetzwerk für 16~Eingänge besteht aus -60~Komparatoren in 10~Schichten. Das schnellste bekannte 16-Sortiernetzwerk -besteht aus 61~Komparatoren in nur 9~Schichten. +\begin{figure} + \centering + \subfigure[16-Sortiernetzwerk aus 60~Komparatoren in 10~Schichten. Das Netzwerk wurde von \textit{M.~W. Green} konstruiert und 1969 in \todo{Referenz} veröffentlicht.]{\input{images/16-green.tex}\label{fig:16-green}} + \subfigure[16-Sortiernetzwerk aus 61~Komparatoren in 9~Schichten. Das Netzwerk wurde von \textit{D. Van~Voorhis} veröffentlicht.]{\input{images/16-voorhis.tex}\label{fig:16-voorhis}} + \caption{Das effizienteste und das schnellste Sortiernetzwerk für + 16~Leitungen, das derzeit bekannt ist.} + \label{fig:16-best-known} +\end{figure} +Diese Ziele führen im Allgemeinen zu unterschiedlichen Netzwerken. +Beispielsweise besteht das \emph{effizienteste} bekannte Sortiernetzwerk für +16~Eingänge aus 60~Komparatoren in 10~Schichten. Es ist in +Abbildung~\ref{fig:16-green} dargestellt. Das \emph{schnellste} bekannte +16-Sortiernetzwerk besteht aus 61~Komparatoren in nur 9~Schichten und ist in +Abbildung~\ref{fig:16-voorhis} zu sehen. Eine Gütefunktion, die die beiden Ziele "`effizient"' und "`schnell"' berücksichtigen kann, hat die folgende allgemeine Form: @@ -1380,15 +1394,63 @@ wurde beim \textsc{SN-Evolution}-Algorithmus auf eine Mutation verzichtet. \label{fig:16-e1-bitonic-1296542566} \end{figure} -Verwendet man den \emph{bitonen Mischer} in der Rekombinationsphase von -\textsc{SN-Evolution}, so erhält man Netzwerke wie das in -Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte: Der Algorithmus -wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk als triviale -Initiallösung gestartet. Das Ergebnis ist ein Netzwerk, das effizienter ist -als das \emph{bitone Mergesort}-Netzwerk: \bs{16} benötigt 80~Komparatoren, -das Sortiernetzwerk in Abbildung~\ref{fig:16-e1-bitonic-1296542566} benötigt -lediglich~67. Die Effizienz des \emph{Odd-Even-Mergesort}-Netzwerks wurde -leider mit keiner Leitungszahl erreicht. +Wenn \textsc{SN-Evolution} mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk +als Eingabe gestartet wird und in der Rekombinationsphase den \emph{bitonen +Mischer} verwendet, gibt der Algorithmus Sortiernetzwerke wie das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte zurück. + +Viele der Sortiernetzwerke, die von \textsc{SN-Evolution} in dieser +Konfiguration gefunden werden, sind effizienter als das \emph{bitone +Mergesort}-Netzwerk \bs{n}, das ebenfalls auf dem \emph{bitonen +Merge}-Netzwerk \bm{n} beruht. Das in +Abbildung~\ref{fig:16-e1-bitonic-1296542566} dargestellte 16-Sortiernetzwerk +benötigt 67~Komparatoren, 13~Komparatoren weniger als \bs{n}. + +Wenn die Gütefunktion so gewählt ist, dass sie schnelle Sortiernetzwerke +bevorzugt, können Netzwerke zurückgegeben werden, die schneller als \bs{n} +sind. Viele der schnellen Sortiernetzwerke sind außerdem effizienter als +\bs{n}. Das Sortiernetzwerk mit $n = 23$ Leitungen benötigt mit +134~Komparatoren jedoch einen Komparator mehr als \bs{23}. Die Daten von +schnellen Sortiernetzwerken, die \textsc{SN-Evolution} mit dem \emph{bitonen +Merge}-Netzwerk erzeugt hat, sind in Tabelle~\ref{tbl:sn-ev-bm-fast} +aufgelistet. + +\begin{table}\label{tbl:sn-ev-bm-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \bm{n}} & \multicolumn{2}{|l|}{\bs{n}} \\ +\cline{2-5} + ($n$) & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & \gcell 20 & 6 & 24 & 6 \\ + 9 & \Gcell 26 & 8 & 28 & 8 \\ + 10 & \gcell 31 & \gcell 8 & 33 & 9 \\ + 11 & \Gcell 37 & \Gcell 9 & 39 & 10 \\ + 12 & \gcell 42 & \gcell 9 & 46 & 10 \\ + 13 & \Gcell 48 & 10 & 53 & 10 \\ + 14 & \gcell 54 & 10 & 61 & 10 \\ + 15 & \Gcell 61 & 10 & 70 & 10 \\ + 16 & \gcell 67 & 10 & 80 & 10 \\ + 17 & \Gcell 76 & 12 & 85 & 12 \\ + 18 & \gcell 87 & \gcell 12 & 91 & 13 \\ + 19 & \Gcell 93 & \Gcell 13 & 98 & 14 \\ + 20 & \gcell 104 & \gcell 13 & 106 & 14 \\ + 21 & \Gcell 109 & \Gcell 14 & 114 & 15 \\ + 22 & \gcell 118 & \gcell 14 & 123 & 15 \\ + 23 & 134 & \Gcell 14 & \Gcell 133 & 15 \\ + 24 & \gcell 133 & 15 & 144 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{bitonen Merge}-Netzwerks \bm{n}. Der Algorithmus + wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} gestartet + und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion nutzte die + Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = 1$, + $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} \subsection[Odd-Even-Mischer]{Versuche mit dem Odd-Even-Mischer} @@ -1408,13 +1470,20 @@ Im vorherigen Abschnitt wurde gezeigt, dass der Sortiernetzwerke erzeugen kann, die effizienter als das rekursiv aus dem \emph{bitonen Mischer} aufgebaute \emph{bitone Mergesort}-Netzwerk sind. Dieses Ergebnis lies sich mit dem \emph{Odd-Even-Merge}-Netzwerk nicht -wiederholen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung -des \emph{Odd-Even}-Mischers findet, erreichen das +erzielen. Die Sortiernetzwerke, die \textsc{SN-Evolution} unter Verwendung des +\emph{Odd-Even-Merge}-Netzwerks findet, erreichen das \emph{Odd-Even-Mergesort}-Netzwerk bezüglich Effizienz, übertreffen es aber nicht. Ein Beispiel für ein entsprechendes Sortiernetzwerk ist in -Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. Wenn $n$ keine -Zweierpotenz ist, kann \textsc{SN-Evolution} unter Umständen Sortiernetzwerke -ausgeben, die schneller als \oes{n} sind. +Abbildung~\ref{fig:16-e1-oddeven-1296543330} zu sehen. + +Mit einer Gütefunktion, die schnelle Sortiernetzwerke bevorzugt, ist es auch +mit dem \emph{Odd-Even}-Mischer möglich, dass \textsc{SN-Evolution} +Sortiernetzwerke zurück gibt, die schneller als \oes{n} sind. Dies geschieht +beispielsweise bei $n = 11$ und $n = 12$: für diese Leitungszahlen gibt +\textsc{SN-Evolution} Sortiernetzwerke aus, die nur 9~Schicten benötigen. +\oes{11} und \oes{12} benötigen jeweils 10~Schichten. Eine Auflistung der +Ergebnisse von \textsc{SN-Evolution} mit dem \emph{Odd-Even}-Mischer befindet +sich in Tabelle~\ref{tbl:sn-ev-oem-fast}. %\begin{figure} %\begin{center} @@ -1448,6 +1517,56 @@ ausgeben, die schneller als \oes{n} sind. %\label{fig:10-e2-1239014566} %\end{figure} +\begin{table}\label{tbl:sn-ev-oem-fast} +\begin{center} +\rowcolors{4}{black!5}{} +\begin{tabular}{|r|r|r|r|r|} +\hline +Leitungen & \multicolumn{2}{l|}{\textsc{SN-EV} mit \oem{n}} & \multicolumn{2}{|l|}{\oes{n}} \\ +\cline{2-5} + & Komp. & Schichten & Komp. & Schichten \\ +\hline + 8 & 19 & 6 & 19 & 6 \\ + 9 & 26 & 8 & 26 & 8 \\ + 10 & 31 & 9 & 31 & 9 \\ + 11 & 38 & \Gcell 9 & \Gcell 37 & 10 \\ + 12 & 43 & \gcell 9 & \gcell 41 & 10 \\ + 13 & 48 & 10 & 48 & 10 \\ + 14 & 53 & 10 & 53 & 10 \\ + 15 & 59 & 10 & 59 & 10 \\ + 16 & 63 & 10 & 63 & 10 \\ + 17 & 74 & 12 & 74 & 12 \\ + 18 & 82 & 13 & 82 & 13 \\ + 19 & 93 & \Gcell 13 & \Gcell 91 & 14 \\ + 20 & 97 & 14 & 97 & 14 \\ + 21 & 108 & \Gcell 14 & \Gcell 107 & 15 \\ + 22 & 117 & \gcell 14 & \gcell 114 & 15 \\ + 23 & 129 & \Gcell 14 & \Gcell 122 & 15 \\ + 24 & 128 & 15 & \gcell 127 & 15 \\ +\hline +\end{tabular} +\caption{Übersicht über die Ergebnisse des \textsc{SN-Evolution}-Algorithmus + unter Verwendung des \emph{Odd-Even-Merge}-Netzwerks \oem{n}. Der + Algorithmus wurde mit dem \emph{Odd-Even-Transpositionsort}-Netzwerk \oet{n} + gestartet und nach 2.500.000 Iterationen beendet. Die Bewertungsfunktion + nutzte die Konstanten $w_{\mathrm{Basis}} = 0$, $w_{\mathrm{Komparatoren}} = + 1$, $w_{\mathrm{Schichten}} = n$.} +\end{center} +\end{table} + +\subsection{Zufälliger Mischer} + +Die Ergebnisse der beiden vorhergehenden Abschnitte zeigen, dass für einige +Leitungszahlen der \emph{bitone Mischer} und für andere Leitungszahlen der +\emph{Odd-Even}-Mischer bessere Ergebnisse liefert. Beispielsweise hat das +Netzwerk für $n = 18$ bei Verwendung des \emph{bitone Mischers} nur +12~Schichten, bei Verwendung des \emph{Odd-Even}-Mischers hingegen nur +82~Komparatoren. Daher liegt die Idee nahe, beide Mischer-Netzwerke zu nutzen, +um das beste Ergebnis beider Konstruktionen zu erreichen. +\textsc{SN-Evolution} kann zu diesem Zweck beim Zusammenfügen zweier +Individuen zufällig zwischen dem \emph{bitonen Mischer} und dem +\emph{Odd-Even}-Mischer wählen. \todo{Daten noch in eine Tabelle einfügen.} + %\input{shmoo-aequivalenz.tex} \newpage @@ -1806,8 +1925,8 @@ werden stattdessen Schnittmuster wie $\operatorname{MIN}(6, 7, 11, 12, 15, 16)$, $\operatorname{MAX}(1, 3, 10, 17, 20, 23)$ ausgegeben. Das Ergebnis dieses Schnittmusters ist in Abbildung~\ref{fig:12-ec-from-oes24-fast} zu sehen. Das Sortiernetzwerk besteht aus 43~Komparatoren, die in 9~Schichten -angeordnet sind. Das heißt, dass das resultierende Netzwerk zwar nicht so -effizient wie \oes{12}, dafür aber schneller als \oes{12} und \bs{12} ist. +angeordnet sind. Das resultierende Netzwerk zwar nicht so effizient wie +\oes{12}, dafür aber schneller als \oes{12} und \bs{12}. \begin{figure} \centering