webエンジニアの日常

RubyやPython, JSなど、IT関連の記事を書いています

Setクラスはこう使え!要素の存在確認をするならSetクラス

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

SetクラスはほとんどすべてのコレクションオブジェクトやEnumeratorから構築できるため、initializeメソッドもきれいに書くことができました。

また、Setクラスのinclude?は内部でHashクラスのinlcude?を使っているため(Hashに変換される)、処理は高速です。

標準ライブラリ

標準ライブラリという言葉が出てきました。

Rubyにはすべてのプログラムにプリロードされるコアライブラリと、(requireで)選択的に使うことができる標準ライブラリがあります。

コアライブラリは最低限必要な機能が含まれているため、requireなしで使うことができます。

対して標準ライブラリはもともとRubyに備わっているものですが、コアライブラリよりもかなり大きいので、requireで必要なものだけ使うことを要求しないと使うことができません。

何かと便利なgemが紹介されがちですが、標準ライブラリにも楽しくて便利なクラスがたくさんあるので(例えばerbとかは個人的に好き)どんなものがあるのか調べてみるといいかもしれません。

参考

  • Effective Ruby

本シリーズはこの本を勉強しながら進めています。

初心者には難しいと思いますが、知らなかったことばかりで面白いです!

Effective Ruby

Effective Ruby

  • Ruby on Railsアプリケーションプログラミング

Ruby単体よりもRailsを使うためにRubyを勉強される方が多いようです。

1冊Railsのオススメ書籍を載せておきます。

Ruby on Rails 5アプリケーションプログラミング

Ruby on Rails 5アプリケーションプログラミング

  • プロを目指す人のためのRuby入門

言語仕様から開発手法まで、幅広い話題が載っていて、これからRubyを始める方やほかの言語を学んでRubyを勉強したい方にお勧めです!