Edited at

[Ruby]いろんな処理のベンチマーク選手権

More than 1 year has passed since last update.

P&Dアドベントカレンダー3日目です。

Rubyって同じ処理をするのにも、いろんな書き方がありますよね。

そして、どの書き方が早いのだろうと思うこともあるんじゃないでしょうか。


はじめに

ベンチマークの取り方について、正しいかは分かりません。

あくまで参考程度にお願いします。


環境


  • MacBook Pro(Retina, 13-inch, Early 2015)

  • macOS Sierra

  • CPU: Intel Core i7 3.1GHz

  • RAM: 16GB

  • ruby 2.5.0dev (2017-12-01 trunk 60956) [x86_64-darwin16]


配列に含まれる数値の総和 部門

[1, 2, 3]のような配列に含まれる数値の合計を出す。


injectを使う方法

以下の2つのコードは同じ結果を返す。

sum = array.inject(&:+)

sum = array.inject(:+)


eachを使う方法

sum = 0

sum = array.each { |x| sum += x }


sumを使う方法

sum = array.sum


比較

実行時間の比較は以下のソースコードで行う。

1万個の乱数を配列に入れ、それの総和を取り、各処理を1万回繰り返した時間を計測する


ソースコード

require 'benchmark'

array = 10000.times.map{ rand }

iteration_count = 10000
Benchmark.bmbm 10 do |r|
r.report "inject(&:+)" do
iteration_count.times { sum = array.inject(&:+) }
end
r.report "inject(:+)" do
iteration_count.times { sum = array.inject(:+) }
end
r.report "each" do
iteration_count.times do
sum = 0
array.each{|x| sum += x}
end
end
r.report "sum" do
iteration_count.times { sum = array.sum }
end
end


結果

Rehearsal -----------------------------------------------

inject(&:+) 6.118703 0.028827 6.147530 ( 6.217453)
inject(:+) 3.704129 0.020889 3.725018 ( 3.826290)
each 5.108786 0.018195 5.126981 ( 5.202050)
sum 0.449951 0.003051 0.453002 ( 0.457235)
------------------------------------- total: 15.452531sec

user system total real
inject(&:+) 6.018644 0.022897 6.041541 ( 6.093476)
inject(:+) 3.629471 0.016019 3.645490 ( 3.705651)
each 5.713270 0.017636 5.730906 ( 5.764066)
sum 0.490372 0.004442 0.494814 ( 0.505518)


1位: sum

--- 超えられない壁 ---

2位: inject(:+)

3位: each

4位: inject(&:+)


sumメソッドが最も早く、次にinject(:+)が早いことがわかる。


※ 補足

injecteachは配列の値の和は同じ結果を返すが、sumはそれらと違う結果を返す。

理由としてsum(Enumerable#sum)はRuby2.4から実装されたものであり「カハンの加算アルゴリズム」が使われている。

したがって、Enumerable#sumは誤差が改善され、且つ、高速になっている。

Array.new(10, 0.1).inject(:+) #=> 0.9999999999999999 (誤差がある)

Array.new(10, 0.1).sum #=> 1.0  (誤差がない(小さい))

また、Rails5.0系以下だと、sumがActiveSupportで実装されており、こちらの環境ではEnumerable#sumの恩恵が受けられなかった。


配列の中の文字列を結合 部門

['hoge', 'huga'] のような文字列が含まれる配列に対し'hogehuga'のように文字列を結合する処理を考える。


文字列の結合

まず、文字列同士を結合するときに考えられる方法としてString#+で結合する方法とString#<<で結合する方法が考えられる。

String#<<は破壊的に結合をするため注意が必要。

# String#+ で結合

str = 'abc' + 'edf' #=> 'abcdef'
# String#<< で結合
str = 'abc'
str << 'edf' #=> 'abcdef'


injectを使う方法

以下の2つのコードは同じ結果を返す。

str = array.inject(:+)

str = array.inject(:<<)


eachを使う方法

同様に、以下の2つのコードは同じ結果を返す。

str = ''

array.each{|x| str += x}

str = ''

array.each{|x| str << x}


joinを使う方法

最も簡単な方法である。

str = array.join


比較

実行速度の比較を以下のソースコードで行った。

10万個のランダムな8文字の文字列を配列に入れ、その配列内の文字列を結合する時間を各々のやり方で計測する。


ソースコード

require 'benchmark'

array = 100_000.times.map do
(0...8).map{ (65 + rand(26)).chr }.join
end

Benchmark.bmbm 10 do |r|
r.report "inject+" do
str = array.inject(:+)
end
r.report "each+" do
str = ''
array.each{|x| str += x}
end
r.report "inject<<" do
str = array.inject(:<<)
end
r.report "each<<" do
str = ''
array.each{|x| str << x}
end
r.report "join" do
str = array.join
end
end


結果

Rehearsal ----------------------------------------------

inject+ 9.200816 13.532302 22.733118 ( 23.377148)
each+ 9.210481 13.554497 22.764978 ( 23.322061)
inject<< 0.019297 0.000685 0.019982 ( 0.020103)
each<< 0.030170 0.001236 0.031406 ( 0.032330)
join 0.023466 0.001244 0.024710 ( 0.024955)
------------------------------------ total: 45.574194sec

user system total real
inject+ 25.213289 28.269693 53.482982 ( 54.000338)
each+ 25.290368 28.161327 53.451695 ( 54.087785)
inject<< 0.023882 0.001350 0.025232 ( 0.026615)
each<< 0.027701 0.002200 0.029901 ( 0.032536)
join 0.018329 0.000616 0.018945 ( 0.021102)


1位: join

2位: inject<<

3位: each<<

--- 超えられない壁 ---

4位: each+

5位: inject+


まず、String#+よりString#<<を用いた方が文字列の結合が高速に行えることが結果からわかる。

配列内の文字列を結合するときはArray#joinを使い結合した方がより高速であることがわかる。


配列に要素(整数)を追加する 部門

配列に要素を追加する方法としてArray#pushArray#<<がある。

# Array#<<

array << x
# Array#push
array.push(x)


比較

1から1億までの整数を配列に追加していく処理を2パターン計測する。


ソースコード

require 'benchmark'

Benchmark.bmbm 10 do |r|
r.report '<<' do
array = []
1.upto(100_000_000) do |i|
array << i
end
end
r.report 'push' do
array = []
1.upto(100_000_000) do |i|
array.push(i)
end
end
end


結果

Rehearsal ----------------------------------------------

<< 0.684788 0.046061 0.730849 ( 0.956542)
push 0.916803 0.051229 0.968032 ( 1.448023)
------------------------------------- total: 1.698881sec

user system total real
<< 0.534575 0.037613 0.572188 ( 0.594617)
push 0.784762 0.061471 0.846233 ( 1.044220)


1位: <<

2位: push


整数を配列に追加していくとき、Array#<<を用いた方が早いことがわかる。


配列と配列を結合する 部門

配列同士を結合するときはArray#+や破壊的メソッドであるArray#concatを使うだろう。


Array#+ を使う方法

# 初期化

arr1 = [1, 2, 3]
arr2 = [4, 5, 6]

arr = arr1 + arr2 #=> [1, 2, 3, 4 ,5 ,6]


Array#concat を使う方法

# 初期化

arr1 = [1, 2, 3]
arr2 = [4, 5, 6]

arr1.concat(arr2) #=> [1, 2, 3, 4, 5, 6]


比較

配列arr2に1000個の配列を結合する処理を1000回繰り返す。


ソースコード

require 'benchmark'

arr1 = 1000.times.map { ['foo', 'bar', 'baz'] }
iteration_count = 1000
Benchmark.bmbm 10 do |r|

r.report '+' do
iteration_count.times do
arr2 = []
arr1.each do |elem|
arr2 += elem
end
end
end

r.report 'concat' do
iteration_count.times do
arr2 = []
arr1.each do |elem|
arr2.concat(elem)
end
end
end
end


結果

Rehearsal ----------------------------------------------

+ 2.098824 1.233609 3.332433 ( 3.379559)
concat 0.103126 0.004360 0.107486 ( 0.108041)
------------------------------------- total: 3.439919sec

user system total real
+ 2.036103 1.141893 3.177996 ( 3.211926)
concat 0.106414 0.002987 0.109401 ( 0.109818)


1位: concat

2位: +


破壊的に結合するのであれば、Array#concatを用いたほうが高速に処理できることがわかる。


おわりに

自分でも使うメソッドによってこんなに差が出るとは思っていませんでした。

同じ処理だけど、こう工夫すると早くなるよっていう情報をお持ちの方は是非コメントお願いします。

また、ベンチマークの取り方で不適切な部分があればご指摘ください。


参考文献