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

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

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を使う方法
以下の２つのコードは同じ結果を返す。

``` ruby
sum = array.inject(&:+)
```


``` ruby
sum = array.inject(:+)
```
### eachを使う方法

``` ruby
sum = 0
sum = array.each { |x| sum += x }
```

### sumを使う方法

``` ruby
sum = array.sum
```

### 比較
実行時間の比較は以下のソースコードで行う。
1万個の乱数を配列に入れ、それの総和を取り、各処理を1万回繰り返した時間を計測する
#### ソースコード

``` ruby
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(:+)`が早いことがわかる。

#### ※ 補足
`inject`と`each`は配列の値の和は同じ結果を返すが、`sum`はそれらと違う結果を返す。
理由として`sum(Enumerable#sum)`はRuby2.4から実装されたものであり「カハンの加算アルゴリズム」が使われている。
したがって、`Enumerable#sum`は誤差が改善され、且つ、高速になっている。

``` ruby
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#<<`は破壊的に結合をするため注意が必要。

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

### injectを使う方法
以下の２つのコードは同じ結果を返す。

``` ruby
str = array.inject(:+)
```

``` ruby
str = array.inject(:<<)
```

### eachを使う方法
同様に、以下の２つのコードは同じ結果を返す。

``` ruby
str = ''
array.each{|x| str += x}
```

``` ruby
str = ''
array.each{|x| str << x}
```

### joinを使う方法
最も簡単な方法である。

``` ruby
str = array.join
```

### 比較
実行速度の比較を以下のソースコードで行った。
10万個のランダムな８文字の文字列を配列に入れ、その配列内の文字列を結合する時間を各々のやり方で計測する。
#### ソースコード

``` ruby
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#push`と`Array#<<`がある。

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

### 比較
1から１億までの整数を配列に追加していく処理を２パターン計測する。
#### ソースコード

``` ruby
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#+ を使う方法

``` ruby
# 初期化
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回繰り返す。

### ソースコード

``` ruby
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`を用いたほうが高速に処理できることがわかる。


# おわりに
自分でも使うメソッドによってこんなに差が出るとは思っていませんでした。
同じ処理だけど、こう工夫すると早くなるよっていう情報をお持ちの方は是非コメントお願いします。
また、ベンチマークの取り方で不適切な部分があればご指摘ください。

## 参考文献
- [Ruby でベンチマークを取る方法](https://qiita.com/scivola/items/c5b2aeaf7d67a9ef310a)
- [module function Benchmark.#bmbm](https://docs.ruby-lang.org/ja/latest/method/Benchmark/m/bmbm.html)