ruby - 避免密钥重复以获得随机散列密钥

Question

我需要随机选择一个哈希条目，所以我这样做

h = {1 => 'one', 2 => 'two', 3 => 'three'}
k = h.keys.sample
result = h[k]

由于h.keys创建了一个新数组，我不喜欢它。有没有办法避免每次都创建一个新数组？

Answer 1

这不会生成另一个数组。平均而言， hash_random_value将在给定哈希的中途迭代以产生随机值。

def hash_random_value(h)
  i = rand(h.length)
  h.each_with_index do |(_, v), i2|
    return v if i == i2
  end
end

h = {1 => 'one', 2 => 'two', 3 => 'three'}
hash_random_value(h)

话虽如此，只有在确定需要这样做时才应该优化。您可以知道的唯一方法是分析您的代码，否则您很可能会进行过早的优化。即使您的代码复杂化并增加引入错误的机会——有时甚至会降低您的程序的性能。您的原始解决方案比我的更容易理解，而且很明显它是正确的。

Answer 2

我想首先重申大多数人所说的话：这可能无关紧要。

其次，我会指出，您似乎确实想要一个随机值，而不是随机键。也许这只是因为您的示例代码片段没有显示您真正在做什么。

如果您经常需要一个随机值，并且很少更新哈希，我建议您在修改哈希时缓存这些值，然后从缓存中获取一个随机值。一种方法可能是这样的：

class RandomValueHash < Hash
  def []=(k, v)
    super(k, v)
    @values = self.values
  end

  def sample_value
    @values ||= self.values
    @values.sample
  end
end

rvh = RandomValueHash[{1 => 'one', 2 => 'two', 3 => 'three'}]
rvh.sample_value
# => "one"
rvh[4] = 'four'
rvh[5] = 'five'
rvh.sample_value
# => "four"

当然，如果你真的想要一个随机键而不是值，那么同样的概念也适用。无论哪种方式，这都避免了每次获得值时都重新创建数组；它只在必要时创建它。

Answer 3

怎么样...

h = {1 => 'one', 2 => 'two', 3 => 'three'}
k = h.keys
...
result = h[k.sample]

您可以随心所欲地执行result = h[k.sample]时间，并且不会重新生成k数组。但是，您应该重新生成k任何时间h更改。

附录：我正在为几个提议的解决方案提供基准代码。享受。

#!/usr/bin/env ruby
require 'benchmark'

NUM_ITERATIONS = 1_000_000

def hash_random_value(h)
  i = rand(h.length)
  h.each_with_index do |(_, v), i2|
    return v if i == i2
  end
end

class RandomValueHash < Hash
  def []=(k, v)
    super(k, v)
    @values = self.values
  end

  def sample_value
    @values ||= self.values
    @values.sample
  end
end

Benchmark.bmbm do |b|
  h = {1 => 'one', 2 => 'two', 3 => 'three'}

  b.report("original proposal") do
    NUM_ITERATIONS.times {k = h.keys.sample; result = h[k]}
  end

  b.report("hash_random_value") do
    NUM_ITERATIONS.times {result = hash_random_value(h)}
  end

  b.report("manual keyset") do
    k = h.keys
    NUM_ITERATIONS.times {result = h[k.sample]}
  end

  rvh = RandomValueHash[{1 => 'one', 2 => 'two', 3 => 'three'}]

  b.report("RandomValueHash") do
    NUM_ITERATIONS.times {result = rvh.sample_value}
  end
end

Answer 4

如果您需要大量随机样本，并且需要它高效，那么Hash对于您的问题，Ruby 可能不是正确的数据结构或存储。Hash即使是一起维护和属性的包装类也Array可能运行良好 - 例如，如果每次写入哈希都需要读取 20 个随机样本。

这是否适合您不仅取决于读写的比率，还与问题数据的逻辑结构有关（与您选择在解决方案中表示它的方式相反）。

但在您开始重新考虑您的问题之前，您需要对受影响代码的更高性能有实际需求。散列需要非常大，才能有显着的成本来获取其密钥。h.keys当哈希在我的笔记本电脑上有 100 万个条目时，大约需要 250 毫秒。

Answer 5

并不真地。散列没有索引，因此您可以将它们转换为数组并选择一个随机索引，或者您可以随机数次枚举散列。您应该对哪种方法最快进行基准测试，但我怀疑您是否可以避免创建新对象。

如果你不关心你的对象，你可以将它的键随机移动几次，但你会为返回值创建数组。

Answer 6

除非你有一个巨大的哈希，否则这是一个毫无意义的问题。Ruby 不是效率强国，如果您对此担心，您应该使用 C(++)。

Answer 7

像这样的东西：

h.each_with_index.reduce(nil) {|m, ((_, v), i)|
  rand(i + 1) == 0 ? v : m
}