ruby と python で FloatやRational の和を取る。速さと正確さ。

Float や Rational の合計を求める計算の速度と値を比較する。

や

を受けて。

ruby 2.5 で inject(&:+) と sum の比較。
ついでに python も。
せっかく python なので、numpy も参戦して。

この記事を公開したら
https://twitter.com/WniKwo/status/1066249059097165824
という反響を頂いたので、math.fsum も追加。

コメント欄を受けて numo/narray も参加。

試したコード

ruby(sum)

ruby2.5

require "benchmark"

N=100000000
a=[0.00000001]*N
p Benchmark::realtime{ p a.sum }

ruby(sum, Rational)

ruby2.5

require "benchmark"

N=100000000
a=[0.00000001r]*N
p Benchmark::realtime{ p a.sum }

ruby(inject)

ruby2.5

require "benchmark"

N=100000000
a=[0.00000001]*N
p Benchmark::realtime{ p a.inject(&:+) }

ruby(inject-no-amp)

コメントを受けて「&:+」ではなく「:+」にしたバージョン

ruby2.5

require "benchmark"

N=100000000
a=[0.00000001]*N
p Benchmark::realtime{ p a.inject(:+) }

ruby(numo/narray)

ruby2.5

require "numo/narray"
require "benchmark"

N=100000000
a=Numo::DFloat.new(N).fill(0.00000001)
p Benchmark::realtime{ p a.sum }

(コメント欄に書いていただいたコードそのまま）

python(sum)

python3.7.1

import time

N=100000000
a = [0.00000001]*N
t0 = time.time()
print( sum(a) )
t1 = time.time()
print( t1-t0 )

python(reduce)

python3.7.1

import time
from functools import reduce

N=100000000
a = [0.00000001]*N
t0 = time.time()
print( reduce(lambda x, y: x + y, a) )
t1 = time.time()
print( t1-t0 )

python(numpy.sum)

python3.7.1

import numpy as np
import time

N=100000000
a = np.array([0.00000001]*N)
t0 = time.time()
print( np.sum(a) )
t1 = time.time()
print( t1-t0 )

python(math.fsum)

python3.7.1

import time
import math

N=100000000
a = [0.00000001]*N
t0 = time.time()
print( math.fsum(a) )
t1 = time.time()
print( t1-t0 )

実行結果

処理系	値	時間
ruby(sum)	1.0	0.41秒
ruby(sum, Rational)	(1/1)	28.18秒
ruby(inject)	1.0000000022898672	5.76秒
ruby(inject-no-amp)	1.0000000022898672	3.61秒
ruby(numo/narray)	1.0000000022898672	0.12秒
python(sum)	1.0000000022898672	0.45秒
python(reduce)	1.0000000022898672	8.07秒
python(numpy.sum)	0.9999999999997999	0.095秒
python(math.fsum)	1.0	1.77秒

で。

ruby の sum で使われている カハンの加算アルゴリズム は強力で、わりと正確な値になる感じっぽい。

こんな

ruby2.5

Array.new(10000){|x| x*0.0001}.sum #=> 4999.5
Array.new(10000){|x| x*0.0001}.inject(&:+) #=> 4999.499999999991

Array.new(10000){|x| 9.0/(x%5+1)**2}.sum #=> 26345.0
Array.new(10000){|x| 9.0/(x%5+1)**2}.inject(&:+) #=> 26345.000000000713

Array.new(10000){|x| 1.0/1.5**x }.sum #=> 3.0
Array.new(10000){|x| 1.0/1.5**x }.inject(&:+) #=> 2.9999999999999987

Array.new(10000){|x| 1.0/(-1.5)**x }.sum #=> 0.6
Array.new(10000){|x| 1.0/(-1.5)**x }.inject(&:+) #=> 0.5999999999999999

Array.new(10000){|x| (2.0/3)**x}.sum #=> 2.9999999999999996
Array.new(10000){|x| (2.0/3)**x}.inject(&:+) #=> 2.9999999999999987
Array.new(10000){|x| (2.0/3)**x.to_r}.sum.to_f #=> 2.9999999999999996

感じ。
ruby の sum は不思議なくらい計算が合う。
(2.0/3)**x の例は一見誤差があるように見えるが、(2.0/3).to_r**x と同じ結果になっていることから分かる通り、sum の計算結果は合っているようだ。恐ろしい。

数十例試してみたが、(hoge) の sum と、(hoge).to_r の sum.to_f で値に違いがある例は見つけられなかった。
すごい。

一方。
python の sum() は普通に足し算しているだけのようで、ruby の inject(&:+) と全く同じ値になる。

そう思うと numpy の sum が違う値になるのは謎だけど、原因については調査していない。

速さでは、さすがの numpy様の圧勝。
正確さで圧倒的一位のRational 版は、やっぱり圧倒的に遅かった。

Go とか C++ も参戦させようかとも思ったけど、今日のところはこれぐらいで。

--- 以下追記 ---

python の math.fsum() は、ruby の sum と同じように誤差の少ない計算をできるみたい。
see https://docs.python.jp/3/library/math.html#math.fsum

前掲の wikipedia には
「Pythonの標準ライブラリには fsum という総和関数があり、Shewchukのアルゴリズムを使い丸め誤差の蓄積を防いでいる。」とあるので、ruby とはちょっと違う方法みたい。

計算に要する時間は ruby の sum よりだいぶ遅い感じ。4倍ちょっと。

そう思うと逆に。
ruby にもやや不正確だけど sum よりも速い合計計算メソッドがあってもいいような気がする。

そして。

ruby の sum / inject(&:+) に課したのと同じような計算を math.fsum() / sum() に課すと、以下のようになった：

python3.7.1

import math

a=[x*0.0001 for x in range(0,10000)]
print( math.fsum(a) ) #=> 4999.5
print( sum(a) ) #=> 4999.499999999991

a=[9.0/(x%5+1)**2 for x in range(0,10000)]
print( math.fsum(a) ) #=> 26345.0
print( sum(a) ) #=> 2.9999999999999987

a=[1.0/1.5**x for x in range(0,1000)]
print( math.fsum(a) ) #=> 3.0
print( sum(a) ) #=> 2.9999999999999987

a=[1.0/(-1.5)**x for x in range(0,1000)]
print( math.fsum(a) ) #=> 0.6
print( sum(a) ) #=> 0.5999999999999999

a=[(2.0/3)**x for x in range(0,1000)]
print( math.fsum(a) ) #=> 2.9999999999999996
print( sum(a) ) #=> 2.9999999999999987

math.fsum() は、ruby の sum と同じように正確。

--- 以下、さらに追記 ---

コメントの指摘を受けて「inject(&:+)」を「inject(:+)」に変えたバージョンも試してみたところ、実行時間が6割ちょっとになった。すごい。なんだこれ。

さらに。

ruby の numo/narray の sum が参戦。
速度面では python の numpy.sum に肉薄するものの惜しくも敗れた。

値のほうは inject(&:+) などと同じ値になった。ますます numpy.sum だけが別の値になっているのが目立っている。