Streamの平均を求める処理が精度が高かった件(総和も)
昨日,JavaDayTokyo2015でProject Lambdaのハンズオンのお手伝いをしてきました.
その中で,Collectors#averagingDoubleやDoubleStream#averageの実装が優秀だということが分かったので,まとめておきます.
結論を先に言うとStreamAPI*1が優秀なので,それを使おうという話です.
*2
普通の実装の話
よくサンプルで出てくる,ある数列から平均値を求める処理は以下のようになっていると思います.
また,おそらく普通のプログラマに平均値を求める処理を書かせても同様なコードを書くと思います.*3
double[] array = {...}; double sum = 0; for (int v : array) { sum += v; } double ave = sum / array.length;
実はこれは精度が低く,実際の平均値と比べて誤差が出てしまう場合があります.
なぜなら,浮動小数点型の特性上,小数値を誤差なく保持できない*4ため,加算によって僅かな誤差が蓄積されていってしまうからです.
誤差が出ることを確認してみます.
例えば,次のようなメソッドがあるとします.
double average(double v, int count) { double sum = 0; for (int i = 0; i < count; i++) { sum += v; } return sum / count; }
このメソッドは同じ浮動小数点値の数列に対する平均値を求めています.
同じ浮動小数点値を何度も足して,最後に足した回数で割っているため,当然同じ値になるはずです.
(現在OpenJDKで開発中のREPLを用いています. 使ってみたい方はこちらをご参照ください. )
-> average(0.5, 10000000) | Expression value is: 0.5 | assigned to temporary variable $13 of type double
確かに,0.5ではうまく動いています.
ですが,先ほど説明したように誤差が出る場合もあります.
例えば,0.1などです.
-> average(0.1, 10000000) | Expression value is: 0.09999999998389754 | assigned to temporary variable $14 of type double -> average(0.015, 10000000) | Expression value is: 0.015000000001293775 | assigned to temporary variable $15 of type double
このように,かなり小さいですが,誤差が生じてしまいます.
Streamの話
さて,この誤差ですが,StreamAPIのCollectors#averagingDoubleやDoubleStream#averageを利用すると,ほとんど生じなくなります.*5
それを確認してみます.
double average(double v, int count) { return DoubleStream.generate(() -> v).limit(count) .average().orElse(0); }
averageの実装をDoubleStreamを使うように修正しました.
これを使って先ほどの誤差が出た例を計算してみます.
-> average(0.1, 10000000) | Expression value is: 0.1 | assigned to temporary variable $18 of type double -> average(0.015, 10000000) | Expression value is: 0.015 | assigned to temporary variable $19 of type double
確かに,先ほどとは違い,誤差が出ていません.
Streamの中の話
実装の話ですが,カハンの加算アルゴリズムという加算アルゴリズムを使用しています.
詳しい話はウィキペディア先生グーグル先生に任せますが,簡単に言うと,sum=a+bをした時に,出た誤差c(=sum-a-b)を次回の足し算の時に,sum-cとすることで誤差を抑えこんでいきます.
詳しい実装はこちらをご覧ください.
Oracleの中の人は優秀ですね.
この誤差は足し算での話なので,総和を求める演算などでもStream/DoubleStreamを用いることで誤差を最小限に抑えこむことができます.
結論
ということで,皆,StreamAPIを使おう!Oracleの優秀なエンジニアの力が自分のものになるよ!
余談
ところでGSCollectionsでも同様のアルゴリズムを用いているそうです.
GSCollectionsでも精度の高い総和・平均計算ができるようです!