Yet another Ruby Memoization

night_stalker: http://www.iteye.com/topic/406220
Hooopo: http://www.iteye.com/topic/810957
两位大仙都讨论过Ruby Memoization
首先说一下什么是Memoization：
举个例子，fib数列：

def fib(n)
  return n if (0..1).include? n
  fib(n-1) + fib(n-2)
end

递归调用，有很多重复的计算，如果我们能够将计算过的结果保存下来，下一次
需要计算的时候，直接出结果就ok了，这就是动态规划的思想。
于是乎：

def fib(n)
     @result ||= []
     return n if (0..1).include? n
     @result[n] ||= fib(n-1) + fib(n-1)
end

我们使用一个@result数组来保存已经计算的结果，并且如果计算过直接返回。
||=是Ruby作为Lazy init和cache的惯用法。
但是对于false和nil的结果，由于||的特性，无效：

def may_i_use_qq_when_i_have_installed_360?
  @result ||= begin
     puts "我们做出了一个艰难的决定..."
     false
  end
end

每次都的做出艰难的决定...
James 写了一个module，http://blog.grayproductions.net/articles/caching_and_memoization可以专门用作Memoization
代码类似如下：

module Memoizable
    def memoize( name, cache = Hash.new )
        original = "__unmemoized_#{name}__"
        ([Class, Module].include?(self.class) ? self : self.class).class_eval do
            alias_method original, name
            private
            original
            define_method(name) { |*args| cache[args] ||= send(original, *args) }
        end
    end
end

使用这个模块，我们只需要include这个module,然后memoize :meth即可

include Memoizable

def fib(n)
    return n if (0..1).include? n
    fib(n-1) + fib(n-2)
end

memoize :fib

可以使用

module Functional
  #
  # Return a new lambda that caches the results of this function and 
  # only calls the function when new arguments are supplied.
  #
  def memoize
    cache = {}  # An empty cache. The lambda captures this in its closure.
    lambda {|*args|
      # notice that the hash key is the entire array of arguments!
      unless cache.has_key?(args)  # If no cached result for these args
        cache[args] = self[*args]  # Compute and cache the result
      end
      cache[args]                  # Return result from cache
    }
  end
  # A (probably unnecessary) unary + operator for memoization
  # Mnemonic: the + operator means "improved"
  alias +@ memoize        # cached_f = +f
end

class Proc; include Functional; end
class Method; include Functional; end

这样：

factorial = lambda {|x| return 1 if x==0; x*factorial[x-1]; }.memoize
# Or, using the unary operator syntax
factorial = +lambda {|x| return 1 if x==0; x*factorial[x-1]; }

James的博客很不错：
http://blog.grayproductions.net/

评论

4 楼 fuliang 2010-12-01  

恩，这样就ok了。

orcl_zhang 写道

3 楼 orcl_zhang 2010-11-29  

fuliang 写道

orcl_zhang 写道

这样true和false也能Memoization。很好。转载下。

false和nil还是不可以的。

有数组了，判断下has_key?就可以了吧？

module Memoizable
    def memoize( name, cache = Hash.new )
        original = "__unmemoized_#{name}__"
        ([Class, Module].include?(self.class) ? self : self.class).class_eval do
            alias_method original, name
            private
            original
            define_method(name) { |*args| cache.has_key?(args) ? cache[args] : cache[args] ||= send(original, *args) }
        end
    end
end

def may_i_use_qq_when_i_have_installed_360?  
  @result ||= begin  
     puts "我们做出了一个艰难的决定..."  
     false  
  end  
end 

cc = Hash.new
include Memoizable  
memoize :may_i_use_qq_when_i_have_installed_360?,cc


may_i_use_qq_when_i_have_installed_360?
may_i_use_qq_when_i_have_installed_360?
may_i_use_qq_when_i_have_installed_360?

def fib(n)  
    puts n
    return n if (0..1).include? n  
    fib(n-1) + fib(n-2)  
end  
  
memoize :fib ,cc

fib 10
fib 10
fib 10

irb(main):002:0> module Memoizable
irb(main):003:1>     def memoize( name, cache = Hash.new )
irb(main):004:2>         original = "__unmemoized_#{name}__"
irb(main):005:2>         ([Class, Module].include?(self.class) ? self : self.class).class_eval do
irb(main):006:3*             alias_method original, name
irb(main):007:3>             private
irb(main):008:3>             original
irb(main):009:3>             define_method(name) { |*args| cache.has_key?(args) ? cache[args] : cache[args] ||= send(original, *args) }
irb(main):010:3>         end
irb(main):011:2>     end
irb(main):012:1> end
=> nil
irb(main):013:0> 
irb(main):014:0* def may_i_use_qq_when_i_have_installed_360?  
irb(main):015:1>   @result ||= begin  
irb(main):016:2*      puts "我们做出了一个艰难的决定..."  
irb(main):017:2>      false  
irb(main):018:2>   end  
irb(main):019:1> end 
=> nil
irb(main):020:0> 
irb(main):021:0* cc = Hash.new
=> {}
irb(main):022:0> include Memoizable  
=> Object
irb(main):023:0> memoize :may_i_use_qq_when_i_have_installed_360?,cc
=> #<Proc:0xb7833db4@(irb):9>
irb(main):024:0> 
irb(main):025:0* 
irb(main):026:0* may_i_use_qq_when_i_have_installed_360?
我们做出了一个艰难的决定...
=> false
irb(main):027:0> may_i_use_qq_when_i_have_installed_360?
=> false
irb(main):028:0> may_i_use_qq_when_i_have_installed_360?
=> false
irb(main):029:0> 
irb(main):030:0* def fib(n)  
irb(main):031:1>     puts n
irb(main):032:1>     return n if (0..1).include? n  
irb(main):033:1>     fib(n-1) + fib(n-2)  
irb(main):034:1> end  
=> nil
irb(main):035:0>   
irb(main):036:0* memoize :fib ,cc
=> #<Proc:0xb7833db4@(irb):9>
irb(main):037:0> 
irb(main):038:0* fib 10
10
9
8
7
6
5
4
3
2
1
0
=> 55
irb(main):039:0> fib 10
=> 55
irb(main):040:0> fib 10
=> 55
irb(main):041:0> fib 10
=> 55
irb(main):042:0> cc
=> {[4]=>3, []=>false, [10]=>55, [1]=>1, [7]=>13, [0]=>0, [6]=>8, [3]=>2, [9]=>34, [2]=>1, [8]=>21, [5]=>5}
 

2 楼 fuliang 2010-11-29  

orcl_zhang 写道

这样true和false也能Memoization。很好。转载下。

false和nil还是不可以的。

1 楼 orcl_zhang 2010-11-28  

这样true和false也能Memoization。很好。转载下。