【Ruby】include?はto_setで高速化できる【注意点あり】

include?メソッドを使っていたんですが、パフォーマンスを改善できることがわかったため、備忘録としてまとめます。

問題

実務で先輩エンジニアから以下のレビューをもらいました。

Arrayクラスのinclude?メソッドは線型探索で判定するので、ここではパフォーマンスに影響が出てしまうと思います！to_setを使っても良いかもしれません！

ですが、この内容が今ひとつ理解できなかったため、レビュー対応に時間がかかってしまいました、、。

解決策

to_setメソッドを使って配列をSetクラスのオブジェクトに変換し、Setクラスのinclude?メソッドを用いることでパフォーマンスが高速化できる、ということでした。

以下に説明を加えます。

Setクラスとは？

Setクラスは集合を表すクラスです。

配列との違いとして、次の2点があります。

• 要素の重複が削除される
• 要素の順序は保持されない

to_setメソッドを用いることで、配列をSetクラスのオブジェクトに変換できます。

irb(main):001:0> [1, 2, 3, 4, 5, 1].to_set
=> #<Set: {1, 2, 3, 4, 5}>

なおSetオブジェクトは内部的に、ハッシュ構造でデータを保持します。

つまり、↑のオブジェクトは裏側では次のデータ構造になっているんです。

@hash = { 1 => true, 2 => true, 3 => true, 4 => true, 5 => true }

ArrayクラスとSetクラスのinclude?メソッドの違い

RubyにはArrayクラスだけでなく、Setクラスにもinclude?メソッドが存在しています。

両者ともに、特定の要素が含まれているかを判定する点では共通ですが、そのチェックの仕方が異なります。

Arrayクラスのinclude?メソッド

Arrayクラスのinclude?メソッドは、配列の要素を前から順番に1個ずつ確認していくことで、特定の要素が含まれているか判定します。

たとえば次のコードでは、10回のチェックが生じることになります。

irb(main):001:0> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].include?(10)
=> true

要素が数百程度までならこれで十分ですが、要素の数が大量だと、チェックの回数もそれだけ多くなるため、パフォーマンスが悪くなってしまいます、、。

Setクラスのinclude?メソッド

一方、Setクラスのオブジェクトは内部的にハッシュでデータを保持しているため、より効率的な判定が可能です。

たとえば次のコードがあったとします。

irb(main):001:0> set = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].to_set
=> #<Set: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}>
irb(main):002:0> set.include?(10)
=> true

このとき内部的には、探したい要素（今回は10）をハッシュのキーに指定し、ピンポイントで存在の有無を確認しています。

# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].to_set は内部的に次のハッシュとなる
@hash = { 1 => true, 2 => true, 3 => true, 4 => true, 5 => true, 6 => true, 7 => true, 8 => true, 9 => true, 10 => true }

# include?(10) の場合、10 をハッシュのキーとして指定し、ピンポイントでデータが含まれているかを判定する
@hash[10]
=> true

1つずつチェックしているわけじゃないので、要素の数が多かったとしてもパフォーマンスが悪化しません。

なので、大量のデータから要素を探したいときは、Arrayクラスのinclude?メソッドではなく、Setクラスのinclude?メソッドを使った方がよい、という話でした。

実際に計測してみた

手元でも実際に、両者のパフォーマンスの違いを計測してみました。

次のコードを用いて、Arrayクラスのinclude?メソッドとSetクラスのinclude?メソッドで性能にどれくらいの違いがあるか検証します。

require 'benchmark'

Benchmark.bm do |x|
  array = []

  100.times do |n|
    # array の中身は [0, 1, 2, ..., 99]
    array.push(n)
  end

  # set の中身は { 0 => true, 1 => true, 2 => true, ..., 99 => true }
  set = array.to_set

  x.report('Array:') { array.include?(99) }
  x.report('Set:') { set.include?(99) }
end

結果は以下のようになりました。

$ ruby sample.rb
       user     system      total        real
Array: 0.000003   0.000001   0.000004 (  0.000003)
Set:   0.000001   0.000001   0.000002 (  0.000001)

たしかに配列よりSetの方が速いんですが、要素の数が100程度だと大して変わらないので、もっと要素の数を大きくしたいと思います。

require 'benchmark'

Benchmark.bm do |x|
  array = []

  1000.times do |n|
    # [0, 1, 2, ..., 999]
    array.push(n)
  end

  # { 0 => true, 1 => true, 2 => true, ..., 999 => true }
  set = array.to_set

  x.report('Array:') { array.include?(999) }
  x.report('Set:') { set.include?(999) }
end

要素の数を1000にしてみました。結果は次のとおり↓

$ ruby sample.rb
       user     system      total        real
Array: 0.000010   0.000001   0.000011 (  0.000007)
Set:   0.000001   0.000000   0.000001 (  0.000001)

Arrayクラスのinclude?メソッドの実行時間が0.000010秒なのに対し、Setクラスのinclude?メソッドの実行時間は0.000001秒と、10倍の差がつきました。

要素数が増えれば増えるほど、この差は大きくなっていきます。

Setクラスのinclude?メソッドを使うときの注意点

ここまでの話だと、ArrayクラスよりSetクラスのinclude?メソッドの方が性能が良さそうですが、つかうときは注意が必要です。

なぜなら、配列をSetオブジェクトへ変換する処理にも時間がかかるからです。

この変換処理では、配列の各要素をハッシュテーブルに挿入するため、要素数に応じて時間がかかります。

先ほどのサンプルコードを少し修正して、検証してみます。

require 'benchmark'

Benchmark.bm do |x|
  array = []

  1000.times do |n|
    # [0, 1, 2, ..., 999]
    array.push(n)
  end

  # 事前にSetクラスのオブジェクトに変換しない
  # set = array.to_set

  x.report('Array:') { array.include?(999) }
  # Set クラスのオブジェクトへの変換も含んだ実行時間を計測する
  x.report('Set:') { array.to_set.include?(999) }
end

実行結果は次のとおりです。

$ ruby sample.rb
       user     system      total        real
Array: 0.000007   0.000000   0.000007 (  0.000006)
Set:   0.000875   0.000285   0.001160 (  0.001931)

なんと、Setクラスの方が、処理時間がはるかに遅くなりました、、。

このことから、to_setで配列をSetオブジェクトに変換するのは、include?メソッドを複数回呼び出す場合だけにした方が良さそうです。

まとめ

• 要素数が少ない場合（数百程度）は、Arrayクラスのinclude?メソッドで十分
• 要素数が多い場合（数千以上）は、Setクラスのinclude?メソッドの方が高速
• ただし、配列からSetオブジェクトへの変換コストを考慮する必要あり
  • include?メソッドを何度も呼び出す場合はSetオブジェクトへの変換がお得
  • include?メソッドの呼び出しが1回きりならArrayクラスのままでOK

たしかにArrayクラスよりSetクラスのinclude?メソッドの方がパフォーマンスは良いんですが、配列からSetへの変換コストを考えると、Arrayクラスのinclude?メソッドをそのまま使った方が良いケースが多そうに感じました。