如何一般地记忆 Ruby 中的任何函数？

Question

我正在尝试编写一个函数来通用地记忆 Ruby 中的任何函数（如本文第 6 页所述，它在 Python 中做同样的事情：http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf ), 但我被卡住了。这是我的代码，它不起作用（函数被正确评估，但没有被记住）。谁能告诉我哪里出错了？

def fib(n)
  return n if n<2
  fib(n-1) + fib(n-2)
end

def memoize(&f)
  memo = {}
  doit = ->(arg) do
    return memo[arg] if memo[arg] 
    memo[arg] = f.call(arg)
    memo[arg]
  end
  doit
end

fib = memoize{|x| fib(x)}
puts fib.call(50)

Answer 1

在python中，函数是可调用的对象，它们的名字只是存储这些对象的变量的名字，所以你可以给那个变量赋一个新的值，使函数的功能完全不同.

但是在ruby中，方法不是对象，它们的名字也不是变量名。要覆盖原始文件，您必须再次 def 它。

这是我的解决方案：

def fib(n)
  return n if n<2
  fib(n-1) + fib(n-2)
end

alias _fib fib

def fib(n)
  $memo ||= {}
  $memo[n] ||= _fib(n)
end

fib(50)  #=> 12586269025

我使用了旧的 ruby 技巧：制作一个别名并覆盖原来的。这很讨厌（因为在覆盖之后有一个额外的 _fib），但这是最简单的方法。

Answer 2

fib 递归调用自身，并通过这样做完全绕过您的记忆逻辑。无论您选择哪种方法，您都必须覆盖 fib 的原始定义，以围绕它包装记忆。

@Aetherus 给出了有效的答案。这是一个更动态的解决方案：

def fib(n)
  return n if n<2
  fib(n-1) + fib(n-2)
end

def memoize(method_name)
  memo = {}
  old_fib = method(method_name)
  define_method(method_name) do |arg|
    return memo[arg] if memo[arg] 
    memo[arg] = old_fib.call(arg)
    memo[arg]
  end
end

memoize(:fib)

puts fib(50)

Answer 3

您可以使用方法装饰器模式，here 是您可以用作库的示例实现：

require "method_decorators/memoize"

class MyMath
  extend MethodDecorators

  +MethodDecorators::Memoize
  def self.fib(n)
    if n <= 1
      1
    else
      fib(n - 1) * fib(n - 2)
    end
  end
end

puts MyMath.fib(200)

Answer 4

如果您来到这里寻找 lambda 的解决方案，这将很有用：

fib = ->(memo, n) {
  return n if n < 2
  
  memo[n] ||= fib[n-1] + fib[n-2]
}.curry[Hash.new]

fib.(6)

一个“调试”版本，以防您想可视化正在发生的事情。

fib = ->(memo, n) {
  return n if n < 2
  
  memo[n] ||= begin
    puts 'calculating'
    fib[n-1] + fib[n-2]
  end
}.curry[Hash.new]

ps：需要ruby 2.5或以上 https://apidock.com/ruby/Proc/curry

如何一般地记忆 Ruby 中的任何函数？

How to generically memoize any function in Ruby?

ruby

memoization