Effective Rubyの勉強メモです。

Array, Hashで存在確認する

コレクションにある指定された要素が存在しているかどうかのチェックには、通常Array#include?メソッドを使うかと思います。

例えば、次のような権限クラスを考えます。権限クラスはパーミッションの配列を持ち、ある権限が特定の行動を許可するかどうかを返すcan?メソッドを持っています。

class Role
  def initialize(name, permissions)
     @name = name
     @permissions = permissions
  end

  def can?(permission)
    @permission.include?(permission)
end

パーミッションが少ないときは問題ないですが、Array#include?はO(n)のオーダーで実行するのでパーミッションが増えるとパフォーマンスに問題が出てきます。（例えば、Railsアプリですべてのモデルに対してCRUDのパーミッションがあるかどうか）

そこで、速度を速めたければHashを使うことを検討します。

インターフェースはそのまま、

@permissions = Hash[permissions.map{|p| [p, true] }]

と変更するだけです。

Hash#include?を使うために、各パーミッションにはハッシュのキーとなってもらいました。

今回の場合は問題になりませんが、キーとして使うために重複した値を入れることができないという制限が追加されます。

また、配列からハッシュにするタイミングでより大きな配列をつくるため、initializeメソッドの負担が大きくなっています。

can?メソッドがわずかな回数しか呼ばれないのであればあまり高速化は期待できません。

この2つの条件と引き換えに、Hash#inlclude?は時間計算量O(logn)なのでパーミッションが多くなった時にArrayと比べると高速になります。

しかし、出来上がった@permissionsはハッシュとしての機能がほぼ使われず、ハッシュ化もあまりきれいではありません。

そこで、今回の要件に最適なSetクラスを使うことを検討します。

Setクラスを使う

Setクラスは「集合」を扱うクラスです。集合とは（ユニークな）オブジェクトの集まりのことです。

基本的に順序はなく、ただ集まっただけです。

Setクラスは標準ライブラリなのでrequireを忘れずに書きます。

require('set')

class Role
  def initialize(name, permissions)
     @name = name
     @permissions = Set.new(permissions)
  end

  def can?(permission)
    @permission.include?(permission)
end