在 Ruby 方法中创建缓存

Question

在JavaScript中，记忆斐波那契这样的函数相当简单：

// In JavaScript

var fibonacci = (function () {
  var cache = {}; // cache for future calculations

  return function (num) {
    if (num < 0)    throw new Error('Negative numbers not allowed');
    if (num === 0)  return 0;
    if (num === 1)  return 1;

    cache[num] = cache[num] || fibonacci(num - 1) + fibonacci(num - 2);
    return cache[num];
  };
})();

console.log( fibonacci(5) ); // results in 5
console.dir( fibonacci ); // you can inspect the closure scope and see that the cache object saves the values for future use

我试图了解如何在 Ruby 中做类似的事情，不幸的是，我唯一能想到的就是创建一个 class 并将缓存存储为 class 变量：

# In Ruby
class Placeholder
  @@cache = {}

  def fibonacci(num)
    raise 'Negative numbers not allowed' if num < 0
    return 0 if num == 0
    return 1 if num == 1

    @@cache[num] ||= fibonacci(num - 1) + fibonacci(num - 2)
  end
end

example = Placeholder.new
puts example.fibonacci(5) # results in 5

我不喜欢这个的事实是，当我并不真正打算创建 Placeholder 的实例时，我正在创建一个 class 结构。相反，我这样做只是因为我想将状态保存在 Ruby class 变量中。理想情况下，如果我能够创建一个 module 并拥有一个 module 变量，那么这至少可以解决我使用基于 class 的解决方案的 "problem" 实例化问题。 在 Ruby 中，您对此有何最佳建议？

根据@meagar 的评论更新：

@meagar，你是在建议这样的事情吗？

class Placeholder
  attr_reader :cache

  def initialize
    @cache = {}
  end

  def fibonacci(num)
    raise 'Negative numbers not allowed' if num  < 0
    return 0 if num == 0
    return 1 if num == 1

    @cache[num] ||= fibonacci(num - 1) + fibonacci(num - 2)
  end
end

FibonacciCalculator = Placeholder.new
puts FibonacciCalculator.fibonacci(5) # results in 5

我已经比我最初的 Ruby 解决方案更喜欢这个了，尽管占位符 class 仍然让我感到不快。

Answer 1

... a class structure when I don't really intend to create instances of Placeholder

嗯，这就是你的问题。

Ruby 是一种面向对象的语言。您不能拥有不属于对象的功能。 对一个对象调用每个方法。

您应该简单地创建一个 Placeholder 的实例（并给它一个合适的名称，例如 FibonacciCalculator），并使您的缓存成为该对象上的一个简单实例变量。

Answer 2

当您不需要实例时，您可以使用 Module 和单例方法：

module Fibonacci
  @cache = {}

  def self.series(num)
    if @cache[num] then return @cache[num]; end
    if num  < 0 then raise 'Negative numbers not allowed'; end
    if num == 0 then return 0; end
    if num == 1 then return 1; end

    @cache[num] = series(num - 1) + series(num - 2)
  end
end

puts Fibonacci.series(5) # results in 5

请注意，对于缓存，Fibonacci 模块上的实例变量与 class 变量一样有效（对于某些扩展用途，它可能会更好）。它之所以有效，是因为模块 Fibonacci 是 Module 的实例 - 在这方面它与任何其他实例变量相同。

Answer 3

您还可以使用闭包存储缓存，这与 javascript 的做法类似。

def memoize func
  cache = {}
  proc do |*args|
    next cache[args] if cache[args]
    cache[args] = func[*args]
  end
end

def slow_double x
  sleep 2
  x * 2
end

memoized_double = memoize(method :slow_double)

memoized_double[4] # takes 2 seconds
memoized_double[4] # returns instantly

Answer 4

您的 ECMAScript 版本的字面翻译是这样的：

fibonacci = -> {
  cache = {} # cache for future calculations

  -> num {
    raise ArgumentError, 'Negative numbers not allowed' if (num < 0)
    return 0 if num.zero?
    return 1 if num == 1

    cache[num] ||= fibonacci.(num - 1) + fibonacci.(num - 2)
  }
}.()

fibonacci.(5)
# => 5
fibonacci.binding.local_variable_get(:cache)
# => {2=>1, 3=>2, 4=>3, 5=>5}

顺便说一句，我们可以做一些简化：如果 num 是 0 和 return，而不是 returning 0 ing 1 如果 num 是 1，我们可以 return num 如果 num 是 0 或 1（或num <= 1）。事实上，我们可以通过简单地用 0 和 1 的值预初始化 cache 来完全摆脱整个条件。此外，缓存可以只是 Array，因为索引只是 Integers:

的连续范围

fibonacci = -> {
  cache = [0, 1] # cache for future calculations

  -> num {
    raise ArgumentError, 'Negative numbers not allowed' if (num < 0)
    cache[num] ||= fibonacci.(num - 1) + fibonacci.(num - 2)
  }
}.()

有趣的是，如果我们用现代 ECMAScript 来写，那么关系就变得很明显了：

const fibonacci = (() => {
    const cache = [0, 1, 1]; // cache for future calculations

    return num => {
        if (num < 0) throw new Error('Negative numbers not allowed');
        return cache[num] = cache[num] || fibonacci(num - 1) + fibonacci(num - 2);
    };
})();

console.log(fibonacci(5));

在老派的 ECMAScript 中会是这样的：

var fibonacci = function () {
    var cache = [0, 1, 1]; // cache for future calculations

    return function (num) {
        if (num < 0) throw new Error('Negative numbers not allowed');
        return cache[num] = cache[num] || fibonacci(num - 1) + fibonacci(num - 2);
    };
}();

console.log(fibonacci(5));

在 Ruby 方法中创建缓存

Creating a cache in Ruby methods

javascript

ruby

memoization