--- title: 'Parallele Berechnung von Präfixen über Arrays-Klasse in Java 8' url: 'https://www.tutego.de/blog/javainsel/2014/01/parallele-berechnung-von-prfixen-ber-arrays-klasse-in-java-8' markdown: 'https://www.tutego.de/blog/javainsel/2014/01/parallele-berechnung-von-prfixen-ber-arrays-klasse-in-java-8.md' date: '2014-01-06' description: 'Stehen mehrere Prozessoren bzw. Kerne zur Verfügung können einige Berechnungen bei Feldern parallelisiert werden. Eine Algorithmus nennt sich parallele Präfix-Berechnung und basiert auf der der Idee, dass eine assoziative Funktion – nennen wir sie f – auf eine bestimmte Art und Weise auf Elemente e…' taxonomy: category: - Insel - 'Java 8' --- # Parallele Berechnung von Präfixen über Arrays-Klasse in Java 8 ![Illustration einer tropischen Insel mit Palmen und einem hohen Berg](https://www.tutego.de/blog/javainsel/user/themes/tutego/images/insel-cover.jpg)# Java Blog für Programmierer [Java Blog für Programmierer](https://www.tutego.de/blog/javainsel/) ## Parallele Berechnung von Präfixen über Arrays-Klasse in Java 8 06.01.2014 · [Christian Ullenboom](https://www.tutego.de/blog/javainsel/author/admin/) Stehen mehrere Prozessoren bzw. Kerne zur Verfügung können einige Berechnungen bei Feldern parallelisiert werden. Eine Algorithmus nennt sich parallele Präfix-Berechnung und basiert auf der der Idee, dass eine assoziative Funktion – nennen wir sie f – auf eine bestimmte Art und Weise auf Elemente eines Feldes – nennen wir es a – angewendet wird, nämlich so: - a\[0\] - f(a\[0\], a\[1\]) - f(a\[0\], f(a\[1\], a\[2\])) - f(a\[0\], f(a\[1\], f(a\[2\], a\[3\]))) - … - f(a\[0\], f(a\[1\], … f(a\[n-2\], a\[n-1\])…)) In der Aufzählung sieht das etwas verwirrend aus, daher soll ein praktisches Beispiel zum Verständnis anregen. Das Feld sei \[1, 3, 0, 4\] und die binäre Funktion die Addition. **Index** **Funktion** **Ergebnis** 0 a\[0\] 1 1 a\[0\] + a\[1\] 1 + 3 = 4 2 a\[0\] + (a\[1\] + a\[2\]) 1 + (3+0) = 4 3 a\[0\] + (a\[1\] + (a\[2\] + a\[3\])) 1 + (3+(0+4)) = 8 Präfix-Berechnung vom Feld \[1, 3, 0, 4\] mit Additions-Funktion Auf den ersten Blick wirkt das wenig spannend, doch kann der Algorithmus parallelisiert werden und somit im Besten Fall in logarithmischer Zeit (mit n Prozessoren) gelöst werden. Voraussetzung dafür ist allerdings eine assoziative Funktion, wie Summe, Maximum, … Ohne genau ins Detail zu gehen könnten wir uns vorstellen, dass ein Prozessor/Kern 0+4 berechnet, ein anderer zeitgleich 1+3, und dann das Ergebnis zusammengezählt wird. Beispiel. Das Beispiel unserer Präfix-Berechnung mit Hilfe einer Methode aus `Arrays`: ```java int[] array = {1, 3, 0, 4}; Arrays.parallelPrefix( array, (a, b) -> a + b ); System.out.println( Arrays.toString( array ) ); // [1, 4, 4, 8] ``` Die Implementierung nutzt eine fortgeschrittene Syntax aus Java 8, die Lambda-Ausdrücke. statt (a + b) -> a + b kann es sogar mit `Integer`::sum noch verkürzt werden. Ein weiteres Beispiel: Finde das Maximum in einer Menge von Fließkommazahlen: ```java double[] array = {4.8, 12.4, -0.7, 3.8 }; Arrays.parallelPrefix( array, Double::max ); System.out.println( array[array.length -1 ] ); // 12.4 ``` Das Beispiel nutzt schon die Methode, die `Arrays` für die parallele Präfix-Berechnung bietet: class `java.util.Arrays` - `static void parallelPrefix(int[] array, IntBinaryOperator op)` - `static void parallelPrefix(int[] array, int fromIndex, int toIndex, IntBinaryOperator op)` - `static void parallelPrefix(long[] array, LongBinaryOperator op)` - `static void parallelPrefix(long[] array, int fromIndex, int toIndex, LongBinaryOperator op)` - `static void parallelPrefix(double[] array, DoubleBinaryOperator op)` - `static void parallelPrefix(double[] array, int fromIndex, int toIndex, DoubleBinaryOperator op)` - `static void parallelPrefix(T[] array, BinaryOperator op)` - `static void parallelPrefix(T[] array, int fromIndex, int toIndex, BinaryOperator op)` Kategorien: [Insel](https://www.tutego.de/blog/javainsel/category/insel/), [Java 8](https://www.tutego.de/blog/javainsel/category/java-8/) [← Alle Beiträge](https://www.tutego.de/blog/javainsel/) --- ## Navigation - Previous: [Internationalisierung von Log-Methoden mit setResourceBundle(…) und logrb(…)](https://www.tutego.de/blog/javainsel/2014/01/internationalisierung-von-log-methoden-mit-setresourcebundle-und-logrb.md) - Next: [Beispiel ListResourceBundle](https://www.tutego.de/blog/javainsel/2014/01/beispiel-listresourcebundle.md)