【Ruby on Rails】Set#include?がなぜ速いのかを理解する #AdventCalendar2020

はじめに

この記事は食べログ Advent Calendar 2020 18日目の記事です。

こんにちは、食べログWebエンジニアの@an_sonyです。
普段は予約サービスのシステム開発をしています。

最近、GoToEatオンライン事業により予約サービスの利用者が増加し（ご利用ありがとうございます！）パフォーマンスチューニングをすることが増えました。

そのチューニング方法の一つで、リストの要素検索処理をArray#include?ではなくSet#include? を使って高速化する をよく使ったのですが、ある時「あれ、ArrayとSetって見た目は似てるのに、なんでこの処理って速いんだろう？」という疑問が浮かびました。

この理由、みなさん答えられますか？

解明するにはSetクラスの中身（実装）を見れば良さそうなのですが、そういえば自分、RubyやRailsの中身を一度も見たことありませんでした。。なので良い機会だと思い、中身を見て解明しようと思います。

↓読んでほしい人

・Setクラスを知らない、ちゃんと理解していない人
・Ruby、Rails初心者〜中級者

そもそもSetクラスって？

「集合」を扱うクラスです。集合とはユニークなオブジェクトの集まりのことです。
要素の間に特に順序関係はありません。

配列を渡せばセットを作成できます。この際、重複した要素は削除されます。

[1] pry(main)> s = Set.new([1, 2, 1])
=> #<Set: {1, 2}>

Set#include?はArray#include?を同じ使い方です。

[2] pry(main)> s.include?(1)
=> true
[3] pry(main)> s.include?(3)
=> false

どんな時に使うの？

Set#include?はArray#include?と比較して、特に要素数が多い場合に速いです。（ここでは計測比較しません）なのでバッチ処理など大量データを扱う時にすごく重宝します。

で、なんで速いのよ？

公式リファレンスを見てみると、こんな説明がありました。

Array の持つ演算機能と Hash の高速な検索機能を合わせ持ちます。
内部記憶として Hash を使います。

ArrayとHashの良いとこ取りをしたクラスなんですね。
そして、どうやら高速化を実現しているのはHashの検索機能のようです。

どういうことか言うと、データ探索アルゴリズムの一つである「ハッシュ法」によって実現しています。ハッシュ法とは、データをメモリに格納する時にデータの格納位置を決めておくことで、特定データを一発で探せるようにする方式です。格納位置は一定の計算式（ハッシュ関数）によって求めます。※正確にはRubyはチェイン法を使っています。
これによって、どれだけ大量のデータだとしても高速に検索することが可能です。

中身を見てみる

ではSetクラスの中身を見ていきましょう。
まずSet.newした時の中身はこれ↓

# Creates a new set containing the elements of the given enumerable
# object.
#
# If a block is given, the elements of enum are preprocessed by the
# given block.
#
#     Set.new([1, 2])                       #=> #<Set: {1, 2}>
#     Set.new([1, 2, 1])                    #=> #<Set: {1, 2}>
#     Set.new([1, 'c', :s])                 #=> #<Set: {1, "c", :s}>
#     Set.new(1..5)                         #=> #<Set: {1, 2, 3, 4, 5}>
#     Set.new([1, 2, 3]) { |x| x * x }      #=> #<Set: {1, 4, 9}>
def initialize(enum = nil, &block) # :yields: o
  @hash ||= Hash.new(false)

  enum.nil? and return

  if block
    do_with_enum(enum) { |o| add(block[o]) }
  else
    merge(enum)
  end
end

いきなりHash.newしてます。
Set.new([1, 2, 1])をするとしたら、blockはないのでmergeメソッドを呼び出しています。
mergeメソッドをみてみます。

# Merges the elements of the given enumerable object to the set and
# returns self.
def merge(enum)
  if enum.instance_of?(self.class)
    @hash.update(enum.instance_variable_get(:@hash))
  else
    do_with_enum(enum) { |o| add(o) }
  end

  self
end

Set.new([1, 2, 1])の場合、addを呼び出しているようです。
addは何をしているかというと、

# Adds the given object to the set and returns self.  Use +merge+ to
# add many elements at once.
#
#     Set[1, 2].add(3)                    #=> #<Set: {1, 2, 3}>
#     Set[1, 2].add([3, 4])               #=> #<Set: {1, 2, [3, 4]}>
#     Set[1, 2].add(2)                    #=> #<Set: {1, 2}>
def add(o)
  @hash[o] = true
  self
end
alias << add

@hashのkeyをセットしています。

つまり、Set.new([1, 2, 1])を実行すると内部では

@hash = {1=>true, 2=>true}

こんな感じでHashのインスタンス変数が作られるようです。
なるほど〜

ではSet#include?は何をやっているか。（予想できちゃいますが。。）

# Returns true if the set contains the given object.
#
# Note that <code>include?</code> and <code>member?</code> do not test member
# equality using <code>==</code> as do other Enumerables.
#
# See also Enumerable#include?
def include?(o)
  @hash[o]
end
alias member? include?

はい、引数のoが@hashのkeyに存在するかで判定しています。
まぁそうですよね。

つまり、Set#include?の中身は
・Hash型のインスタンス変数を作成し、keyに値をセットする
・include?の引数の値がkeyに存在するかで判定

やっていることはHash#include?と一緒ですね。

計算量オーダーも見てみる

計算量オーダーはなんぞや？って人はこちらを参考ください↓
参考: 計算量オーダーについて

メソッド	計算量オーダー
Set#include?, Hash#Include?	O(logn)
Array#Include?	O(n)

Set#include?とHash#include?はO(logn)です。なので要素が増えても処理が遅くなりにくいです。

一方Array#include? は計算量がO(n) のため、要素が増える分処理が遅くなります。
これもArray#include?の中身を見て遅い理由を解明してみます。（C言語ですが...）

/*
 *  call-seq:
 *    array.include?(obj) -> true or false
 *
 *  Returns +true+ if for some index +i+ in +self+, <tt>obj == self[i]</tt>;
 *  otherwise +false+:
 *    [0, 1, 2].include?(2) # => true
 *    [0, 1, 2].include?(3) # => false
 */

VALUE
rb_ary_includes(VALUE ary, VALUE item)
{
    long i;
    VALUE e;

    for (i=0; i<RARRAY_LEN(ary); i++) {
  e = RARRAY_AREF(ary, i);
  if (rb_equal(e, item)) {
      return Qtrue;
  }
    }
    return Qfalse;
}

aryの長さだけfor文でループしています。
なのでaryの要素数が多いと、その分ループ処理が長くなります。
だからO(n) なんですね。

さらに調べてわかったこと

`Hash#include?`も最近進化している

Hashクラスについても調べていたのですが、Ruby2.6でTransient Heapという技術が取り入れられた際に、Hashの探索方法を工夫したという記事を見つけました。

Transient Heap の工夫：Hash の実装

他言語でも使われているSet

別の言語ですが、PythonでもSet型があり、List型と比較して要素検索が高速化するようです。この高速化も仕組みは一緒で、ハッシュ法によって実現しています。

Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由

まとめ

これでSet#include?の仕組みと、なぜ速いのかを解明することができました。
普段コードを書いている時は、クラスやメソッドの中身をあまり意識していないことが多いと思いますが、仕組みを知ることでベースとなる技術の理解促進になるので、時間がある時にRubyやRailsの中身を覗いてみるのをオススメします。

明日は@sarataniさんの「Asanaを使ってデイリーMTGがちょっと楽になった話」です。お楽しみに！

参考URL

https://docs.ruby-lang.org/ja/latest/class/Set.html
https://i.loveruby.net/ja/rhg/book/name.html
https://techlife.cookpad.com/entry/2018/12/27/093914
https://qiita.com/kitadakyou/items/6f877edd263f097e78f4

【Ruby on Rails】Set#include?がなぜ速いのかを理解する