java.util.streamの使い方メモ reduce編

Java

reduceメソッド

<U> U reduce(U identity, BiFunction<U, ? super T, U> accumulator, BinaryOperator<U> combiner)
  • U identity 累算器、合成器の初期値
  • BinFunction<U, ? super T, U> accumulator 累算器
  • BinaryOperator<U> combiner 結合器、順次ストリームのときは結果に影響を与えない

各パラメーター

identity

  • accumulator関数の累算結果引数の初期入力値

accumulator

  • 累算(蓄積)関数と呼ばれる
  • 累算結果と入力要素を受け取り、次の累算結果を返す
    • (前回累算結果, 入力要素) -> { return 次回累算結果; }
// BiFunction == Functionの２つ引数を受け取る版
BiFunction<Integer, Integer, String> add = (left, right) -> {
    return left + " + " + right + " = " + (left + right);
};

// 1 + 2 = 3;
add.apply(1, 2);

combiner

  • 結合関数と呼ばれる
  • 順次ストリームではreduceメソッドの結果に影響を与えない
  • 並行ストリームにおいて、任意の時点でのcombinerの結果とaccumulatorの結果を受け取り、次のcombinerの入力値を返す
    • この際accumulatorは独立して実行される (identityと要素値が引数として渡される)
// BiOperation<T> == BiFunction<T, T, T>
BinaryOperator<Int> add = (left, right) -> {
    return left + right;
};

制約について

順次ストリームと並行ストリームにおいてrecuce()メソッドの結果が同一になるためには以下の制約を遵守しなければならない

  1. identity制約
  2. associativity(結合)制約

1. identity制約

identity と 独立して実行したaccumulatorの結果u (== accumulator(identity, input) を渡した時、結果はuと 同一でなければならない

combiner.apply(identity, u) == u

2. associativity(結合)制約

結合関数に、順次ストリームにおけるある任意の累算器の結果u と 累算器を独立して実行した結果(accumulator(identity, t)) を渡した結果は、累算器の結果と同一でなければならない

combiner(u, accumulator(identity, t)) == accumulator(u, t)

制約について例で確認する

1. identity制約

ある整数ストリームの各要素を二乗し、その総和を求めるrecude関数は以下のように定義できます。

数学的には以下を求める

f(x) = Σx^2

reduce関数による実装例

// 順次ストリームで実行 結果は30
var sum = Stream.of(1,2,3,4)
    .reduce(
        0,
        (acc, input) -> acc + input*input,
        (acc1, acc2) -> acc1 + acc2
    );

// 並行ストリームで実行 結果は30
var sum = Stream.of(1,2,3,4)
    .parallel()
    .reduce(
        0,
        (acc, input) -> acc + input*input,
        (acc1, acc2) -> acc1 + acc2
    );

次にidentityの値を 0から1 に変更すると、 順次ストリームでの結果と逐次ストリームの結果が異なる。

// 順次ストリームで実行 結果は31
var sum = Stream.of(1,2,3,4)
    .reduce(
        1,
        (acc, input) -> acc + input*input,
        (acc1, acc2) -> acc1 + acc2
    );

// 並行ストリームで実行 結果は34
var sum = Stream.of(1,2,3,4)
    .parallel()
    .reduce(
        1,
        (acc, input) -> acc + input*input,
        (acc1, acc2) -> acc1 + acc2
    );

上記identity制約を違反しているため

BinaryOperator<Int> combiner = (acc, input) -> {
    acc + input;
}

とすると、

combiner(1, input) != input

でありidentity制約を満たさないことが分かる。

2. associativity(結合)制約について

並行ストリームでは累算器にidentityと各要素が入力値として渡され各自独立して実行され、各累算結果はcombiner関数によって合成する。 このときcombiner関数とaccumulator関数において以下の関係を満たさない場合、順次ストリームと平行ストリームでの結果が異なる。

combiner(u, accumulator(identity, t)) == accmulator(u, t)
  • u 順次ストリームにおけるある任意の累算結果
  • t 次の入力要素
  • accumulator(identity, t) は、並列ストリームにおいて各累算処理結果を表している

上記は、順次ストリームでは、accumulator関数が以下のように呼び出されます。

n accumulatorへの入力 累算結果
1 acc(identity, x1) acc1
2 acc(acc1, x2) acc2
3 acc(acc2, x3) acc3
4 acc(acc3, x4) acc4

この時、任意の時点Nにおいて combiner関数の結果が以下を満たす必要があると述べている。

combiner(accN-1, acc(identity, xN) == accN

例として N=3 の時、以下を満たしていることを確認する

combiner(acc2, acc(identity, x3) == acc3

実際に値を入れてaccumulatorの動作を追うと以下

n accumulatorへの入力 結果値
1 acc(0, 1) 1
2 acc(1, 2) 5
3 acc(5, 3) 14
4 acc(14, 4) 30

であるから N=3 のときのcombinerの値は以下

combiner(5, acc(0, 3)) = 5 + 9 = 14

従ってN=3においては満たしていると言える。

recuceメソッド簡易版

reduce()メソッドは以下２つの簡易版が用意されている

  • T reduce(T identity, BinaryOperator\<T\> accumulator)
  • Optional\<T\> reduce(BinaryOperator\<T\> accumulator)

Collectorとの関係について

  • reduce() メソッドは collect() メソッドの簡易版である
  • streamにおいてreduction処理を行う場合は、collect()メソッド側を利用すると便利
    • Collectors クラスには Collector を生成するための便利なメソッドが用意されている
      • 一般的なコレクション型への変換
      • 総和
      • ソート