Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

https://qiita.com/angel_p_57/items/24078ba4aa5881805ab2#comment-3001a8f9ccbbfd44e719

https://twitter.com/angel_p_57/status/1066164125036756993

を受けて。

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_rsum.to_f で値に違いがある例は見つけられなかった。
すごい。

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

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

速さでは、さすがの 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 だけが別の値になっているのが目立っている。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away