From 36e6060c43037ba34eb96b809e6a0349fa545cf1 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Fri, 25 Feb 2011 14:13:55 +0100 Subject: [PATCH] =?utf8?q?SN-Evolution:=20Versuche=20mit=20dem=20Odd-Even-?= =?utf8?q?Mischer=20=C3=BCberarbeitet.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- diplomarbeit.tex | 54 +++++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 49 insertions(+), 5 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 8e7beca..98dd41e 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -1460,13 +1460,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} @@ -1500,6 +1507,43 @@ 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} + %\input{shmoo-aequivalenz.tex} \newpage -- 2.11.0