Java8 Streamのリダクション操作について

Java8 Streamざっくりまとめで、大体のStream操作は紹介しましたが、リダクション操作については詳しい説目が必要そうだったので書きます。
基本的にStreamのJavaDocを参考にしています。

リダクション操作とは

リダクション操作はストリーム内のすべての要素を累積関数を使って一つにまとめた結果を返す操作です。
reductionは日本語では畳み込みと言ったりするようですが、いわゆる畳み込み積分(convolution)ではありません。
どっちかというと総和や総乗のようなイメージです(というか、総和や総乗がリダクションの一種です)。
リダクション操作には、1つの値を返すリダクションと値を複数含むコンテナ(Collectionなど)を返す可変リダクションがあります。

reduce~リダクション~

reduceメソッドは累積関数(accumulator)を使って各要素を累積した結果を返します。
reduceメソッドには以下の3種類のオーバーライドが存在します。

メソッド
T reduce(T identity, BinaryOperator<T> accumulator)
Optional<T> reduce(BinaryOperator<T> accumulator)
<U> U reduce(U identity, BiFunction<U,? super T,U> accumulator, BinaryOperator<U> combiner)

T：Stream内要素の型

各引数

accumulator~累積関数~

accumulatorは要素同士の合算を繰り返し、累積結果を求めるための関数(インターフェース)です。
reduceメソッドでは、accumulator.applyを内部的に呼び出して2つの値を合算して中間結果を生成し、その中間結果に対してさらに合算処理を繰り返すことで最終的な結果を得ます。
そのため、accumulator.applyは結合法則が成り立つ演算である必要があります。

identity~単位元~

indetifyは、accumulator.applyの単位元となる値です。

単位元の数学的定義

集合内の任意の要素aとその上の二項演算*によって以下の性質を満たすeを単位元と呼ぶ。
a * e = e * a = a

Java的表現

ストリーム内の任意の要素aに対して、以下の性質を満たすidentifyを単位元と呼ぶ。
accumulator.apply(identify, a) == accumulator.apply(a, identify) == a

具体的な例を上げると、実数集合上の+(加法)の単位元は0、*(乗法)の単位元は1になります。

a = 2の場合

0 + 2 = 2 + 0 = 2

1 * 2 = 2 * 1 = 2

ストリーム内の要素が存在しない場合、リダクションの結果として単位元の値が返されます。
単位元を指定しない場合(2番目のオーバーライドメソッド)、`reduce'内の処理が単純化されるため(特に並列処理では大幅に)、できるだけ指定するべきです。

combiner~結合関数~

combinerは累積結果同士を結合するための関数(インターフェース)です。
並列ストリームで、各スレッドで実行された結果の結合を行います。
combinerを指定しない場合(1、2番目のオーバーライドメソッド)、この結合処理はaccumulatorが行います。
また、順次ストリームの場合はcombinerを指定しても使用されません。

combinerはaccumulatorと同じで単位元がidentityかつ、結合法則を満たす関数である必要があるほか、以下を満たす(accumulatorと互換性がある)必要があります。

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

combinerが必要となるケースは、要素同士の合算時と累積結果の結合で実行する関数が異なる場合です。
例えば、二乗和がそのケースに当たります。
二乗和の場合、要素同士では$a^2 + b^2$ですが、その結果同士を結合するときも同じ関数を使ってしまうと、$(a^2 + b^2) ^2 + (c^2 + d^2) ^2$になってしまいます。
そこで、combinerを単純な和にしておくことによって二乗和のリダクションが実現できます。

Stream.iterate(1, x->x+1)
      .limit(4)
      .parallel()
      .reduce(0, (x,y)->x*x + y*y, (x,y)->x+y);

この処理は1～4までの二乗和を取るので結果は30になります。
しかし、combinerを使わない場合は結果が異なります。
並列処理だと計算順序を調べづらいので、順次処理に変更してこの処理を実行すると結果は1172になります。
これは、以下のような計算が行われた結果です。

(((((0^2+1^2)^2)+2^2)^2+3^2)^2+4^2) = 1172

しかし、この形式の処理はmapを使うと単純に表現することができます。
二乗和であれば、mapで各要素の二乗を求めてからリダクションすればよいだけです。

Stream.iterate(1, x->x+1)
      .limit(4)
      .parallel()
      .map(x->x*x)
      .reduce(0, (x,y)->x*x + y*y);

collect~可変リダクション~

collectメソッドは結果として値ではなく可変な結果コンテナを返します。
collectメソッドには、2種類のオーバーライドが存在します。

メソッド
<R> R collect(Supplier<R> supplier, BiConsumer<R,? super T> accumulator, BiConsumer<R,R> combiner)
<R,A> R collect(Collector<? super T,A,R> collector)

コンテナ操作による方法

1つめの方法は結果コンテナによる各操作を自分で定義する方法です。
生成、追加、結合の操作をそれぞれ引き渡すと各操作を使ってリダクションを行います。

supplier~生成~

supplierは結果コンテナのインスタンスを生成する処理です。
基本的には、結果コンテナクラス::newを渡すことが多いかとは思いますが、Factoryクラスがある場合はその生成メソッドを渡すこともあるでしょう。
並列処理の場合supplierは複数回呼び出されますが、そのたびに新しいインスタンスを生成する必要があります。

accumulator~追加~

accumulatorは結果コンテナへ1つの要素を追加するための処理です。
Collection系のオブジェクトにおいては、addメソッドが該当します。
結合法則が成り立つ処理である必要があります。

combiner~結合~

combinerは2つの結果コンテナを結合するための処理です。
並列処理の場合、各スレッドで作成された結果メソッドがcombinerによって結合されます。
Collection系のオブジェクトにおいては、addAllメソッドが該当します。
通常のリダクション処理と同じく、結合法則が成り立ち、accumulatorと互換性がある処理である必要があります。
また、順次ストリームの場合は使用されません。

例えば、ストリーム内の要素をArrayListに格納して戻すリダクション処理は以下のようになります。

Stream.iterate(1, x->x+1)
      .limit(10)
      .parallel()
      .collect(ArrayList::new,
               Collection::add,
               Collection::addAll));

Collcetorを使う方法

Collectorはsupplier、accumulator、combinerという各操作をカプセル化したオブジェクトです。
Collector自体はインターフェースであり上記3つの操作以外に、コレクションの特性セットを返すcharacteristics、最終的な変換処理を行うfinisherメソッドが定義されています。
Collectorオブジェクトは自作することも可能ですが、Collctorsクラスには有用なCollectorを返すstaticメソッドが多く用意されています。

例えば、先ほどのようにListにする処理はtoListメソッドを使って次のように記述できます。

Stream.iterate(1, x->x+1)
      .limit(10)
      .parallel()
      .collect(Collectors.toList()));

ただし、toListでは返されるListの型までは保証されません(上の処理で試したらArrayListでしたが)。
より詳細に使用するCollectionの型を決めたい場合は、toCollectionメソッドがあります。

Stream.iterate(1, x->x+1)
      .limit(10)
      .parallel()
      .collect(Collectors.toCollection(ArrayList::new)));

toCollectionメソッドでは、supplier(生成処理)だけを引き渡してやります。
Collectionの実装クラスなら何でもよいのでHashSetにすることも可能です(SetにするならtoSetというメソッドもありますが)。

このように便利なメソッドがCollectorsクラスには多く用意されているので、活用していくことで簡単に可変リダクションを使うことができます。