Freitag, Juni 16, 2017

Java 8 Collection Beispiele | Stream#reduce()

Thema heute: Die unterschiedlichen #reduce(...) Methoden der Klasse java.util.Stream. Betrachtet werden die Methoden:

  1. Optional<T> java.util.Stream#reduce(BinaryOperator<T> accumulator)
    
  2. T java.util.Stream#reduce(T identity,
                              BinaryOperator<T> accumulator)
    
  3. <U> U java.util.Stream#reduce(U identity,
                                  BiFunction<U,? super T, U> accumulator,
                                  BinaryOperator<U> combiner)

Gemein ist allen drei Varianten der Parameter accumulator. In den ersten beiden Varianten ist der accumulator vom Typ BinaryOperator<T>. Der BinaryOperator<T> nimmt zwei Werte entgegen und liefert ein Ergebnis zurück. Die beiden Eingabeparameter und der Rückgabewert sind vom gleichen Typ und entsprechen dem Typ des Streams. Damit sind diese beiden Varianten zu verwenden, wenn es um z.B. um die Addition von Integer Werten aus einem Stream geht. Also immer dann, wenn das Akkumulationsergebnis vom gleichen Typ ist wie der Stream.

Sollen die Längen der Strings aus einem Stream addiert werden, kommt die dritte Ausprägung ins Spiel: Hier entspricht der accumulator einer BiFunction<U,? super T, U>. Der zweite Parameter ist ein Element aus dem Stream. Der erste Parameter das Ergebnis aus der letzten Akkumulation. Entsprechend dem Beispiel wäre also der erste Parameter ein Integer und der zweite Parameter ein String. Das Ergebnis ist dann vom Typ Integer. Für das erste Element aus dem Stream wird bei Anwendung der Akkumulation als erster Parameter (Erinnerung: Die Summe aller String-Längen) identity verwendet. Für das Beispiel wäre dies sinnvollerweise die 0. Der dritte Parameter combiner wird bei einer parallelen Verarbeitung des Streams benötigt. In den ersten beiden Varianten kann der Akkumulator als Combiner verwendet werden, da Eingabe- und Ausgabetyp die gleichen sind. Um bei dem Beispiel zu bleiben: Zwei Threads teilen sich die Bearbeitung des Streams. Es werden zwei Integer Werte ermittelt, die jeweils die Länge der Strings aus dem jeweiligen Teil-Stream repräsentieren. Diese beiden Integer Werte werden vom Combiner addiert.

Mathematisch ausgedrückt ist es vielleicht am anschaulichsten. Der zentrale Parameter accumulator repräsentiert eine Funktion (In der Java Welt ist es entweder ein java.util.function.BinaryOperator oder ein java.util.function.BiFunction) zur Berechnung der Reduktion. Allen drei Methoden ist dieser Parameter gemein. Es sei f() eine Funktion. f() wird auf alle Elemente des Stream rekursiv angewendet.

f(f(f(a0, a1), a2), a3)
Ein andere Darstellung ergibt sich, wenn statt einer Funktion ein (Bi-)Operator op verwendet wird.
a0 op a1 op a2 ...
bzw. ganz allgemein
ai op ai + 1

Die binäre Funktion/der binäre Operator sollte folgenden funktionalen Anforderungen genügen:

  • assoziativ: a op (b op c) = (a op b) op c. Darunter fallen solche Operationen wie die Addition, Multiplikation, Min, Max. Die Subtraktion ist z.B. nicht assoziativ: (20-5)-4 ≠ 20-(5-4). Das gleiche gilt für die Division. Eine Stolperfalle für (hastige) Codeänderungen?
  • Nicht störend (non-interfering). Wie kann man das verstehen? Auf "NOSID-Java 8 stream reduce vs collect" findet sich eine gute Erklärung: Die reduce-Methode eignet sich ausschließlich für Reduktionen mit reinen Funktionen. Damit sind Funktionen gemeint, die beim Aufruf weder ihren eigenen Zustand, den Zustand der Übergabeparameter noch irgendwelchen global sichtbaren Zustand ändern. Sie geben lediglich eine Referenz auf ein Objekt zurück, das üblicherweise entweder neu erzeugt wird oder zumindest unveränderlich ist – in jedem Fall aber keine Auswirkungen auf den sonstigen Programmzustand hat.
  • zustandslos. Der accumulator darf keinen inneren, äußeren oder globalen Zustand besitzen. Passt irgendwie gut zu dem letzten Punkt.
Folgt man diesen Anforderungen erhält man eine im mathematischen Sinne echte Funktion.


Fall 1

Optional<T> java.util.Stream#reduce(BinaryOperator<T> accumulator)

Für die #reduce(...) aus 1 ergeben sich folgende Regeln für die Ergebnisberechnung:

  • Leere Streams erzeugen ein leeres Ergebnis. Deswegen wird ein Optional als Rückgabeparameter verwendet.
  • Ein 1-elementiger Stream liefert das erste und einzige Element zurück. Die Akkumulator Funktion wird auf das Element nicht angewendet!
  • Auf mehrelementige Streams wird die BinaryOperator Funktion, wie beschrieben, angewendet.


Fall 2

T java.util.Stream#reduce(T identity, BinaryOperator<T> accumulator)

Das #reduce(...) aus 2 bekommt einen weiteren Parameter identity. Mathematisch erfüllt es den folgenden Zweck: a op id = a. Für die Addition wäre das z.B. die 0 oder für die Multiplikation die 1.

  • Leere Streams liefern die identity zurück. Im Gegensatz zu 1 kann das Optional als Rückgabeparameter entfallen.
  • Für einen einelementigen Stream wird der Akkumulator mit den Parametern identity und dem Stream-Element aufgerufen.
  • Auf mehrelementige Streams wird die BinaryOperator Funktion, wie beschrieben, angewendet. Die erste Akkumulation wird mit Hilfe der identity berechnet.


Fall 3

<U> U java.util.Stream#reduce(U identity,
                              BiFunction<U,? super T, U> accumulator,
                              BinaryOperator<U> combiner)

Dieser Fall wird benötigt, wenn der accumulator in der einfachen Form BinaryOperator<T> nicht verwendet werden kann. Siehe dazu oben in der Einleitung (Berechnung der Gesamtlänge aller Strings eines Streams).

  • Leere Streams liefern die identity zurück. Im Gegensatz zu 1 kann das Optional als Rückgabeparameter entfallen.
  • Für einen einelementigen Stream wird der Akkumulator mit den Parametern identity und dem Stream-Element aufgerufen. Der Rückgabetyp der Akkumulation ist ungleich dem Stream-Typ.
  • Mehrelementige Streams werden wie aus Fall 2 bekannt verarbeitet. Falls der Stream für die Parallelverarbeitung aufgeteilt wird, kommt der combiner ins Spiel. Dieser sorgt dafür, das die Teilergebnisse zu einem Gesamtergebnis kombiniert werden. Für die Fälle 1 und 2 kann der Akkumulator für die Zusammenführung der Teilergebnisse selbst verwendet werden. Die Parametertypen für ein Ein- und Ausgabe sind hier gleich. Laut Javadoc wird die folgende Anforderung an einen combiner gestellt:
    combiner.apply(u, accumulator.apply(identity, t)) == accumulator.apply(u, t)
    Was heißt das? Egal, ob der Combiner bei der Verarbeitung des Streams verwendet wird oder nicht, das Endergebnis der Stream-Reduktion/Akkumulation muss gleich sein.


Nach der ganzen Theorie jetzt ein wenig Code zum ausprobieren (In der Theorie sind Theorie und Praxis gleich):
import org.assertj.core.api.Assertions.*;
import org.junit.*;

List strings = Arrays.asList("Abc", "Def", "Ghi", "Jkl", "Mno");

assertThat(strings.stream().reduce(0,
        (Integer sum, String string) -> sum + string.length(),
        (Integer sum1, Integer sum2) -> sum1 + sum2).intValue()).isEqualTo(15);

Nach der ganzen Theorie nun einige Beispiele. In diesem Fall werden die Elemente einer Liste addiert. Ich empfehle, den Code per Copy und Paste in die bevorzugte IDE zu übernehmen und den Test einmal auszuführen. Das assertThat() stammt aus dem Package org.assertj.core.api.Assertions.*. Der Rest ist wohlbekannt.

assertThat(
    Arrays.asList(10, 20, 30)
          .stream()
          .reduce((result, element) -> result + element)
          .get())
          .isEqualTo(60);

assertThat(
    Arrays.asList(10)
          .stream()
          .reduce((result, element) -> result + element)
          .get())
          .isEqualTo(10);

// Bei der Addition zweier Elemente soll das Ergebnis um 1 erhöht
// werden.
assertThat(
    Arrays.asList(10, 20, 30)
          .stream()
          .reduce((result, element) -> result + element + 1)
          .get())
          .isEqualTo(62);
// Auf das erste Element wird die übergebene Funktion nicht angewendet!

assertThat(
    Arrays.asList(10)
          .stream()
          .reduce((result, element) -> result + element + 1)
          .get())
         .isEqualTo(10);
// Auf das erste Element wird die übergebene Funktion nicht angewendet!

// Nun zusätzlich mit dem Parameter identity
assertThat(
    Arrays.asList(10, 20, 30)
          .stream()
          .reduce(0, (result, element) -> result + element + 1))
          .isEqualTo(63);
// Die Funktion wird auf das erste Element angewendet. In diesem Fall
// wird der result Parameter mit dem identity Parameter vorbelegt.

assertThat(
    Arrays.asList(10)
         .stream()
         .reduce(0, (result, element) -> result + element + 1))
         .isEqualTo(11);

assertThat(
    Arrays.asList(666)
         .stream()
         .reduce(5, (result, element) -> result + element))
         .isEqualTo(671);
// 666 + 5 => 671


// Ein Beispiel mit Combiner:
assertThat(Arrays.asList("Abc", "Def", "Ghi", "Jkl", "Mno")
         .stream()
         .reduce(0, (Integer sum, String string) -> sum + string.length(),
                    (Integer sum1, Integer sum2) -> sum1 + sum2)
         .intValue())
         .isEqualTo(15);

// Tückisch ...
List strings = Arrays.asList("abc", "def", "ghi", "jkl", "mno", "pqr", "stu", "vwx", "yz");

// ... Sequentiell ausgefuehrt wäre das noch in Ordnung ...
assertThat(
    strings.stream().reduce(
        new StringBuilder(),
        StringBuilder::append,
        StringBuilder::append).toString()).isEqualTo("abcdefghijklmnopqrstuvwxyz");

// ... die parallele Streamverarbeitung verursacht aber einen Fehler ...
assertThat(
    strings.parallelStream().reduce(
        new StringBuilder(),
        StringBuilder::append,
        StringBuilder::append).toString()).isNotEqualTo("abcdefghijklmnopqrstuvwxyz");
Gerade letztes Beispiel zeigt, dass die naive Verwendung von reduce interessante Fehler verursachen kann. Problematisch in diesem Fall ist die Verwendung von StringBuilder::append, welches ein berechnetes Ergebnis verändert. Das fällt in die Kategorie interfering (störend beeinflussend, einmischend). Die Codebeispiele finden sich auch auf GitHub unter Java 8 Examples

Weitere Hinweise und Beispiele:



UPDATE:

  • 2017-08-15 Was ist 'interfering'? Abgrenzung im Vergleich zu #collect()

Keine Kommentare:

Kommentar veröffentlichen

AssertJ und java.util.List

AssertJ hat eine praktische Möglichkeit, Listen in JUnit Tests abzuprüfen. Insbesondere, wenn in der Liste komplexe Objekte abgelegt sind, s...