RubyのSet#include? で効率化

項目18 要素が含まれているかどうかの処理を効率よく行うために集合を使うことを検討しよう

作者:Peter J.Jones
翔泳社

先ずはArray

Array#include? は計算量がO(n) 。

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

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

Hashを使うと高速化できる

メモリを消費するが、要素へのアクセスはO(log n)。
ハッシュの値はtrueを使うとイミュータブルなグローバル変数となり効率的。

class Role
  def initialize(name, permissions)
    @name = name
    @permissions = Hash[permissions.map { |p| [p, true] } ]
  end

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

ただし、注意点としては、重複が失われることと、配列をHash化するためにさらに大きな配列を作成していること。#can? の効率化を図ったが、結果 #initialize のコストが増加しているので #can? の呼び出し回数が少なければ効果は少ない。

そこでSetですよ

Hashの例はかっこが多くて見にくい。そしてHashの特別な機能を使っているわけではない。
SetクラスはHashに要素を格納するので、Hashと同等のパフォーマンスが出る。

require "set"

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

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

覚えておくべき事項

要素が含まれているかどうかの高速チェックではSetを使うことを検討しよう
Setに挿入されるオブジェクトは、ハッシュキーとしても使えなければならない。