2.4 Listenpräfix

Ein Array erlaubt es uns, auf das Element $A[i]$ in konstanter Zeit zuzugreifen. Das liegt daran, dass wir uns nur die Anfangsadresse $\mathtt{\text{address}}(A)$ merken müssen und dan das $i$-te Element in Zelle $\mathtt{\text{address}}(A)+i$ finden. Das ist der Grund, warum Sie in C folgenden Code schreiben können (wenn auch nicht schreiben sollten):

#include <stdio.h>

int main () {
    char *name = "psarallel algorithms";
    printf("%cn", *(name + 7)); // statt printf("%cn", name[7]);

    int primes[7] = {2,3,5,7,11,13,17};
    printf("%dn", *(primes + 5)); // statt printf("%dn", primes[5]);
}

Arrays erlauben also Zugriff in konstanter Zeit, haben allerdings andere Nachteile. So können wir in Arrays nicht an Stelle $i$ ein neues Element einfügen (hierfür müssten wir alle Elemente, die nach $i$ kommen, um 1 nach hinten verschieben; und im Worstcase auch mit dem ganzen Array umziehen, denn es ist nicht gesagt, dass hinter dem Array noch eine Speicherstelle frei ist); und oft liegen die Daten gar nicht als Array vor.

Ein Datentyp, der effizientes Löschen und Einfügen unterstützt ist die verkettete Liste, auf Englisch linked list. Ein Element besteht aus einem Datensatz und einem Zeiger auf das nächste Element. Das stellen wir gerne graphisch dar:

Diese Darstellung kann leicht irreführend sein, weil sie "zu übersichtlich" ist. In der Wirklichkeit eines Rechnerspeichers sieht es eher so aus:

Wir wollen nun auch auf solchen verketteten Listen schnell parallel Präfixsummen berechnen. Sei also $l=[l_1,l_2,\dots ,l_n]$ eine verkettete Liste, so wollen wir eine Liste $[s_1,s_2,\dots ,s_n]$ erstellen, welche die Teilsummen

$$\begin{array}{r}{s}_i:=l_i+l_{i+1}+\cdots +l_n\end{array}$$

enthält. Sicherlich haben Sie gemerkt: wir summieren hier von $i$ nach $n$, nicht von $1$ nach $i$. Wir sollten also eher von Suffixsummen sprechen. Wir vollziehen diesen Wechsel, weil sich die Algorithmen leichter für Suffixsummen erklären lassen. Im Folgenden betrachten wir den Fall, dass die Liste aus $n$ Gliedern besteht, die in den ersten $n$ Stellen unseres Speichers liegt. Als Werte speichern wir nicht Buchstaben wie im obigen Beispiel, sondern Zahlen. Weil wir ja Summen bilden wollen. Also zum Beispiel die Liste

Wir führen die Konvention ein, dass die Liste mit einer $0$ endet. Dies ist leicht zu erreichen und dient primär dazu, die Algorithmen zu vereinfachen:

Unsere Liste hat nun also $n+1$ Elemente. Nun liegt jedes Listenglied in eiener Speicherzelle:

Die Lage sieht also eher so aus:

Beachten Sie, dass in der ersten Zeile Adressen und in der zweiten Zeile Werte stehen. In unserer Vorstellung kann jede Speicherzelle $i$ zwei Datensätze enthalten, nämlich den Nachfolger $\text{succ}[i]$ und den Wert $\text{val}[i]$.

Pointer Jumping

Der erste Algorithmus, den wir untersuchen werden, verwendet ein als Pointer Jumping bekanntes Prinzip. Wir ordnen jeder Speicherzelle einen Prozessor zu. Wir haben also insgesamt $n+1$ (im obigen Beispiel 9) Prozessoren. Jeder Prozessor führt nun pro Zeitschritt folgende Anweisungen aus:

Wir illustrieren diesen Algorithmus anhand des obigen Beispiels:

Überzeugen Sie sich, dass dies tatsächlich die korrekten Werte sind. Wie analysieren wir diesen Algorithmus? Wir betrachten für die "Länge" des Pointers $j=\text{succ}(i)$ zu einem Zeitpunkt. Wenn in Zelle $i$ das $a$-te Listenelement steht und in $j$ das $b$-te, dann sei $b-a$ die Länge des Pointers. Am Anfang hat jeder Pointer Länge 1. Nach $t$ Zeitschritten hat jeder Pointer Länge $2^t$ oder zeigt bereits auf das letzte Element. Nach $\lceil \log n\rceil$ Schritten hat jeder Pointer Länge mindestens $n$ oder zeigt auf das letzte Element (also Element $n+1$ in der Liste). In anderen Worten: alle Zeiger deuten auf das letzte Element. Wie entwickelt sich $\text{val}(i)$? Seien $v_1,\dots ,v_n,v_{n+1}$ die Werte der Listenelemente (in der Reihenfolge, in der sie in der verketteten Liste auftreten, also mit $v_{n+1}=0$). Wir setzen als Konvention $0=v_{n+2}=v_{n+3}=\dots$. Sei weiterhin $i$ das $a$-te Element der Liste. Dann gilt nach $t$ abgeschlossenen Zeitschritten

$$\begin{array}{r}\text{val}(i)=v_a+\cdots +v_{a+2^t-1}.\end{array}$$

$\text{val}(i)$ ist also die Summe der nächsten $2^t$ Listenelemente, angefangen mit Element an Stelle $a$. Am Anfang ist $t=0$, und somit gilt anfangs $\text{val}(i)=v_a$ wie gewohnt. Nach $\lceil \log n\rceil$ Zeitschritten gilt $\text{val}(i)=v_a+v_{a+1}+\cdots +v_{a+n-1}$. Da $a+n-1\ge n$ gilt, ist diese Summe genau $v_a+v_{a+1}+\cdots +v_n$, also die gewünschte Suffixsumme.

Rechnermodell?

Sie haben vielleicht schon bemerkt: der Schritt Schaue an gegebener Speicheradresse nach und tu dann dies und das passt nicht in unsere bisherige Schaltkreis-Metapher. Die greift nur, so lange die "Adressen" von vornherein feststehen und nicht von den Input-Daten selbst abhängen. Wir haben nun ein neues Modell, in welchem der Input in einem gemeinsamen Speicher liegt, und jeder Prozessor kann in konstanter Zeit auf eine Speicherzelle lesend oder schreibend zugreifen. Dieses Modell ist flexibler als das Schaltkreis-Modell des letzten Teilkapitels, allerdings auch schwieriger exakt zu definieren. Hierfür nehmen wir uns im nächsten Kapitel Zeit.