名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

Ruby で メモ化カッコカリ( #rubytokai 発表メモ)

昨日の Ruby東海 第32回 勉強会 で、メモ化の発表をしてきました。

資料を作る暇(と体力)がなかったのですが、とりあえず発表内容をまとめておきます。

自己紹介

メモ化とは?

Ruby でメモ化(仮)

  • [資料]の Probrem 節を説明
    • 「if 式とその後の <%= 〜 %> で同じメソッドを呼んで、同じ計算を 2 回している。もったいないよね?」
  • [資料]の Caching with instance variable 節を説明
    • Ruby ではよくこういう書き方をします:」
  def total_budget
    @total_budget ||= self.available_accounts.inject(0) { |sum, a| sum += a.budget }
  end
    • 説明:
      • @total_budget …「@〜」はインスタンス変数。
      • ||= …左辺値が定義されていなかったら、右辺値を評価(計算)して代入する、という Ruby の複合代入演算子
      • この書き方は Ruby でよく使われる(初期化時のイディオムの 1 つ)。以下と同じ意味になる*2
  def total_budget
    if @total_budget
      @total_budget
    else
      @total_budget = self.available_accounts.inject(0) { |sum, a| sum += a.budget }
    end
  end
  • [資料]の Memoizable 節を説明
    • ActiveSupport::Memoizable というのを使うと、シンプルに以下のように書けます(ました):
  extend ActiveSupport::Memoizable

  def total_budget
    self.available_accounts.inject(0) { |sum, a| sum += a.budget }
  end

  def total_spent(start_date, end_date)
    self.available_accounts.where('created_at >= ? and created_at <= ?', start_date, end_date).inject(0) { |sum, a| sum += a.spent }
  end
  memoize :total_budget, :total_spent
      • extend ActiveSupport::Memoizable …後の memoize 《メソッド名》 という記述をするための準備
      • memoize :total_budget, :total_spent …引数に指定したメソッド名のメソッドを「メモ化メソッド」に置き換える。
      • この書き方の利点
        • 上記の例のように、引数が(複数)存在するメソッドでも手軽にメモ化できる。
        • メソッド定義がスッキリする♪
    • 「書けました」と過去形なのは、ActiveSupport::Memoizable が廃止されて現在は使えないから(>_<)
      • 元の記事も「ActiveSupport::Memoizable が Deprecated になったからこれからは〜」という内容。
  • Memoist gem の説明
    • matthewrudy/memoist · GitHub
    • ↑で説明した ActiveSupport::Memoizable をほぼそのまま抽出した gem。[資料]でも紹介されている。
    • ActiveSupport::Memoizable でやっていたことがそのままできる:
  extend Memoist

  def total_budget
    self.available_accounts.inject(0) { |sum, a| sum += a.budget }
  end

  def total_spent(start_date, end_date)
    self.available_accounts.where('created_at >= ? and created_at <= ?', start_date, end_date).inject(0) { |sum, a| sum += a.spent }
  end
  memoize :total_budget, :total_spent

(素の)Ruby でメモ化(引数対応)

  • gem を使わずに引数の存在するメソッドのメモ化をしてみよう!
  • 説明簡単化のため、[資料]に出てきた2引数のメソッドを1引数にして考えます。
  def total_spent(start_date)
    self.available_accounts.where('created_at >= ? and created_at <= ?', start_date, @end_date).inject(0) { |sum, a| sum += a.spent }
  end
  • まず、↓のようにした場合どうなる?
  def total_spent(start_date)
    @total_spent ||= self.available_accounts.where('created_at >= ? and created_at <= ?', start_date, @end_date).inject(0) { |sum, a| sum += a.spent }
  end
    • 異なる start_date で計算しようとしても、前の計算結果が記憶されていてその値が返ってきてしまう。
    • 例えば、2014/01/01 からの経過日数を取得(例えば60日)した後、2014/03/01 からの経過日数を取得(結果は1日になるはず?)しようとしても、期待した結果が返ってこない(60日と返ってくる(>_<))
  • こうすればうまくいきます!
  def total_spent(start_date)
    @total_spent ||= Hash.new do |hash, key|
      hash[key] = self.available_accounts.where('created_at >= ? and created_at <= ?', key, @end_date).inject(0) { |sum, a| sum += a.spent }
    end
    @total_spent[start_date]
  end
    • Hash.new do |hash, key| 〜 endHashインスタンス生成時にブロックを渡すと、key が登録されていないときにそのブロックを実行し、実行結果を値として返す。
      • ブロックの第1引数はその Hash 自身、第2引数は key
      • このブロックは、定義時には呼ばれず key が存在しないときのみ実行される(遅延実行)*3
      • そのブロック内で hash[key] = 〜 という記述をすると、その計算結果をそのまま登録つまり記憶することができる
        →2回目以降同じキーが来たら再計算せず記憶した値を返すだけ(=メモ化!)
    • ↑を @total_spent ||= インスタンス変数に(まだなければ)登録。つまりメソッドが最初に呼ばれたときのみ Hash を生成。
      →別の引数で呼び出されたとき、
      • Hash オブジェクトは既に存在しているので、そのまま利用(以前の結果はそのまま残っている)。
      • 新しい引数に対応する値はまだ存在しないので、ブロックが実行されて計算処理が走り、結果を記憶すると共にその値が返ってくる。
  • 引数が複数ある場合は、key として配列を渡せばOK:
  def total_spent(start_date, end_date)
    @total_spent ||= Hash.new do |hash, key|
      hash[key] = self.available_accounts.where('created_at >= ? and created_at <= ?', key[0], key[1]).inject(0) { |sum, a| sum += a.spent }
    end
    @total_spent[[start_date, end_date]]
  end

Integer クラスでメモ化

  • 整数の計算でも、メモ化したいことが(個人的に)あります:
class Integer
  def sq
    @sq ||= self ** 2
    # This raises RuntimeError on Ruby >= 2.0.x
  end
end
require 'numeric_memoist'

class Integer
  extend NumericMemoist

  def sq
    self ** 2
  end
  memoize :sq
end
    • 参考:Memoist gem を使用すると、RuntimeError にはならないよう工夫はされていますが、メモ化は有効に働きません。例えば以下のようにすると毎回きちんと5秒待たされます(´・_・`)
require 'memoist'

class Integer
  extend Memoist

  def sq
    sleep 5
    self ** 2
  end
  memoize :sq
  # No Error raised, but momeize doesn't work on Ruby >= 2.0.x
end

注意点・その他その場ででた議論とか

  • 1点注意:[資料]でも言及されている通り、@xx ||= の書き方には1つだけ注意点があります。
    計算結果が nil または false の場合、2回目に呼ばれたときの左辺値が false 扱いになるので、再計算が走ってしまいます(>_<)
    • 対処法:以下のようにすれば回避可能:
def has_comment?
  return @has_comment if defined?(@has_comment)
  @has_comment = self.comments.size > 0
end
    • Memoist や拙作の NumericMemoist は、ちゃんと対応しているので心配不要。
  • この[資料]は Rails の Practice ということで ActiveRecord を例にしているが、内部で query cache も働くので、毎回 DB アクセスするわけではないため、改めてメモ化しても実際には効果は薄いかもしれない。
    • inject で合計値の計算をしているので、件数が多い場合にその計算分は省略できるかも。
    • query cache も、デフォルトだとファイルにキャッシュしたりして、必ずしもスピードは出ないことがある?
  • 複数引数の場合で配列をキーにした場合、結構メモリを要する。
    そうでなくてもメモ化は、メモリを犠牲にしてパフォーマンスを確保する効率化手法の一つ。多用するとどんどんメモリを圧迫(>_<)
    • →ご利用は計画的に。
その場で出なかった(出せなかった)お話とか
  • 本当は「参照透過性」の話とか、「情報工学的な正確性を期したメモ化の話をした上で『これは本当にメモ化なのか!?』というマサカリ投げ」もしてみたかった。

*1:2015/08/03 リンク切れを修正。

*2:Ruby では文も式であり値を持ち、さらにメソッドは return がなければ最後の式の値が戻り値になるので、どちらも最終的に「そのインスタンス変数の値か、インスタンス変数に代入した結果」が返ってきます。

*3:Array も new 時に、配列に格納する値を計算するブロックを渡すことが出来ますが、遅延実行ではなく即時実行されます。

*4:「そのようなプログラムは窓から外に放り出しましょう」て言われて悲しくなりました。投げないでー