ruby - Ruby 中有内置的惰性哈希吗？

Question

我需要用各种值填充哈希。一些值经常被访问，而另一些则很少。

问题是，我正在使用一些计算来获取值，并且使用多个键填充哈希变得非常慢。

在我的情况下，使用某种缓存不是一种选择。

我想知道如何使哈希仅在第一次访问键时而不是在添加键时计算值？

这样，很少使用的值不会减慢填充过程。

我正在寻找“有点异步”或延迟访问的东西。

Answer 1

有许多不同的方法可以解决这个问题。我建议使用您定义的类的实例而不是哈希。例如，而不是...

# Example of slow code using regular Hash.
h = Hash.new
h[:foo] = some_long_computation
h[:bar] = another_long_computation
# Access value.
puts h[:foo]

...创建自己的类并定义方法，就像这样...

class Config
  def foo
    some_long_computation
  end

  def bar
    another_long_computation
  end
end

config = Config.new
puts config.foo

如果您想要一种简单的方法来缓存长计算，或者它绝对必须是 Hash，而不是您自己的类，您现在可以用 Hash 包装 Config 实例。

config = Config.new
h = Hash.new {|h,k| h[k] = config.send(k) }
# Access foo.
puts h[:foo]
puts h[:foo]  # Not computed again. Cached from previous access.

上述示例的一个问题是h.keys不包括在内:bar，因为您尚未访问它。因此，例如，您不能遍历其中的所有键或条目，h因为它们在实际访问之前不存在。另一个潜在的问题是您的键必须是有效的 Ruby 标识符，因此在Config.

如果这对你很重要，有不同的方法来处理它。一种方法是使用thunk填充散列并在访问时强制使用 thunk。

class HashWithThunkValues < Hash
  def [](key)
    val = super
    if val.respond_to?(:call)
      # Force the thunk to get actual value.
      val = val.call
      # Cache the actual value so we never run long computation again.
      self[key] = val
    end

    val
  end
end

h = HashWithThunkValues.new
# Populate hash.
h[:foo] = ->{ some_long_computation }
h[:bar] = ->{ another_long_computation }
h["invalid Ruby name"] = ->{ a_third_computation }  # Some key that's an invalid ruby identifier.
# Access hash.
puts h[:foo]
puts h[:foo]  # Not computed again. Cached from previous access.
puts h.keys  #=> [:foo, :bar, "invalid Ruby name"]

最后一个示例的一个警告是，如果您的值是可调用的，它将不起作用，因为它无法区分需要强制执行的 thunk 和值之间的区别。

同样，有办法处理这个问题。一种方法是存储一个标志，该标志标记一个值是否已被评估。但这将需要每个条目的额外内存。更好的方法是定义一个新类来标记哈希值是未评估的 thunk。

class Unevaluated < Proc
end

class HashWithThunkValues < Hash
  def [](key)
    val = super

    # Only call if it's unevaluated.
    if val.is_a?(Unevaluated)
      # Force the thunk to get actual value.
      val = val.call
      # Cache the actual value so we never run long computation again.
      self[key] = val
    end

    val
  end
end

# Now you must populate like so.
h = HashWithThunkValues.new
h[:foo] = Unevaluated.new { some_long_computation }
h[:bar] = Unevaluated.new { another_long_computation }
h["invalid Ruby name"] = Unevaluated.new { a_third_computation }  # Some key that's an invalid ruby identifier.
h[:some_proc] = Unevaluated.new { Proc.new {|x| x + 2 } }

这样做的缺点是现在您必须记住Unevaluted.new在填充哈希时使用。如果您希望所有值都是惰性的，您也可以覆盖[]=。我认为它实际上不会节省很多打字，因为您仍然需要使用Proc.new, proc, lambda, 或->{}首先创建块。但这可能是值得的。如果你这样做了，它可能看起来像这样。

class HashWithThunkValues < Hash
  def []=(key, val)
    super(key, val.respond_to?(:call) ? Unevaluated.new(&val) : val)
  end
end

所以这里是完整的代码。

class HashWithThunkValues < Hash

  # This can be scoped inside now since it's not used publicly.
  class Unevaluated < Proc
  end

  def [](key)
    val = super

    # Only call if it's unevaluated.
    if val.is_a?(Unevaluated)
      # Force the thunk to get actual value.
      val = val.call
      # Cache the actual value so we never run long computation again.
      self[key] = val
    end

    val
  end

  def []=(key, val)
    super(key, val.respond_to?(:call) ? Unevaluated.new(&val) : val)
  end

end

h = HashWithThunkValues.new
# Populate.
h[:foo] = ->{ some_long_computation }
h[:bar] = ->{ another_long_computation }
h["invalid Ruby name"] = ->{ a_third_computation }  # Some key that's an invalid ruby identifier.
h[:some_proc] = ->{ Proc.new {|x| x + 2 } }

Answer 2

你可以使用这个：

class LazyHash < Hash

  def [] key
    (_ = (@self||{})[key]) ? 
      ((self[key] = _.is_a?(Proc) ? _.call : _); @self.delete(key)) :
      super
  end

  def lazy_update key, &proc
    (@self ||= {})[key] = proc
    self[key] = proc
  end

end

你的惰性散列会表现得和正常一样Hash，因为它实际上是一个真实的Hash.

在此处查看现场演示

*** 更新 - 回答嵌套 procs 问题 ***

是的，它会工作，但它很麻烦。

请参阅更新的答案。

使用lazy_update而不是[]= 将“惰性”值添加到您的哈希中。

Answer 3

您可以使用以下内容定义自己的索引器：

class MyHash
  def initialize
    @cache = {}
  end

  def [](key)
    @cache[key] || (@cache[key] = compute(key))
  end

  def []=(key, value)
    @cache[key] = value
  end

  def compute(key)
    @cache[key] = 1
  end
end

并按如下方式使用它：

1.9.3p286 :014 > hash = MyHash.new
 => #<MyHash:0x007fa0dd03a158 @cache={}> 

1.9.3p286 :019 > hash["test"]
 => 1 

1.9.3p286 :020 > hash
 => #<MyHash:0x007fa0dd03a158 @cache={"test"=>1}> 

Answer 4

这不是对您问题主体的严格回答，但Enumerable::Lazy 肯定会成为 Ruby 2.0 的一部分。这将让您对迭代器组合进行惰性评估：

lazy = [1, 2, 3].lazy.select(&:odd?)
# => #<Enumerable::Lazy: #<Enumerator::Generator:0x007fdf0b864c40>:each>
lazy.to_a 
# => [40, 50]