Warum ist Pointer Jumping ineffizienter als der Algorithmus (ursprünglich: Schaltkreis) für Präfixsumme? Schauen wir uns nochmal das Beispiel für Pointer Jumping an, und zwar zu dem Zeitpunkt, zu dem Zeitschritt 1 abgeschlossen ist:

Der Prozessor, der für das erste Listenelement (mit Wert 19) zuständig ist, zeigt nun auf das dritte Element und wird auch im weiteren Verlauf in jedem Schritt Arbeit leisten. Alternativ könnte er sich doch verabschieden und warten, bis das zweite Listenelement "fertig" ist (also auf das Ende deutet), und dann den Wert übernehmen. In etwa wie hier:

Nur gerade Indizes nehmen am Pointer Jumping teil. Die anderen verabschieden sich, bis die geraden fertiggeworden sind. Dann machen wir rekursiv weiter (sprich: teilen jeden geraden Index durch zwei). Das ist im Prinzip genau das, was wir auf Arrays bei Präfixsummen getan haben. Warum geht das bei Listen nicht? Um das auf Listen zu implementieren, müsste jedes Listenelement wissen, ob es geraden oder ungeraden Index hat. Wofür es seinen Rang, also seinen Abstand zum Listenende wissen müsste - genau jenes Problem, das wir im Moment lösen wollen.

Randomisierung

Verallgemeinern wir das Prinzip "gerade Werte machen Pointer Jumping, ungerade Werte verabschieden sich vorerst" zu "Listenelemente in der Menge $X$ verabschieden sich; Elemente in $L \setminus X$ überspringen sie."

Diesen Schritt kann man in einem Zeitschritt ausführen, falls keine zwei aufeinanderfolgenden Listenglieder in $X$ liegen. Falls dies so wäre, könnten wir den neuen Nachfolger nicht in konstanter Zeit berechnen, wie zum Beispiel Knoten $u$ in dieser Liste:

Um die Elemente in $X$ in konstanter Zeit überspringen zu können, um also die "kontrahierte" Liste auf den Elementen $L \setminus X$ in konstanter Zeit bauen zu können, müssen wir (in konstanter Zeit) eine unabhängige Menge $X$ finden; und zwar soll $X$ möglichst groß sein - im Idealfall $n/2$, aber $\Omega(n)$ wäre auch in Ordnung; dann würden wir in jeder Runde einen konstanten Anteil von Elementen eliminieren (überspringen) und wären nach $O(\log n)$ Runden fertig.

Wir unterhalten einen Prozessor pro Listenelement $u$. In jedem Schritt wirft jeder Prozessor eine Münze - wählt also ein Zufallsbit $b(u)$ in $\{0,1\}$. Wenn nun $b(u)=1$ und $b(\succ[u])=0$, dann fügen wir $u$ in $X$ ein.

Wir wiederholen diesen Schritt $T$ mal. Elemente $u$, die zu einem Zeitpunkt $t$ eliminiert werden (also grau markiert werden), merken sich den Zeitpunkt: $\textnormal{elim-time}[u] := t$. Vorgänger von grauen Elementen, die also Pointer Jumping durchführen, merken sich, wie lange ihr Pointer ist - wie weit voraus in der ursprünglichen Liste also ihr Nachfolger liegt. Hierfür initialisieren wir $\textnormal{dist}[u] := 1$ für alle $u$ bis auf das letzte Glied; dann setzen wir, falls $\succ[u]$ eliminiert wird:

\begin{align*} \textnormal{dist}[u] := \textnormal{dist}[u] + \textnormal{dist}[\succ[u]] \tag{falls $\succ[u]$ eliminiert wird} \end{align*}

Wenn wir zum Ende gekommen sind, also alle Elemente bis auf das letzte (mit der Selbstschleife) eliminiert worden sind, dann starten wir die Rekonstruktionsphase, in der wir $\textnormal{rank}[u]$ für jedes Element berechnen wollen (also den Abstand von Element $u$ zum Ende der Liste, gemessen in der ursprünglichen Liste). Sei $z$ das letzte Listenelement. Wir setzen $\textnormal{rank}[z] :=0 $ und zählen dann die Zeitschritte zurück: $t = T, T-1, \dots, 1$. Sei $t$ der aktuelle Zeitschritt dieser Phase. Wenn $\textnormal{elim-time}[u] = t$ ist, dann setzen wir

\begin{align*} \textnormal{rank}[u] := \textnormal{dist}[u] + \textnormal{rank}[\succ[u]] \ . \end{align*}

Per Induktion können wir nun zeigen, dass jedes Element $u$ zum Zeitpunkt $t = \textnormal{elim-time}[u]$ seinen richtigen Rang zugewiesen bekommt:

1. Sei $v := \succ[u]$. Das Element $v$ wird später als $u$ eliminiert (oder gar nicht, wenn es das Ende der Liste ist), also hat $\textnormal{\rank}[v]$ bereits den korrekten Wert.
2. Den Abstand von $u$ zu $v$ in der ursprünglichen Liste haben wir uns in Phase 1 in $\textnormal{dist}[u]$ gemerkt.

Analyse

Die Gesamtzahl der Zeitschritte in Phase 2 ist gleich der in Phase 1. Wir müssen also überlegen, wie lange Phase 1 dauert. Dies steht nicht a priori fest sondern ist eine Zufallsvariable! Rein theoretisch könnten wir ja Pech haben und in den ersten $n$ Schritten für jedes Element $b(u) = 0$ wählen und somit gar keine Elemente eliminieren. Wir müssen nun mit Wahrscheinlichkeiten rechnen. Was ist die Wahrscheinlichkeit, dass ein (bis jetzt noch nicht eliminiertes Element) $u$ in der nächsten Runde eliminiert wird?

\begin{align*} \Pr[u \textnormal{ wird eliminiert}] & = \Pr[b(u)=1 \wedge b(\succ[u])=0] = \frac{1}{4} \ . \end{align*}

Im Schnitt sinkt also die Länge der Liste in jedem Schritt um einen Faktor $3/4$. Machen wir das präzise. Die Wahrscheinlichkeit, dass ein Element $u$ nach $t$ Schritten noch nicht eliminiert worden ist, ist

\begin{align*} \pfrac{3}{4}^t \end{align*}

Sei $Y_t$ die Anzahl der Elemente, die nach $t$ Schritten noch nicht eliminiert worden sind, also die Länge der Restliste. Es gilt $Y_0 = n$ und

\begin{align*} \E[Y_t] & = \sum_{\textnormal{Element} u} \Pr[u \textnormal{ noch nicht eliminiert nach $t$ Schritten}] \\ & = n \cdot \pfrac{3}{4}^t \ . \end{align*}

Für $t := 6 \log n$ ist dies

\begin{align*} \E[Y_{6 \log n}] & = n \cdot \pfrac{3}{4}^{6 \log n} \\ & = n \cdot \pfrac{27}{64}^{2 \log n} \\ & \lt n \cdot \pfrac{1}{2}^{2 \log n} = n \cdot \frac{1}{n^2} = \frac{1}{n} \ . \end{align*}

Falls wir nach $6 \log n$ Schritten also noch nicht zu Ende sind, dann gilt $Y_{6 \log n} \geq 1$. Nach Markovs Ungleichung ist

\begin{align*} \Pr[Y_{6 \log n} \geq 1] \leq \frac{1}{n} \ . \end{align*}

Wir können also nach $t = 6 \log n$ Schritten eine "Abstimmung" durchführen, in der wir schauen, ob es überhaupt noch überlebende Listenelemente gibt. Hierfür könnte jeder Prozessor für "sein" Element $u$ einen Indikator $\textnormal{survives}[u] \in \{0,1\}$ setzen. Wir berechnen dann parallel in $\log n$ Schritten die Summe

\begin{align*} \textnormal{survives}[1] + \textnormal{survives}[2] + \cdots + \textnormal{survives}[n] \ . \end{align*}

Falls diese größer ist als 1, dann führen wir noch einmal $6 \log n$ Schleifendurchläufe durch, und so weiter. Im Erwartungswert brauchen wir also $O(\log n)$ Schritte, bis Phase 1 zu Ende ist.

Implementierung

Der Algorithmus von Anderson und Miller

Der obige Algorithmus braucht immer noch $O(n \log n)$ Arbeit, was daran liegt, dass wir auch für bereits eliminierte Elemente Arbeit verrichten müssen - und sei es nur, zu überprüfen, ob dieses Element noch in der Restliste oder bereits eliminiert worden ist. Die Idee des nächsten Algorithmus ist nun, die Elemente so auf eine beschränkte Menge von Prozessoren aufzuteilen, dass jeder Prozessor sich in jedem Schritt auf ein noch existierendes Listenelement konzentrieren kann. Der Algorithmus stammt aus dem Paper A simple randomized parallel algorithm for list-ranking von Richard J. Anderson und Gary L. Miller aus dem Jahre 1988.

Wir gehen von $n/\log n$ Prozessoren aus. Unsere Liste liegt in $n$ aufeinanderfolgenden Speicherzellen $1, \dots, n$, wobei wir eben nicht davon ausgehen können, dass der Listennachfolger von $i$ die Zelle $i+1$ ist. Wir teilen die $n$ Elemente gleichmäßig auf die Prozessoren auf, so dass jeder Prozessor einen Block von $\log n$ zusammenhängend im Speicher liegenden Zellen (also Elementen) bekommt. Prozessor $i$ ist also für die Speicherzellen $Z_i := \{i \log(n), i \log(n)+1, \dots, i \log (n) + \log(n)-1\}$ zuständig. Wir betonen, dass die Zellen $Z_i$ einen zusammenhängenden Block im Speicher bilden, nicht notwendigerweise in der Liste. Wir gehen nun ähnlich vor wie im vorherigen Algorithmus, allerdings vorsichtiger.

1. Jeder Prozessor merkt sich einen Index $v \in Z_i$, nämlich die linkeste Speicherzelle, die einem noch nicht eliminierten Listenelement entspricht. Anfangs ist also $v = i \log (n)$. Wir nennen $v$ die aktive Zelle von Prozessor $i$.
2. Der Prozessor wählt ein Bit $b[v] \in \{0,1\}$. Falls $\succ[v]$ selbst Bit $0$ gewählt hat (oder gar nicht aktive Zelle eines Prozessors ist), fügen wir $v$ in die Menge $X$ der zu eliminierenden Elemente ein.
3. Falls $j$ eliminiert werden soll, so merkt sich der Prozessor den Zeitpunkt der Eliminierung: $\textnormal{elim-time}[v] = t$. Wir bestimmen den Vorgänger $u := \pred[v]$ und führen für ihn Pointer Jumping durch: \begin{align*} \dist[u] & := \dist[u] + \dist[v]\\ \succ[u] & := \succ[v] \end{align*}

Wir können die Vorgänger $\pred[v]$ anfangs in einem Schritt parallel berechnen (bzw. mit $n/\log n$ Prozessoren mit $\log n$ Schritten).

Laufzeit-Analyse

Wir können Phase 1 beenden, wenn alle Prozessoren ihren Teil abgearbeitet haben, jeder Prozessor also seine $\log n$ Listenelemente eliminiert hat. Im Worst-Case zeigt die aktive Zelle $v$ eines Prozessors auf die aktive eines anderen, und dann ist die Wahrscheinlichkeit, dass wir $v$ eliminieren können, wieder $\frac{1}{4}$. Im Schnit würde es also $4 \log n$ Runden dauern, bis Prozessor $i$ seine Elemente eliminiert hat. (Mit etwas Zusatzarbeit könnten wir bestimmt zeigen, dass ein aktives Element eben nicht immer auf ein anderes aktives deuten wird und dass daher die Wahrscheinlichkeit deutlich höher als $\frac{1}{4}$ liegen wird; auf mehr als $1/2$ werden wir allerdings sicherlich nicht kommen, und da uns konstante Faktoren nicht interessieren, werden wir auch nicht weiter groß darüber nachdenken). Wenn nun also jeder Prozessor im individuellen Erwartungswert nach höchstens $4 \log n$ Schritten fertig ist, wie lange wird es dauern, bis alle Prozessoren fertig sind? Wir wollen nun zeigen, dass nach $16 \log n$ Schritten mit hoher Wahrscheinlichkeit alle Prozessoren fertig sind.

Wir definieren die Indikatorvariablen $X_t^{(i)}$ wie folgt:

\begin{align*} X_t^{(i)} := \begin{cases} 1 & \textnormal{ wenn Prozessor $i$ zum Zeitpunkt $t$ ein Listenelement eliminieren konnte} \\ 0 & \textnormal{ sonst.} \end{cases} \end{align*}

Sei $E_i$ das Ereignis, dass $\sum_{t=1}^T X_t^{(i)} \lt \log n$ ist; dass also Prozessor $i$ nach $T$ Schritten noch nicht fertig ist. Die Ereignisse $E_1, E_2, \dots, E_p$ sind nicht unabhängig, da die $\succ$-Pointer im Allgemeinen zwischen den Blöcken, die den einzelnen Prozessoren zugeordnet sind, hin- und herzeigen. Wir wenden daher eine Union-Bound-Schranke an:

\begin{align*} \Pr[\textnormal{Nach $T$ Schritten sind nicht alle Prozessoren fertig}] & = \Pr\left[\bigcup_{i=1}^p E_i \right]\\ & \leq \sum_{i=1}^p \Pr[E_i] \ . \end{align*}

Wir konzentrieren uns nun darauf, zu zeigen, dass $\Pr[E_i]$ klein ist. Auch für einen Prozessor $i$ sind die unterschiedlichen Variablen $X^{(i)}_1, X^{(i)}_2, \dots$ im Allgemeinen nicht unabhängig. Allerdings gilt: wenn $\sum_{t=1}^s X^{(i)}_s \lt \log n$, wenn Prozessor $i$ also nach $s$ Schritten noch nicht alle Listenelemente abgearbeitet hat, dann gilt $\Pr[X^{(i)}_{s+1}] \geq \frac{1}{4}$: zu jedem Zeitpunkt wird das aktive Element mit Wahrscheinlich mindestens $1/4$ eliminiert, egal, was bisher geschehen ist. Formal:

Wir definieren nun unabhängige Zufallsvariable $Y_1, \dots, Y_T$, die Werte in $\{0,1\}$ annehmen und $\Pr[Y_t = 1] = \frac{1}{4}$ für jedes $t$ erfüllen. Die $X_t^{(i)}$ sind also "mindestens so gut" wie die $Y_t$, und daher gilt

Formal müsste man dies mit einem Coupling Argument zeigen. Hier vertrauen wir aber auf unsere Intuition, dass die $X^{(i)}_t$ ja immer "besser" sind als die $Y_t$.

Die Tschebyschow-Ungleichung reicht nicht aus

Sei $T = 16 \log n$. Was ist die Wahrscheinlichkeit, dass Prozessor $i$ nach $T$ Schritten noch nicht fertig ist? Wie wir gesehen haben ist das höchstens die Wahrscheinlichkeit, dass $Y_1 + \cdots Y_T \lt \log n = T/16$ ist. Sei $Y := Y_1 + \cdots Y_T$. Im Erwartungswert ist $\E[Y] = T/4$. Das "schlechte" Ereignis tritt also dann ein, wenn der tatsächliche Wert von $Y$ weniger als ein Viertel seines Erwartungswertes ist. So eine Wahrscheinlichkeit können wir mit der Tschebyschow-Ungleichung abschätzen.

In unserem Fall gilt $\E[Y] = T/4$. Wenn also $Y \lt T/8$, dann ist $|Y - \E[Y]| \gt |T/8 - T/4| = T/8$ und somit

\begin{align*} \Pr[Y \lt T/8] \leq \frac{\Var(Y)}{(T/8)^2} \ . \end{align*}

Da $Y = Y_1 + \cdots + Y_T$ ist und die einzelnen $Y_t$ unabhängig sind, gilt

\begin{align*} \Var(Y) = \Var(Y_1) + \cdots + \Var(V_T) = T \cdot \Var(Y_1) \ , \end{align*}

da alle $Y_t$ die gleiche Verteilung haben. Was ist nun $\Var(Y_1)$? Für eine Variable, die nur die Werte $0$ und $1$ annimmt und $1$ mit Wahrscheinlichkeit $p$ gilt $\Var(Y_1) = p (1-p)$; in unserem Fall ist $p=1/4$ und somit $\Var(Y_1) = \frac{1}{4} \cdot \frac{3}{4}$. Zusammen also

\begin{align*} \Pr[Y \lt T/8] \leq \frac{\Var(Y)}{(T/8)^2} = \frac{T \cdot \frac{3}{16}}{(T/8)^2} = \frac{T \cdot 3 \cdot 64}{T^2 \cdot 16} = \frac{12}{T} = \frac{12}{8 \log n} = \frac{3}{2} \cdot \frac{1}{\log n} \ . \end{align*}

Kombinieren wir das nun mit unserem Union Bound oben:

\begin{align*} & \Pr[\textnormal{Nach $T$ Schritten sind nicht alle Prozessoren fertig}] \\ & = \Pr\left[\bigcup_{i=1}^p E_i \right]\\ & \leq \sum_{i=1}^p \Pr[E_i] \\ & = \sum_{i=1}^p \Pr\left[ \sum_{t=1}^T X_t^{(i)} \lt \log n\right] \\ & \leq \sum_{i=1}^p \Pr\left[ \sum_{t=1}^T Y_t \lt \log n\right] \\ & \leq \sum_{i=1}^p \frac{3}{2} \cdot \frac{1}{\log n} \\ & = \frac{3p}{2 \log n}\\ & = \frac{3 n}{2 (\log n)^2 } \ , \end{align*}

weil wir ja $p = n / \log n$ viele Prozessoren verwenden. Was haben wir bewiesen? Die Wahrscheinlichkeit zum Scheitern ist höchstens $\frac{3 n}{2 (\log n)^2 }$. Das ist aber eine nutzlose Schranke, weil sie immer größer ist als $1$. Und in der Tat ist die Tschebyschow-Ungleichung bei der Analyse von Algorithmen oft nicht stark genug.

Sei $Y = Y_1 + \cdots + Y_T$ die Summe unabhängiger $0/1$-Zufallsvariablen mit $\Pr[Y_t=1] = p$. Die Tschebyschow-Ungleichung besagt in Worten, dass große Abweichungen vom Erwartungswert bei $Y$ unwahrscheinlich sind, und insbesondere hat diese Wahrscheinlichkeit die Form $c/T$. Der genaue Wert von $c$ hängt nun $p$ ab und davon, was wir unter einer "großen" Abweichung verstehen. Die Chernoff-Schranke, die wir im nächsten Teilkapitel kennenlernen werden, besagt, dass die Wahrscheinlichkeit einer großen Abweichung noch viel kleiner ist, nämlich $\exp(-cT)$. Da $T = \log n$ ist, ist das höchstens $1/n^2$, wenn wir die Konstante $c$ richtig hinkriegen. Dann könnten wir wie folgt rechnen:

\begin{align*} & \Pr[\textnormal{Nach $T$ Schritten sind nicht alle Prozessoren fertig}] \\ \leq \dots \leq & \sum_{i=1}^p \Pr\left[ \sum_{t=1}^T Y_t \lt \log n\right] \tag{siehe Rechnung oben} \\ & \leq \sum_{i=1}^p \frac{1}{n^2} \\ & = \frac{n}{\log n} \cdot \frac{1}{n^2} \lt \frac{1}{n} \ . \end{align*}

Und somit ist die Wahrscheinlichkeit, dass wir nach $16 \log n$ Schritten nicht fertig sind, sehr klein. Wir können nun nach $16 \log n$ Schritten eine parallele "Umfrage" durchführen, um herauszufinden, ob wir fertig sind. Ansonsten würden wir wiederum $16 \log n$ Schritte fortfahren. Die erwartete Laufzeit von Phase 1 - und des gesamten Algorithmus - ist somit $O(\log n)$. Da wir $n / \log n$ Prozessoren beschäftigen, ist die Anzahl der Arbeitsschritte $O(n)$.