Memoization in Ruby

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

缓存方法结果：

举个最简单常用的例子：
Ruby代码

   1. class ApplicationController < ActionController::Base   
   2.     def current_user   
   3.         User.find(session[:user_id])   
   4.     end   
   5. end  

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


vs.

Ruby代码

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

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



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


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

Ruby代码

   1. def may_i_help_u? 
   2.   @result ||= begin 
   3.       此处是一个耗时很长的判断。。 
   4.       puts "我被执行了！" 
   5.       false 
   6.     end 
   7. end 

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



连续两次调用该方法：

Ruby代码

   1. may_i_help_u? => 我被执行了！. 
   2. may_i_help_u? => 我被执行了！ 

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



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


更通用的memoization：


Ruby代码

   1. def some_method(*args) 
   2.   @some_method ||= {} 
   3.   @some_method[args] ||= ( 
   4.     这里要等很久 
   5.   ) 
   6. end 

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



用方法名对应的实例变量存储结果集，结果集为ruby的hash，不同的参数对应相应的返回值。

这个实现虽然支持了参数形式，缺点同样是不能缓存nil和false返回值。


继续改造：


Ruby代码

   1. def some_method(*args) 
   2.   @some_method ||= {} 
   3.   return @some_method[args] if @some_method.has_key?(args) 
   4.    
   5.   @some_method[args] = ( 
   6.     这里要等很久 
   7.   ) 
   8. end 

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



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


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

Ruby代码

   1. extend ActiveSupport::Memoizable 
   2.  
   3. def zipcode_and_name 
   4.   "{zipcode} {name}" 
   5. end 
   6. memoize :zipcode_and_name 

extend ActiveSupport::Memoizable

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



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


Ruby代码

   1. class << self 
   2.   extend ActiveSupport::Memoizable 
   3.  
   4.   def a_class_method 
   5.      some code 
   6.   end 
   7.   memoize :a_class_method 
   8. end 

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本身就不是万金油，也不能滥用。。特别是当方法参数和返回不是一一映射时，比如这两个方法：


随机数：

Java代码

   1. def rank(n) 
   2.  rand(n*n) 
   3. end 

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



与动态数据紧密相关的：

Ruby代码

   1. def age 
   2.   today = Date.today 
   3.   today.year - birth_date.year + (today.month - birth_date.month + ((today.day - birth_date.day) < 0 ? -1 : 0) < 0 ? -1 : 0) 
   4. 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编程语言》

Ruby代码

   1. module Functional 
   2.   def memoize 
   3.     cache = {} 
   4.     lambda {|*args| 
   5.       unless cache.has_key? args 
   6.         cache[args] = self[*args] 
   7.       end 
   8.       cache[args] 
   9.    } 
  10.   end 
  11.   alias +@ memoize 
  12.  
  13. end 
  14.  
  15. Proc.send(:include, Functional) 
  16.  
  17. fac = lambda{|x| return 1 if x == 0; x * fac[x - 1];}.memoize 
  18. 或fac = +lambda{|x| return 1 if x == 0; x * fac[x - 1];} 

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 不缓存结果。

在建项目：www.viila.net欢迎各位大侠攻击指教