Yet another Ruby Memoization_Ruby_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > Ruby > Yet another Ruby Memoization

Yet another Ruby Memoization

 2010/12/5 13:14:03  fuliang  http://fuliang.javaeye.com  我要评论(0)
  • 摘要:night_stalker:http://www.javaeye.com/topic/406220Hooopo:http://www.javaeye.com/topic/810957两位大仙都讨论过RubyMemoization首先说一下什么是Memoization:举个例子,fib数列:deffib(n)returnnif(0..1).include?nfib(n-1)+fib(n-2)end递归调用,有很多重复的计算,如果我们能够将计算过的结果保存下来,下一次需要计算的时候
  • 标签:
night_stalker: http://www.javaeye.com/topic/406220
Hooopo: http://www.javaeye.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

James的博客很不错:
http://blog.grayproductions.net/
  • 相关文章
发表评论
用户名: 匿名