Memoization in Ruby

这里的Memoization就是将ruby的方法或lambda返回值缓存起来的技术。

缓存方法结果：

举个最简单常用的例子：

class ApplicationController < ActionController::Base  
    def current_user  
        User.find(session[:user_id])  
    end  
end 

vs.

class ApplicationController < ActionController::Base  
    def current_user  
        @current_user ||= User.find(session[:user_id]) 
    end  
end  

下面代码的好处显而易见，在一次请求中最多只调用一次取session和查db操作。

||=这个操作适用于单行赋值操作。是ruby的惯用法之一，一般情况下ruby的||=就可以解决类似的缓存功能。但是情况并不是那么简单，看下面代码：

def may_i_help_u?
  @result ||= begin
      #此处是一个耗时很长的判断。。
      puts "我被执行了！"
      false
    end
end

连续两次调用该方法：

may_i_help_u? #=> 我被执行了！.
may_i_help_u? #=> 我被执行了！

由于||=操作的特性，这里对nil和false返回就不能做缓存了。。还有一个缺点就是不能缓存带参数的方法。。

更通用的memoization：

def some_method(*args)
  @some_method ||= {}
  @some_method[args] ||= (
    #这里要等很久
  )
end

用方法名对应的实例变量存储结果集，结果集为ruby的hash，不同的参数对应相应的返回值。
这个实现虽然支持了参数形式，缺点同样是不能缓存nil和false返回值。

继续改造：

def some_method(*args)
  @some_method ||= {}
  return @some_method[args] if @some_method.has_key?(args)
  
  @some_method[args] = (
    #这里要等很久
  )
end

嗯，可以缓存nil或false返回值了，也可以支持多参数了。不过如果每个方法里这么写也有点烦躁。。

还好ActiveSupport已经写好了这个扩展，使用起来也很方便：

extend ActiveSupport::Memoizable

def zipcode_and_name
  "#{zipcode} #{name}"
end
memoize :zipcode_and_name

Memoization类方法也很简单，ruby里类方法只不过是Class的实例，只需打开metaclass：

class << self
  extend ActiveSupport::Memoizable

  def a_class_method
    # some code
  end
  memoize :a_class_method
end

ActiveSupport::Memoizable的实现方式和上面的思路一样，不过用了很多元编程技巧，使用起来才这么方便。
PS：最近面试总有些面试官喜欢问元编程，问神马是元编程，ruby里怎样元编程。。答案无非是“程序运行时动态改变自身”“method_missing、各种eval、define_method、反射等等”
我觉得还不如找些简单功能说说实现方案/思路来的实在。。

这个memoizable同样都不能正确处理带block参数的方法。因为这个memoization本身就不是万金油，也不能滥用。。特别是当方法参数和返回不是一一映射时，比如这两个方法：

随机数：

def rank(n)
 rand(n*n)
end

与动态数据紧密相关的：

def age
  today = Date.today
  today.year - birth_date.year + (today.month - birth_date.month + ((today.day - birth_date.day) < 0 ? -1 : 0) < 0 ? -1 : 0)
end

缓存Proc/lambda结果：

Via：《Ruby编程语言》

module Functional
  def memoize
    cache = {}
    lambda {|*args|
      unless cache.has_key? args
        cache[args] = self[*args]
      end
      cache[args]
   }
  end
  alias +@ memoize

end

Proc.send(:include, Functional)

fac = lambda{|x| return 1 if x == 0; x * fac[x - 1];}.memoize
#或fac = +lambda{|x| return 1 if x == 0; x * fac[x - 1];}

ruby的Hash是个好东西，可以传递Proc做参数，并且缓存结果。

引用

Hash 映射和 Proc 映射区别在于： Hash 带有缓存机制，而 Proc 不缓存结果。

更多关于Proc memoize的内容见NS的这篇：http://www.iteye.com/topic/406220

评论

7 楼 orcl_zhang 2010-12-08  

activesupport/lib/active_support/memoizable.rb

6 楼 wxz125627771 2010-11-20  

ray_linn 写道

=java里方法的cache吧？适用于p=f(x)，当x既定时，p不变。

5 楼 ywencn 2010-11-19  

Hooopo又调皮了.. 送精华一枚...

4 楼 ray_linn 2010-11-18  

=java里方法的cache吧？适用于p=f(x)，当x既定时，p不变。

3 楼 sina2009 2010-11-18  

收藏起....

2 楼 jinleileiking 2010-11-18  

hoooopoooooo 你说的东西，我看不懂！（也没仔细看。。。。）

1 楼 fireflyman 2010-11-15  

Hooopo总算复活了