Stehen mehrere Prozessoren bzw. Kerne zur Verf\u00fcgung k\u00f6nnen einige Berechnungen bei Feldern parallelisiert werden. Eine Algorithmus nennt sich parallele Pr\u00e4fix-Berechnung und basiert auf der der Idee, dass eine assoziative Funktion \u2013 nennen wir sie f \u2013 auf eine bestimmte Art und Weise auf Elemente eines Feldes \u2013 nennen wir es a \u2013 angewendet wird, n\u00e4mlich so: <\/p>\n
\u00b7 a[0] <\/p>\n
\u00b7 f(a[0], a[1]) <\/p>\n
\u00b7 f(a[0], f(a[1], a[2])) <\/p>\n
\u00b7 f(a[0], f(a[1], f(a[2], a[3]))) <\/p>\n
\u00b7 \u2026 <\/p>\n
\u00b7 f(a[0], f(a[1], \u2026 f(a[n-2], a[n-1])\u2026)) <\/p>\n
In der Aufz\u00e4hlung sieht das etwas verwirrend aus, daher soll ein praktisches Beispiel zum Verst\u00e4ndnis anregen. Das Feld sei [1, 3, 0, 4] und die bin\u00e4re Funktion die Addition. <\/p>\n
| \n Index<\/b><\/p>\n<\/td>\n | \n Funktion<\/b><\/p>\n<\/td>\n | \n Ergebnis<\/b><\/p>\n<\/td>\n<\/tr>\n 0<\/p>\n<\/td>\n a[0]<\/p>\n<\/td>\n 1<\/p>\n<\/td>\n<\/tr>\n 1<\/p>\n<\/td>\n a[0] + a[1]<\/p>\n<\/td>\n 1 + 3 = 4<\/p>\n<\/td>\n<\/tr>\n 2<\/p>\n<\/td>\n a[0] + (a[1] + a[2])<\/p>\n<\/td>\n 1 + (3+0) = 4<\/p>\n<\/td>\n<\/tr>\n 3<\/p>\n<\/td>\n a[0] + (a[1] + (a[2] + a[3]))<\/p>\n<\/td>\n 1 + (3+(0+4)) = 8<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Pr\u00e4fix-Berechnung vom Feld [1, 3, 0, 4] mit Additions-Funktion <\/p>\n 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\u00f6st werden. Voraussetzung daf\u00fcr ist allerdings eine assoziative Funktion, wie Summe, Maximum, \u2026 Ohne genau ins Detail zu gehen k\u00f6nnten wir uns vorstellen, dass ein Prozessor\/Kern 0+4 berechnet, ein anderer zeitgleich 1+3, und dann das Ergebnis zusammengez\u00e4hlt wird. <\/p>\n Beispiel. Das Beispiel unserer Pr\u00e4fix-Berechnung mit Hilfe einer Methode aus Arrays: <\/p>\n int[] array = {1, 3, 0, 4}; <\/p>\n Arrays.parallelPrefix<\/b>( array, (a, b) -> a + b ); <\/p>\n System.out.println( Arrays.toString( array ) ); \/\/ [1, 4, 4, 8] <\/p>\n Die Implementierung nutzt eine fortgeschrittene Syntax aus Java 8, die Lambda-Ausdr\u00fccke. statt (a + b) -> a + b kann es sogar mit Integer::sum noch verk\u00fcrzt werden. <\/p>\n Ein weiteres Beispiel: Finde das Maximum in einer Menge von Flie\u00dfkommazahlen: <\/p>\n double[] array = {4.8, 12.4, -0.7, 3.8 }; <\/p>\n Arrays.parallelPrefix<\/b>( array, Double::max ); <\/p>\n System.out.println( array[array.length -1 ] ); \/\/ 12.4 <\/p>\n Das Beispiel nutzt schon die Methode, die Arrays f\u00fcr die parallele Pr\u00e4fix-Berechnung bietet: <\/p>\n class java.util.Arrays <\/p>\n \u00a7 static void parallelPrefix(int[] array, IntBinaryOperator op) <\/p>\n \u00a7 static void parallelPrefix(int[] array, int fromIndex, int toIndex, IntBinaryOperator op) <\/p>\n \u00a7 static void parallelPrefix(long[] array, LongBinaryOperator op) <\/p>\n \u00a7 static void parallelPrefix(long[] array, int fromIndex, int toIndex, LongBinaryOperator op) <\/p>\n \u00a7 static void parallelPrefix(double[] array, DoubleBinaryOperator op) <\/p>\n \u00a7 static void parallelPrefix(double[] array, int fromIndex, int toIndex, DoubleBinaryOperator op) <\/p>\n \u00a7 static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) <\/p>\n \u00a7 static <T> void parallelPrefix(T[] array, int fromIndex, int toIndex, BinaryOperator<T> op)<\/p>\n","protected":false},"excerpt":{"rendered":" Stehen mehrere Prozessoren bzw. Kerne zur Verf\u00fcgung k\u00f6nnen einige Berechnungen bei Feldern parallelisiert werden. Eine Algorithmus nennt sich parallele Pr\u00e4fix-Berechnung und basiert auf der der Idee, dass eine assoziative Funktion \u2013 nennen wir sie f \u2013 auf eine bestimmte Art und Weise auf Elemente eines Feldes \u2013 nennen wir es a \u2013 angewendet wird, n\u00e4mlich […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":"","_links_to":"","_links_to_target":""},"categories":[11,66],"tags":[],"class_list":["post-2616","post","type-post","status-publish","format-standard","hentry","category-insel","category-java-8"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2616","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/comments?post=2616"}],"version-history":[{"count":1,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2616\/revisions"}],"predecessor-version":[{"id":2617,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2616\/revisions\/2617"}],"wp:attachment":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/media?parent=2616"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/categories?post=2616"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/tags?post=2616"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} |