3.3 Valiants $O(\log \log n)$-Merge (und warum es nicht ganz korrekt ist)

Leslie Valiant fand 1975 eine trickreiche Methode, zwei Arrays der Länge $n$ mit in $O(\log \log n)$ zu mergen. Der Algorithmus ist rekursiv und verwendet folgendes Lemma als Grundbaustein:

Um nun $\text{merge}(A,B)$ zu berechnen, wählen wir jedes $\sqrt{m}$-te Element aus $A$ und jedes $\sqrt{n}$-te Element aus $B$ aus

und speichern sie in einem Array:

$$\begin{array}{rl}{A}^{\prime }& :=[A[i\cdot \sqrt{m}]|1\le i\le \sqrt{m}-1]\\ B^{\prime }& :=[B[j\cdot \sqrt{n}]|1\le j\le \sqrt{n}-1].\end{array}$$

Mittels Lemma 3.3.1 bestimmen wir mit $|A^{\prime }|\cdot |B^{\prime }|=\sqrt{mn}$ Prozessoren in $O(1)$ Zeit den Rang $\text{rank}(A^{\prime }[i],B^{\prime })$ für jedes $1\le i\le \sqrt{m}-1$. Für bestimmtes $i$ bezeichnen wir diesen Rang mit $j$. Es gilt also

$$\begin{array}{r}B[j\sqrt{n}]<A[\sqrt{i}]<B[(j+1)\sqrt{n}].\end{array}$$

Bildlich gesprochen heißt dass, wir wissen, in welches "Teilstück" von $B^{\prime }$ das Element $x$ gehört.

In einem nächsten Schritt bestimmen wir, wieder mit Hilfe von Lemma 3.3.1, den Rang von $x=A[\sqrt{i}]$ in "seinem Interval" $B[j\sqrt{n}+1,\dots ,(j+1)\sqrt{n}-1]$. Wir tun dies parallel für jedes $1\le i\le \sqrt{m}-1$ und brauchen dafür wieder $\sqrt{mn}$ Prozessoren und $O(1)$ Zeit. Mit $O(\sqrt{mn})$ Prozessoren und $O(1)$ Zeit haben wir also folgendes berechnet:

Wir kennen also $\text{rank}(x,B)$ für jedes $x\in A^{\prime }$. So können wir $B$ in $\sqrt{m}$ Teilarrays $B_1,B_2,\dots ,B_{\sqrt{m}}$ zerlegen und $A$ ebenso in $A_1,A_2,\dots ,A_{\sqrt{m}}$, so dass

$$\begin{array}{r}{A}_i,B_i\le A[i\sqrt{m}]<A_{i+1},B_{i+1}\end{array}$$

gilt. Mit der Schreibweise $U<x$ für eine Liste $U$ meinen wir, dass $z<x$ für jedes $z\in U$ gilt. Wir können nun also

$$\begin{array}{}\text{(2)}& \text{merge}(A,B)=\text{merge}(A_1,B_1)\circ \text{merge}(A_2,B_2)\circ \cdots \circ \text{merge}(A_{\sqrt{m}-1},B_{\sqrt{m}-1})\circ \text{merge}(A_{\sqrt{m}},B_{\sqrt{m}})\end{array}$$

wobei jedes $\text{merge}(A_i,B_i)$ rekursiv gelöst wird.

Zeitkomplexität

Anfangs haben unsere Listen $A$ und $B$ die Längen $m$ und $n$. Nach einem Rekursionsschritt haben wir $\sqrt{m}$ Teilprobleme $(A_i,B_i)$ mit $|A_i|=\sqrt{m}$. Die Länge der "linken" Liste schrumpft also in $O(1)$ Zeitschritten von $m$ auf $\sqrt{m}$. Nach einem weiteren Rekursionsschritt haben die linken Listen Länge $\sqrt{\sqrt{m}}$ und ganz allgemein nach $t$ Rekursionsebenen Länge $\sqrt[2^t]{m}$. Für jedes Teilproblem $\text{merge}(A^{\prime },B^{\prime })$ gehen wir davon aus, dass uns $\sqrt{|A^{\prime }|\cdot |B^{\prime }|}$ Prozessoren zur Verfügung stehen. Nach $T:=\log \log m$ Ebenen haben wir Listen der Länge $$\begin{array}{r}{m}^{2^{-T}}=m^{2^{-\log \log m}}=m^{\frac{1}{\log m}}={\left(2^{\log m}\right)}^{\frac{1}{\log m}}=2\end{array}$$

erreicht. Das verbleibende Problem $\text{merge}(A^{\prime },B^{\prime })$ für $|A|\le 2$ können wir mit $\sqrt{|A^{\prime }|\cdot |B^{\prime }|}$ Prozessoren in $O(1)$ Schritten berechnen. Insgesamt benötigen wir also $O(T)=O(\log \log m)$ Schritte, um $\text{merge}(A,B)$ zu berechnen.

Anzahl der Prozessoren

Um die rechte Seite von ($\text{2}$) zu berechnen, müssen wir $\text{merge}(A_i,B_i)$ für jedes $1\le i\le \sqrt{m}-1$ berechnen. Dies tun wir rekursiv. Dafür statten wir das Teilproblem $\text{merge}(A_i,B_i)$ mit $\sqrt{|A_i|\cdot |B_i|}$ Prozessoren aus. Sei $m_i:=A_i$ und $n_i:=B_i$. Wir wissen, dass $m_i=\sqrt{m}$ (bis eventuell auf das letzte Array); $n_i$ allerdings kann bis zu $n$ Elemente erhalten; wir wissen nur, dass $\sum n_i=n$ ist. Wir können daher die benötigte Anzahl an Prozessoren mit der Cauchy-Schwarz-Ungleichung abschätzen:

$$\begin{array}{}\text{(3)}& \sum _{i=1}^{\sqrt{m}-1}\sqrt{m_i{n}_i}\le \sqrt{\sum _i{m}_i}\sqrt{\sum _i{n}_i}=\sqrt{mn}.\end{array}$$

Wenn $A$ und $B$ anfangs also jeweiles $n$ Elemente haben, so können wir mit $n$ Prozessoren verfahren und diese dann auch auf die Teilprobleme aufteilen - wir haben für jedes Teilproblem ausreichend viele Prozessoren.

Was wir unterschlagen haben

Die obige Laufzeitanalyse unterschlägt ein wichtiges Detail: die Ungleichung ($\text{3}$) sagt uns zwar, dass wir unsere $\sqrt{mn}$ hinreichend viele sind, um jedes Teilproblem adäquat auszustatten, sagt uns aber nicht, welcher Prozessor auf welchem Teilproblem arbeiten muss. Betrachten wir den $l$-ten unserer $\sqrt{mn}$ Prozessoren für $\text{merge}(A,B)$. Soll er zugeordnet werden? Für die ersten $k$ Teilprobleme benötigen wir

$$\begin{array}{}\text{(4)}& p_k:=\sum _{i=1}^k\sqrt{m_i{n}_i}\end{array}$$

Prozessoren. Prozessoren $1,\dots ,p_1$ arbeiten also an $\text{merge}(A_1,B_1)$; Prozessoren $p_1+1,\dots ,p_2$ an $\text{merge}(A_2,B_2)$ und so weiter. Der Haken hierbei: bei ($\text{4}$) handelt es sich um eine Präfixsumme. Und um die zu berechnen bräuchten wir selbst wieder Zeit $O(\log n)$, wie wir in Kapitel 2.3 gelernt haben.

Valiant erkennt dieses Problem und unterscheidet zwischen Schritten, in denen tatsächlich Elemente aus der zu sortierenden Menge verglichen werden und "Overhead" und erwähnt, dass wachsender Overhead die Effizienzgewinne wieder zunichte macht. Auf der einen Seite ist das unbefriedigend, weil wir ja alle Berechnungsschritte zählen wollen, nicht nur die, in denen ein Vergleich ausgeführt wird; andererseits ist es vielleicht ganz interessant, zu untersuchen, was man alles machen kann, wenn man nur Vergleichsoperationen zählt.

Maximum in $O(\log \log n)$ parallelel Vergleichsschritten

Lassen wir uns also auf Valiants Gedankenexperiment ein, nur Schritte zu zählen, in denen wirklich Vergleichsoperationen durchgeführt werden. Wir nennen solche Schritte parallele Vergleichsschritte. Alle anderen Operationen, also Ergebnisse addieren, kopieren betrachten wir als kostenlos.

Dies ist also deutlich schneller als der traditionelle binärbaumartige Algorithmus, der so vorgeht wie in der K.o.-Runde einer Weltmeisterschaft und $O(\log n)$ Schritte braucht.