search
LoginSignup
15

More than 5 years have passed since last update.

posted at

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)

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
15