ruby - Ruby Pascal 的带记忆功能的三角形生成器

Question

我正在尝试记忆我的 Pascal 三角形生成器的实现，作为 Ruby 学习实验。我有以下工作代码：

module PascalMemo
  @cache = {}
  def PascalMemo::get(r,c)
    if @cache[[r,c]].nil? then 
      if c == 0 || c == r then 
        @cache[[r,c]] = 1
      else
        @cache[[r,c]] = PascalMemo::get(r - 1, c) + PascalMemo::get(r - 1, c - 1)
      end
    end
    @cache[[r,c]]
  end
end

def pascal_memo (r,c)
  PascalMemo::get(r,c)
end

这可以更简洁吗？具体来说，我可以比这更简单地创建一个具有局部闭包的全局范围函数吗？

Answer 1

def pascal_memo
  cache = [[1]]
  get = lambda { |r, c|
    ( cache[r] or cache[r] = [1] + [nil] * (r - 1) + [1] )[c] or
      cache[r][c] = get.(r - 1, c) + get.(r - 1, c - 1)
  }
end

p = pascal_memo
p.( 10, 7 ) #=> 120

请注意，上面的构造确实实现了记忆化，它不仅仅是一个简单的递归方法。

Answer 2

这可以更简洁吗？

看起来很清楚，IMO，moduleing 通常是一种很好的直觉。

我可以比这更简单地创建一个具有本地闭包的全局范围的函数吗？

另一种选择是递归lambda：

memo = {}

pascal_memo = lambda do |r, c|
  if memo[[r,c]].nil?
    if c == 0 || c == r
      memo[[r,c]] = 1
    else
      memo[[r,c]] = pascal_memo[r - 1, c] + pascal_memo[r - 1, c - 1]
    end
  end
  memo[[r,c]]
end

pascal_memo[10, 2]
# => 45

Answer 3

我找到了一种方法来完成我想要的稍微令人满意的事情，因为它产生了一个函数而不是 lambda：

class << self
  cache = {}

  define_method :pascal_memo do |r,c|
    cache[[r,c]] or 
    (if c == 0 or c == r then cache[[r,c]] = 1 else nil end) or 
    cache[[r,c]] = pascal_memo(r-1,c) + pascal_memo(r-1,c-1)
  end
end

这会为主对象打开元类/单例类，然后使用 define_method 添加一个新方法来关闭缓存变量，然后除了 pascal_memo 方法之外，该方法超出了所有内容的范围。