避免重複按鍵以得到一個隨機哈希鍵

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

不是。哈希沒有索引，因此您可以將它們轉換爲數組並隨機選擇一個索引，或者將您的哈希枚舉爲隨機數。你應該基準哪種方法最快，但我懷疑你可以避免創建一個新的對象。

如果你不關心你的對象，你可以將它的按鍵移動一個隨機次數，但是然後你可以爲數組返回值。

Answer 3

......怎麼

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

你可以做result = h[k.sample]倍，往往你喜歡，也不會再生k陣列。但是，您應該隨時h更改k重新生成。

附錄：我正在拋出幾個建議的解決方案的基準代碼。請享用。

#!/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

除非你有一個巨大的散列，這是一個毫無意義的問題。 Ruby不是效率的強者，如果你擔心這一點，你應該使用C（++）。

Answer 5

如果您需要製作很多隨機樣本，並且需要高效，那麼Ruby Hash可能不是您的問題的正確數據結構或存儲。甚至一個維護Hash和Array屬性的包裝類也可以很好地工作 - 例如，如果每次寫散列需要讀取20個隨機樣本。

不管你是否適合你，不僅取決於閱讀和寫作的比例，還與你的問題數據的邏輯結構有關（與你在解決方案中如何選擇代表它的方式相反）。

但是，在您重新考慮您的問題之前，您需要對受影響的代碼具有更高性能的實際需求。散列值需要相當大才能獲得明顯的代價來獲取密鑰。當我的筆記本電腦上有1百萬條記錄時，h.keys需要大約250ms。

Answer 6

是這樣的：

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

Answer 7

我想先重申大多數人都在說什麼：這可能並不重要。

其次，我會指出，這肯定好像你想要一個隨機值，而不是一個隨機關鍵。也許這只是因爲你的代碼片段沒有顯示你真正在做什麼。

如果您非常頻繁需要一個隨機值，並且極少更新哈希，我建議緩存哈希隨時修改的值，然後採取從緩存中的隨機值。要做到這一點的方法之一可能是這樣的：

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" 

當然，如果你真的想要一個隨機密鑰，而不是價值，確切的概念同樣適用。無論哪種方式，這可以避免每次獲取值時重新創建數組;它只在必要時創建它。