まあ知ってる人には驚く話ではないのだけれども。
Ruby で数値の総和を求める
Ruby で数値の配列が与えられていて,その要素の総和を求めたいとき,Array#sum を使うのが鉄則である。
以下のコードを比較してみよう。
numbers = Array.new(1000){ rand }
# (1)
numbers.inject(&:+)
# (2)
numbers.inject(:+)
# (3)
numbers.sum
速度は (1) → (2) → (3) の順に速くなる。
これらの中で (3) は最も高速かつ簡素であり,それだけでも sum
を採用すべき理由になる。
しかし,それだけではない。
精度
数値が Integer や Rational の場合はそもそも演算の誤差が生じないのでよいが,数値が Float の場合,演算の誤差を考えなければならない。
浮動小数点数の演算には誤差を伴うことが多い。それ自体は仕方がないのだが,2 回以上演算を繰り返す場合は,誤差の累積を問題にしなければならない。
結論を先に書くと,sum
を採用すべき三つ目の理由は,sum
には誤差の累積を抑える「Kahan の加算アルゴリズム」が採用されていることである。
参考:カハンの加算アルゴリズム - Wikipedia
誤差の例
Float が表す数について
本題に入る前に,少し予備知識の整理をしておきたい。
2 進法に基づく浮動小数点数で 0.1 という数値が表せないことはよく知られている。簡単に言えば,0.1 という数値は 2 進法では無限小数になるので,それを有限桁で表すことはできないからである。
では,Ruby で
puts 0.1
を実行すると端末に 0.1
と表示されるのはどういうことか。
まず Ruby の処理系は 0.1
という浮動小数点数リテラルを見て,Float
オブジェクトを生成する。
これは「0.1 に極めて近いが同じではない」浮動小数点数を表わしている。
大雑把に言って,(10 進で)15 桁くらいの精度をもった数値である。いや,実は Ruby の Float オブジェクトがどんなビット列で表されているかは環境依存なのだが,多くの環境で C 言語の double という数値型に基づいているらしく,その場合はそうなる。本記事の内容はすべてこの前提で書かれており,該当しない環境の場合は結果が異なりうる。
0.1 ではない数値を表示させているのになぜ 0.1
と表示されるのか。
それは,puts
に Float オブジェクトを与えたとき,まず to_s
メソッドによって「10 進法に基づく数字列」という String オブジェクトに変換されるのだが,その結果が "0.1"
という文字列だからである。
10 進 → 2 進と違って,2 進 → 10 進の変換だと,有限小数が無限小数になったりはしない1。実際,浮動小数点数リテラル 0.1
が表す Float オブジェクト(が表す数値)は,10 進法で
0.1000000000000000055511151231257827021181583404541015625
という,小数点以下 55 桁の有限小数になるようだ(私がなんかどこかでミスしてなければ)。
しかし,Ruby の Float#to_s メソッドはそんな文字列を返さない。
Float オブジェクトが持ちうる精度に見合った桁数だけを取り,"0.1"
という文字列を返すのである。これは to_s
の仕様である。
(このあたり,あまり詳しくないので,誤りの指摘や補足があればお願いします)
(2021-03-07 追記)
@mrkn さんによると Ruby は浮動小数点数を 10 進の文字列に変換するにあたって以下の論文のアルゴリズムを使っているそうです(Slack の ruby-jp で教えていただきました)。
https://ampl.com/REFS/rounding.pdf
えっと,私はめくってみましたが読んでません(ムツカシソウ)。
誤差の累積
では本題である sum
と inject(:+)
で結果が異なる例を見よう。
numbers = [0.1] * 6
puts numbers.sum == numbers.inject(:+)
# => false
6 個の 0.1
の総和が一致していない(繰り返すが,環境によっては結果が異なりうる)。
それぞれの結果を puts
で表示させてみよう。
numbers = [0.1] * 6
puts numbers.sum # => 0.6000000000000001
puts numbers.inject(:+) # => 0.6
これを見て,「えっ? sum
より inject(:+)
のほうが精度が高いじゃん! 嘘つき!」と早合点してはいけない2。
既に見たように Ruby の浮動小数点数リテラル 0.1
によって生成される Float オブジェクトが表している数値は 0.1 ではないのである。
ちなみに,inject
版の結果が 0.6
と表示されているが,返り値が 0.6(という数を表す Float オブジェクト)であることを意味しない。あくまで返り値を to_s
した結果が "0.6"
という文字列だというだけである。
誤差の評価
では,誤差がどうなっているかを正確に知るにはどうすればいいか。
それには Float#to_r を用いて Float オブジェクトを Rational オブジェクトに変換する。
このメソッドは,Float が表している数値に厳密に一致する有理数オブジェクトを返す。
こんな具合である。
puts 0.1.to_r
# => 3602879701896397/36028797018963968
なんかスゴイ分数が表示されたが,何かの間違いではない。
0.1
というリテラルに基づく Float
オブジェクトはこのような数値を表しているのである。
一見わけが分からない数字列に見えるが,よくよく見えば分子と分母は末尾以外は数字が一致しており,分子のほうが一桁少ない。つまり,0.1 という数値に非常に近いことが見て取れる。
Rational に持ち込めば加減乗除で演算誤差は生じない。
こんなふうにしよう。
Rational にしてから取った総和を「真の和」と呼ぶことにする。
sum
と inject
で作った和と真の和の差の絶対値を「誤差」と呼ぶことにする。
どちらが誤差が小さいか比べるため,sum
版の誤差から inject
版の誤差を引いたものを計算する。これが正なら sum
版の誤差が大きく,負なら inject
版の誤差が大きい。
# 足すべき数
x = 0.1
# 足し合わせる個数
n = 6
# 真の和(Rational)
exact_sum = x.to_r * n
# n 個の x からなる配列
numbers = [x] * n
# sum による和(Rational)
sum_by_sum = numbers.sum.to_r
# その誤差
error_by_sum = (exact_sum - sum_by_sum).abs
# inject による和(Rational)
sum_by_inject = numbers.inject(:+).to_r
# その誤差
error_by_inject = (exact_sum - sum_by_inject).abs
# 比較
puts sum_by_sum - sum_by_inject # => 1/9007199254740992
puts error_by_sum - error_by_inject # => 0/1
あれれ? sum
版の和と inject
版の和は確かに微妙に違っているのだが,それぞれの誤差は完全に一致している?
一見不可解だが,何も不思議なことはない。「誤差」を計算するときに絶対値を取っているからこうなる。
sum
版と inject
版の和は,真の和の左右に同じ距離だけ離れて存在しているのだ。和そのものの値は違っているが真の和とのズレ量は同じだったということ。
「ん? じゃあ,sum
が inject
より精度が高いとか言ってたのは嘘だったのかよ」
話を最後まで聞いてほしい3。
今の場合,つまり,0.1
(というリテラルによる Float)を 6 個足し合わせた場合は,精度に違いがなかった。
これは inject
版にとって幸運なケースだったということだ。
では,実際に sum
版のほうが真の和に近いケースはあるのか。あるいは逆のケースは無いのか。
以下のようにして調べてみよう。
足すべき数は 0.1
(というリテラルによる Float)とし,足し合わせる個数を変えていく。
x = 0.1
1.upto(100) do |n|
exact_sum = x.to_r * n
numbers = [x] * n
sum_by_sum = numbers.sum.to_r
error_by_sum = (exact_sum - sum_by_sum).abs
sum_by_inject = numbers.inject(:+).to_r
error_by_inject = (exact_sum - sum_by_inject).abs
puts "%4d %2d" % [n, (error_by_sum <=> error_by_inject)]
end
error_by_sum <=> error_by_inject
は,もし sum
版の誤差のほうが大きければ 1
を,その逆であれば -1
を,同じ誤差の大きさなら 0
を返すはずである。
結果は以下のようになった。
1 0
2 0
3 0
4 0
5 0
6 0
7 -1
8 -1
9 -1
10 -1
11 -1
12 0
13 0
14 0
15 -1
16 -1
17 -1
18 -1
19 -1
20 -1
21 -1
22 -1
23 -1
24 -1
25 -1
26 -1
27 -1
28 -1
29 -1
30 -1
31 -1
32 -1
33 -1
34 -1
35 -1
36 -1
37 -1
38 -1
39 -1
40 -1
41 -1
42 -1
43 -1
44 0
45 0
46 -1
47 -1
48 -1
49 -1
50 -1
51 -1
52 -1
53 -1
54 -1
55 -1
56 -1
57 -1
58 -1
59 -1
60 -1
61 -1
62 -1
63 -1
64 -1
65 -1
66 -1
67 -1
68 -1
69 -1
70 -1
71 -1
72 -1
73 -1
74 -1
75 -1
76 -1
77 -1
78 -1
79 -1
80 -1
81 -1
82 -1
83 -1
84 -1
85 -1
86 -1
87 -1
88 -1
89 -1
90 -1
91 -1
92 -1
93 -1
94 -1
95 -1
96 -1
97 -1
98 -1
99 -1
100 -1
見てのとおり,1 個から 100 個までの中に,誤差の大きさが同じだったものが 11 あった。
それ以外はすべて sum
版のほうが誤差が小さい。
結局,この実験の範囲では,
-
sum
版とinject
版の誤差が同じケース → 少数 -
sum
版のほうが誤差が小さいケース → 多数 -
sum
版のほうが誤差が大きいケース → 無し
であった。
しかし,もちろんこんな簡単な実験の結果を一般化するわけにはいかない。今の私にできるのは,Kahan のアルゴリズムを信じることと,上記の実験の範囲内では期待される結果が得られたことを確認することだけである。
ちなみに,sum
版が真の和と一致したものは 7 個あった。このうち,3 個は inject
版も一致していた。
まとめ
総和を得るなら inject(:+)
ではなく sum
を使おう。
そのほうが簡素で高速。そして,数値が浮動小数点数の場合は誤差の累積も抑えられる。