Memoistでメソッドをメモ化して処理を速くする

Memoist

いわゆるメモ化をサポートしてくれるライブラリのようです。
READMEには、ActiveSupport::Memoizableを抜き出した旨が書いてありました。

インストール

$ gem install memoist --no-ri --no-rdoc

使い方

READMEのまんまですが、クラスメソッドの場合はこんな感じで書くと良さそうです。

require 'memoist'

module Hoge
  class << self
    extend Memoist

    def fib(n)
      if n < 2
        n
      else
        fib(n-2) + fib(n-1)
      end
    end
    memoize :fib
  end
end

Hoge::fib(100) #=> 354224848179261915075
Hoge::fib(200) #=> 280571172992510140037611932413038677189525

ベンチマーク

せっかくなので、どれくらい高速化されたかベンチマークスクリプトを書いてみます。

fib.rb

#!/bin/env ruby

# fibonacci
# @param [Fixnum] n
# @return [Fixnum]
def fib(n)
  if n < 2
    n
  else
    fib(n - 2) + fib(n - 1)
  end
end

if __FILE__ == $0
  require 'optparse'
  require 'benchmark'

  # コマンド引数に -m を付けるとメモ化する.
  params = ARGV.getopts('m')
  if params["m"]
    require 'memoist'
    extend Memoist
    memoize :fib
  end

  Benchmark.bm do |bm|
    [20,30,40].each do |n|
      bm.report("fib(#{n})") {
        puts " #=> #{ fib(n) }"
      }
    end
  end
end

実行結果

メモ化なし版

$ ruby fib.rb
       user     system      total        real
fib(20) #=> 6765
  0.010000   0.000000   0.010000 (  0.002523)
fib(30) #=> 832040
  0.320000   0.000000   0.320000 (  0.327861)
fib(40) #=> 102334155
 38.940000   0.010000  38.950000 ( 39.023283)

メモ化あり版

$ ruby fib.rb -m
       user     system      total        real
fib(20) #=> 6765
  0.000000   0.000000   0.000000 (  0.000663)
fib(30) #=> 832040
  0.000000   0.000000   0.000000 (  0.000657)
fib(40) #=> 102334155
  0.000000   0.000000   0.000000 (  0.000176)

メモ化することで如実に速くなってます。
なにより高速化するにあたり既存のロジックを修正しなくて済むのがラクですね。