Quelltext der Seite Präfixsumme

In der [[Informatik]] ist die '''Präfixsumme''' einer Folge von Zahlen ''a''<sub>0</sub>, ''a''<sub>1</sub>, ''a''<sub>2</sub>, … die Zahlenfolge ''s''<sub>0</sub>, ''s''<sub>1</sub>, ''s''<sub>2</sub>, … ihrer [[Partialsumme]]n:
: ''s''<sub>0</sub> = ''a''<sub>0</sub>
: ''s''<sub>1</sub> = ''a''<sub>0</sub> + ''a''<sub>1</sub>
: ''s''<sub>2</sub> = ''a''<sub>0</sub> + ''a''<sub>1</sub>+ ''a''<sub>2</sub>
: …

Beispielsweise ist die Präfixsumme der [[natürliche Zahl|natürlichen Zahlen]] die Folge der [[Dreieckszahl]]en:
{| class="wikitable" style="margin-left:2em"
|-
| '''Eingabefolge''' || &nbsp;1 || &nbsp;2 || &nbsp;3 || &nbsp;4 || &nbsp;5 || &nbsp;6 || …
|-
| '''Präfixsumme''' || &nbsp;1 || &nbsp;3 || &nbsp;6 || 10 || 15 || 21 || …
|}

Die Präfixsumme ist mit einer einfachen Schleife [[Sequentialisierung|sequenziell]] berechenbar, indem mit der Formel
: ''s<sub>i</sub>'' = ''s''<sub>''i''−1</sub> + ''a<sub>i</sub>''
für ''i''>0 jeder Summenwert sukzessive aufaddiert wird. Die Präfixsumme bildet die Grundlage für Algorithmen wie den [[Countingsort]].<ref name="clrs">{{Literatur |Autor=Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein |Titel=Introduction to Algorithms |Auflage=2 |Verlag=MIT Press, McGraw-Hill |Datum=2001 |ISBN=0-262-03293-7 |Kapitel=8.2 Counting Sort |Seiten=168–170}}</ref>
Sie kann statt der Summierung als Basisoperation eine allgemeine [[Assoziativgesetz|assoziative]] [[Zweistellige Verknüpfung|binäre Operation]] verwenden, womit sie beispielsweise zur [[Polynominterpolation]] oder zur [[Zeichenkette|Stringbearbeitung]] eingesetzt<ref name="blelloch11">{{Literatur |Autor=Guy Blelloch |Titel=Prefix Sums and Their Applications (Lecture Notes) |Verlag=Carnegie Mellon University |Datum=2011 |Online=[http://www.cs.cmu.edu/afs/cs/academic/class/15750-s11/www/handouts/PrefixSumBlelloch.pdf Online]}}</ref><ref name="callahan1995">{{Literatur |Autor=Paul Callahan, S. Rao Kosaraju |Titel=A Decomposition of Multi-Dimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields |Sammelwerk=Journal of the ACM |Band=42 |Nummer=1 |Datum=1995}}</ref>
und in der [[Funktionale Programmierung|funktionalen Programmierung]] auf [[Funktion höherer Ordnung|Funktionen höherer Ordnung]] angewandt werden kann; in diesem Falle wird sie auch '''Scan''' genannt. Da die Präfixsumme mit dem Fork-join-Modell<ref name="fork-join">A. de Vries (2014): [http://www4.fh-swf.de/media/downloads/fbtbw/download_8/devries_1/Funktionen-Streams.pdf Funktionale Programmierung und Streams in Java] (PDF) Einführendes Vorlesungsskript Wirtschaftsinformatik, [[FH Südwestfalen|FH Südwestfalen Hagen]], §&nbsp;3</ref> zudem effizient auf [[Mehrkernprozessor]]systemen und [[Rechnercluster]]n berechnet werden kann, spielt sie in Betrachtungen zu [[Paralleler Algorithmus|parallelen Algorithmen]] eine wichtige theoretische und praktische Rolle, als zu lösendes Testproblem ebenso wie als Subroutine wichtiger paralleler Algorithmen.<ref name="lf80" /><ref name="tv85" /><ref name="Prefix.book.92">{{Literatur |Autor=S. Lakshmivarahan, S.K. Dhall |Titel=Parallelism in the Prefix Problem |Verlag=[[Oxford University Press]] |Datum=1994 |ISBN=0-19-508849-2}}</ref>

Mathematisch kann die Berechnung der Präfixsumme von endlichen auf unendliche Folgen verallgemeinert werden. Sie stellt dann eine [[Reihe (Mathematik)|Reihe]] dar. Die Präfixsummierung ist ein [[linearer Operator]] auf einem [[Vektorraum]] endlicher oder unendlicher Folgen. Seine Inverse ist ein [[Differenz-Operator]].

== Präfixoperationen (''Scans'') von Funktionen höherer Ordnung ==
Die eigentliche Präfixsumme basiert auf der [[Zweistellige Verknüpfung|binären Operation]] der [[Addition]]. In der [[Funktionale Programmierung|funktionalen Programmierung]] kann die Präfixsumme auf jede binäre [[Assoziativgesetz|assoziative]] Operation verallgemeinert werden, also statt einer Präfix''summe'' eine Präfix''operation'' darstellen. (Allerdings wird oft der Begriff „Präfixsumme“ auch dafür verwendet.) Die aus dieser Verallgemeinerung resultierende Präfixoperation ist eine [[Funktion höherer Ordnung]] und wird auch '''Scan''' genannt. Zum Beispiel kann die Folge der [[Fakultät (Mathematik)|Fakultäten]] (''a<sub>k</sub>'') als Präfixprodukt berechnet werden, indem die Addition durch die Multiplikation ersetzt wird:
{| class="wikitable" style="margin-left:2em"
|- 
|'''Eingabefolge''' || &nbsp;1 || &nbsp;2 || &nbsp;3 || &nbsp;4 || &nbsp;&nbsp;5 || &nbsp;&nbsp;6 || …
|- 
|'''Präfixprodukt''' || &nbsp;1 || &nbsp;2 || &nbsp;6 || 24 || 120 || 720 || …
|}
Die Scan-Operation ist daher ähnlich der [[MapReduce|Reduce-Operation]], allerdings liefert ''Scan'' die gesamte Folge der Partialoperationen, während ''Reduce'' nur den Wert der letzten Partialoperation als Ergebnis liefert.

In [[Haskell (Programmiersprache)|Haskell]] gibt es zwei Varianten von ''Scan'', nämlich <code>scanl</code> und <code>scanl1</code>.<ref>{{Literatur |Titel=Haskell 98 Language and Libraries: The Revised Report |Datum=2002 |Kapitel=Standard Prelude |Online=[http://www.haskell.org/onlinereport/standard-prelude.html Online]}}</ref> Die prozeduralen [[Message Passing Interface|MPI]]-Bibliotheken bieten eine Operation <code>MPI_Scan</code> an, um eine Scan-Operation zwischen vernetzten Processoreinheiten zu berechnen. Die Programmiersprache [[C++]] hat eine Funktion <code>partial_sum</code> in ihrer Standardbibliothek, welche, trotz ihres Namens, eine Scan-Operation mit einer beliebigen binären Operation ausführt. Die Programmiersprache [[Java (Programmiersprache)|Java]] bietet (ab der Version 1.8) in dem Standardpaket <code>java.util.Arrays</code> eine Methode <code>parallelPrefix</code> in mehreren Varianten an, die neben dem zu bearbeitenden Array einen binären Operator erwartet.<ref name="java">[http://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html Java SE 8 API] (2014)</ref> Die Präfixsumme eines Arrays <code>a[k]</code> wird damit durch die folgende Anweisung berechnet und in dem Eingabearray gespeichert:
<syntaxhighlight lang="java">
Arrays.parallelPrefix(a, (x,y) -> x + y);
</syntaxhighlight>
Der binäre Operator ist hier als [[Lambda-Ausdruck]], also eine [[anonyme Funktion]] mit zwei Parametern angegeben. Entsprechend kann die Fakultät nach obigem Beispiel als Präfixprodukt
<syntaxhighlight lang="java">
Arrays.parallelPrefix(a, (x,y) -> x * y);
</syntaxhighlight>
programmiert werden.

== Parallele Berechnung ==
[[Datei:Prefix sum 16.svg|mini|Abfolge der Rechenschritte einer parallelen Präfixsumme mit 16 Eingabeeinträgen]]
Mit Hilfe des Fork-join-Modells<ref name="fork-join" /> kann eine Präfixsumme mit den folgenden Schritten effizient parallel berechnet werden.<ref name="lf80" /><ref name="offman" /><ref name="krapchenko" />
# Berechne die Summen der aufeinanderfolgenden Paareinträge, in denen der erste Eintrag jeweils einen geraden Index hat: ''z''<sub>0</sub> = ''a''<sub>0</sub> + ''a''<sub>1</sub>, ''z''<sub>1</sub> = ''a''<sub>2</sub> + ''a''<sub>3</sub>, ….
# Berechne rekursiv die Präfixsumme ''w''<sub>0</sub>, ''w''<sub>1</sub>, ''w''<sub>2</sub>, … der Folge ''z''<sub>0</sub>, ''z''<sub>1</sub>, ''z''<sub>2</sub>, ….
# Drücke jeden Term der Ergebnisfolge ''s''<sub>0</sub>, ''s''<sub>1</sub>, ''s''<sub>2</sub>, … als die Summe von höchstens zwei Termen dieser Zwischenfolge aus: ''y''<sub>0</sub> = ''a''<sub>0</sub>, ''y''<sub>1</sub> = ''z''<sub>0</sub>, ''y''<sub>2</sub> = ''z''<sub>0</sub> + ''a''<sub>2</sub>, ''y''<sub>3</sub> = ''w''<sub>0</sub> etc. Nach dem ersten Wert ist jede sukzessive Zahl ''y<sub>i</sub>'' entweder eine Kopie des Werts mit halb so großem Index in der Folge ''w'', oder sie ist der vorherige Wert plus einem Wert in der originalen Folge ''a''.
Hat die Eingabefolge ''n'' Einträge, so schreitet die Rekursion bis zu einer Tiefe von ''O''(log ''n'') fort, was ebenso die Begrenzung der parallelen Laufzeit darstellt. Die Anzahl der Schritte des Algorithmus beträgt ''O''(''n'') und kann auf einer [[Parallel Random Access Machine|PRAM]] mit ''O''(''n''/log ''n'') Prozessoren implementiert werden, indem in Runden, in denen mehr Einträge als Prozessoren vorhanden sind, einem Prozessor einfach mehrere Indizes zugewiesen werden.<ref name="lf80" />

Parallele Algorithmen für Präfixsummen können auf andere Präfixoperationen (Scans) [[Assoziativgesetz|assoziativer]] [[Zweistellige Verknüpfung|binärer Operationen]] verallgemeinert werden.<ref name="lf80" /><ref name="tv85" /> Sie laufen effizient auf paralleler Hardware wie [[Mehrkernprozessor]]en, [[Global Processing Unit|GPU]]'s oder [[Rechnercluster]]n ab.<ref>{{Literatur |Autor=Shubhabrata Sengupta, Mark Harris, Yao Zhang, John D. Owens |Titel=Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware |Datum=2007 |Kapitel=Scan primitives for GPU computing |Seiten=97–106 |Online=[http://graphics.idav.ucdavis.edu/publications/print_pub?pub_id=915 Online]}}</ref> Viele parallele Implementierungen verwenden dazu zwei Durchgänge: im ersten Durchgang werden die partiellen Präfixsummen auf jeder Prozessoreinheit berechnet; die Präfixsumme dieser Teilsummen wird dann berechnet und zum zweiten Durchgang an die einzelnen Prozessoreinheiten zurückgesendet, die nun mit dem bekannten Präfix als Anfangswert weiterrechnen. Asymptotisch angenähert erfordert diese Methode etwa zwei Lese- und eine Schreiboperation pro Eintrag.

== Anwendungen ==
* [[Countingsort]] ist ein Algorithmus zur Sortierung einer Folge ganzer Zahlen, der die Präfixsumme eines [[Histogramm]]s der Schlüsselhäufigkeiten verwendet, um die Position jedes Schlüssels in der sortierten Ausgabefolge zu bestimmen. Der Algorithmus hat lineare Zeitkomplexität ''O(n)'' für ganzzahlige Schlüsselwerte, die kleiner als die Anzahl Einträge sind, und ebenso lineare Speicherkomplexität. Countingsort wiederum kann eine von zwei möglichen Subroutinen für den [[Radixsort]].<ref name="clrs" />
* [[List ranking]] ist das Problem, eine [[Liste (Datenstruktur)|verkettete Liste]] in ein [[Feld (Datentyp)|Array]] derselben Elementfolge zu transformieren. Es kann durch Berechnung einer Präfixsumme der Folge 1, 1, 1, … und der Zuordnung jedes Listenelements zu seinem Präfixsummenwert als Array-Index. Durch Kombination von List Ranking, Präfixsumme und [[Eulerkreisproblem|Eulerkreise]] können viele wichtige Probleme an [[Baum (Graphentheorie)|Baumstrukturen]] effizient durch parallele Algorithmen gelöst werden.<ref name="tv85">{{Literatur |Autor=Robert E. Tarjan, Uzi Vishkin |Titel=An efficient parallel biconnectivity algorithm |Sammelwerk=[[SIAM Journal on Computing]] |Band=14 |Nummer=4 |Datum=1985 |Seiten=862–874 |DOI=10.1137/0214061}}</ref>
* Parallele Präfixsummenalgorithmen können für den Entwurf von [[Addierwerk]]en verwendet werden, also Boole’schen [[Schaltnetz]]en, die zwei ''n''-stellige [[Binärzahl]]en addieren. Hierbei kann eine Folge von [[Übertragbit]]s als eine Präfixoperation der [[Konjunktion (Logik)|Konjunktion]] <math>f(x,y) = x \wedge y</math> der Folge von Bitpaaren berechnet werden; jedes Bit der Ergebniszahl ist dann ein [[XOR]] der beiden Eingabebits und des zugehörigen Übertragbits. Damit kann man ein paralleles Addierwerk für ''n''-stellige Binärzahlen mit ''O''(''n'') [[Logikgatter]]n and ''O''(log ''n'') Rechenschritten realisieren.<ref name="lf80">{{Literatur |Autor=R. E. Ladner, M. J. Fischer |Titel=Parallel Prefix Computation |Sammelwerk=[[Journal of the ACM]] |Band=27 |Nummer=4 |Datum=1980 |Seiten=831–838 |DOI=10.1145/322217.322232}}</ref><ref name="offman">{{Literatur |Autor=Yuri Petrovich Ofman |Titel=Об алгоритмической сложности дискретных функций |Sammelwerk=[[Proceedings of the USSR Academy of Sciences|Doklady Akademii Nauk SSSR]] |Band=145 |Nummer=1 |Datum=1962 |Sprache=ru |Seiten=48–51 |Kommentar=English translation, ''On the algorithmic complexity of discrete functions''. In: ''Soviet Physics Doklady'', 7, S. 589–591 1963}}</ref><ref name="krapchenko">{{Literatur |Autor=V. M. Khrapchenko |Titel=Asymptotic Estimation of Addition Time of a Parallel Adder |Sammelwerk=Problemy Kibernet. |Band=19 |Datum=1967 |Sprache=ru |Seiten=107–122 |Kommentar=English translation in: ''Syst. Theory Res.'', 19, 1970, S. 105–122}}</ref>
* Der [[Gray-Code]] einer ganzen [[Binärzahl|binären Zahl]] ''n'' kann einfach durch Berechnung des [[XOR]] von ''n'' und ''n''/2 (also der [[Arithmetische Verschiebung|Rechtsverschiebung]] von ''n'' um ein Bit) gebildet werden. Die inverse Operation, also die Dekodierung eines Gray-Codes ''x'' in eine Binärzahl, kann als Präfixsumme der Bits von ''x''&nbsp;[[modulo]]&nbsp;2 ausgedrückt werden, also als Präfixoperation mit der assoziativen XOR-Funktion <math>f(x_1,x_2) = x_1 \oplus x_2</math>.<ref>{{Literatur |Autor=Henry S. Warren |Titel=Hacker’s Delight |Verlag=Addison-Wesley |Datum=2003 |ISBN=978-0-201-91465-8 |Seiten=236 |Online=[http://books.google.com/books?id=iBNKMspIlqEC&pg=PA236 Google Books]}}</ref>
* Parallele Präfixprodukte (mit der Multiplikation als assoziative Operation) können als Baustein von schnellen parallelen Algorithmen zur [[Polynominterpolation]] eingesetzt werden. Insbesondere können sie zur Koeffizientenberechnung nach dem Schema der dividierten Differenz im [[Polynominterpolation#Newtonscher Algorithmus|Newton’schen Algorithmus]] verwendet werden.<ref>{{Literatur |Autor=O. Eğecioğlu, E. Gallopoulos, C. Koç |Titel=A parallel method for fast and practical high-order Newton interpolation |Band=30 |Nummer=2 |Datum=1990 |Seiten=268–288 |DOI=10.1007/BF02017348 |Online=[http://www.springer.com/mathematics/computational+science+%26+engineering/journal/10543 BIT Computer Science and Numerical Mathematics]}}</ref> Ähnlich kann die [[Hermiteinterpolation|Hermite-Interpolation]] oder die [[Interpolation]] von [[Funktion (Mathematik)|Funktionen]] mit Hilfe der [[Vandermonde-Matrix|Vandermonde-Matrizen]] effizient parallel berechnet werden.<ref>{{Literatur |Autor=O. Eğecioğlu, E. Gallopoulos, C. Koç |Titel=Fast computation of divided differences and parallel Hermite interpolation |Sammelwerk=Journal of Complexity |Band=5 |Datum=1989 |Seiten=417–437 |DOI=10.1016/0885-064X(89)90018-6}}</ref>

== Siehe auch ==
* [[Reihe (Mathematik)]]

== Weblinks ==
* {{MathWorld |id=CumulativeSum |title=Cumulative Sum}}

== Einzelnachweise ==
<references />

{{SORTIERUNG:Prafixsumme}}

[[Kategorie:Algorithmus]]
[[Kategorie:Computercluster]]
[[Kategorie:Parallelverarbeitung]]
[[Kategorie:Theoretische Informatik]]
[[Kategorie:Verteiltes System]]