\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\rank}{\textnormal{rank}} \newcommand{\flows}{\textnormal{flows}} \newcommand{\Z}{\mathbb{Z}} \DeclareMathOperator*{\E}{\mathbb{E}} \newcommand{\scalar}[2]{\langle #1, #2\rangle} \)

Zur Wiederholung: wir haben $P$ Maschinen, jede mit einem Speicherplatz $O(S)$, und $N$ Items. Es gilt $PS \geq c\cdot N$. Die Items liegen beliebig über die Maschinen verteilt, aber so, dass sie in den Speicher der jeweiligen Maschine passen. Es gelte $S = N^{\epsilon}$ für ein $0 \lt \epsilon \lt 1$. Der Wert von $\epsilon$ is konstant, hängt also nicht von $N$ ab. Wir wollen die Eingabemenge $X$ aus $N$ Items sortieren: am Ende der Berechnung soll für jedes $x \in X$ ein Item $(x,i)$ erzeugt worden sein, mit $i := \rank(x,X)$, und auf einer beliebigen Maschine liegen.

Die naive Quicksort-Implementierung aus dem letzten Teilkapitel benötigt $O(1/\epsilon^2)$ Runden, was quadratisch mehr ist als unser "Goldstandard" $O(1/\epsilon)$. Dies erinnert uns an die Situation auf der CREW PRAM: naives Mergesort benötigt $O(\log n^2)$ Zeit, und es bedurfte eines doch recht komplizierten Algorithmus (Cole's parallel mergesort), um eine Laufzeit von $O(\log n)$ zu erreichen.

Goodrich, Sitchinava und Zhang geben in ihrem Paper einen Sortieralgorithmus, der in insgesamt $O(1/\epsilon)$ Runden läuft.

Übungsaufgabe (Indexing). Sei $X$ die Menge der $N$ Eingabe-Items. Ziel ist es, eine Ausgabemenge von Items zu berechnen, so dass es

  1. für jedes $x \in X$ genau einen Ausgabe-Item $(x,i)$ mit $1 \leq i \leq N$ gibt; die Zahl $i$ heißt der Index von $x$;
  2. jedes $x \in X$ einen anderen Index hat: wenn also $(x,i)$ und $(x', i')$ in der Ausgabemenge sind und $x \ne x'$, dann auch $i \ne i'$.

In anderen Worten: wir wollen eine injektive Funktion $X \rightarrow [N]$ berechnen. Hierbei ist muss die Ausgabemenge nicht sortiert sein: der Index $i$ von $(x,i)$ muss eindeutig sein, kann aber ansonsten beliebig in $[N]$ sein. Zeigen Sie, wie man das in $O(1/\epsilon)$ Schritten implementieren kann.

Als Baustein für einen schnelleren Quicksort-Algorithmus entwerfen wir uns einen Algorithmus

Übungsaufgabe (Alle Paare bilden). Eingabe sind zwei Mengen $X$ und $Y$ mit $|X|, |Y| \leq \sqrt{N}$. Ziel ist es, als Ausgabemenge das cartesische Produkt $X \times Y$ zu berechnen: jedes Item $(x,y) \in X \times Y$ soll genau auf einer Maschine liegen.

Zeigen Sie, wie man das in $O(1/\epsilon)$ implementieren kann.

Tip: Stellen Sie sich eine $(\sqrt{N} \times \sqrt{N})$-Matrix vor, bei der die $i$-te Zeile für $x_i$ und die $j$-te Spalte für $y_j$ "zuständig" ist. Bauen Sie Bäume, um $x_i$ von links ausgehend zu jeder Zelle in Zeile $i$ zu schicken.

Übungsaufgabe Zeigen Sie, wie man mit Hilfe der letzten Übung eine Menge $X$ von $\sqrt{N}$ Elementen in $O(1/\epsilon)$ Runden sortieren kann.

Gegeben seien zwei Mengen $X$ und $Y$, beide mit $|X|, |Y| \leq \sqrt{N}$. Beschreiben Sie, wie man in $O(1/\epsilon)$ Runden für jedes $x \in X$ den Rang $\rank(x,Y)$ berechnen kann. Am Ende der Berechnung soll also für jedes $x \in X$ ein Item $(x, \rank(x,Y))$ erzeugt worden sein.

Ab jetzt persönliche Notizen. Noch unausgereift!

Definition ($k$-verzweigter Suchbaum für $Z$). Wir konstruieren einen Baum von unten (Blätter) nach oben (Wurzel), in der jeder Knoten $v$ eine Menge $Z_v \subseteq Z$ der Größe $k$ enthält.

  • Der unterste Level, also die Blätter, besteht aus $|X|/k$ Knoten. Wenn $l$ das $i$-te Blatt ist, dann setzen wir $Z_l := \{z_{ik}, z_{ik+1}, \dots, z_{ik+k-1}\}$.
  • Solange die oberste Ebene mehr als einen Knoten enthält:
    • Fasse die Knoten der obersten Ebene in Blöcke von $k$ Knoten zusammen.
    • Für so einen Block $v_1, \dots, v_k$ erschaffen wir einen gemeinsamen Elternknoten $u$ eine Ebene höher.
    • Die Menge $Z_u$ besteht aus den $k$ Minima seiner Kinder, also \begin{align*} Z_u := \{ \max(Z_v) \ | \ \textnormal{$v$ ein Kind von $u$}\} \ . \end{align*}

Sofern $k \leq S$ ist, können wir jedem Knoten in dem Baum eine Maschine zuordnen. Wenn $X$ sortiert ist, können wir den Baum effizient in $O(h)$ Runden bauen; $h = \log_k |Z|$ ist die Höhe des Baumes.

Unser neues Quicksort wählt nun eine Menge $Z$ von (circa) $\sqrt{N}$ Pivots und sortiert diese so wie in . Sei nun $T$ so ein $k$-ärer Suchbaum für die Menge $Z$ der Pivots, und sei $h$ seine Höhe. Für ein Eingabeitem $x \in X$ können wir mit Hilfe von $T$ den Rang $\rank(x,Z)$ in $O(h)$ Runden bestimmen. Das geht, sofern $k \leq S$ ist, weil ja jeder Knoten $k$ Elemente speichern muss.

Wieviele Items können wir mit so einem Baum parallel verarbeiten? Sei $Q \subseteq X$ eine Menge von Items. Wenn $|Q| \leq S$ ist, können wir $Q$ der Wurzel-Maschine schicken; diese ist damit nicht überlastet. Sie bestimmt dann lokal für jedes $q \in Q$, in welchem der $k$ Unterbäume weitergesucht werden muss.

Literatur