Ruby 按一定的概率随机给出键，怎么实现好
比如有一个 hash 是这样的{a: 0.5, b: 0.15, c: 0.2,d: 0.15}，每个值是该键的概率 现在想随机取出一个键，取出的概率等于它的值，如:a 有 50% 的可能被取出，:c 有 20% 的可能性。 该怎么实现好呢？
hash = { :a => 0.5, :b => 0.15, :c => 0.2, :d => 0.15 }
keys = []
hash.each do |k, v|
(v*100).to_i.times { keys << k }
end
p keys.sample
这个演算法使用相对的比例。O(N) 计算，O(1) 空间
pairs = {a: 1, b: 2}
def freq(pairs)
total = pairs.values.inject(0) { |sum,n| sum + n }
# pick a number (1..total) inclusive
target = rand(total)+1
pairs.each do |key,weight|
if target <= weight
return key
else
target -= weight
end
end
end
再来个单行的；）
hash = { :a => 0.5, :b => 0.15, :c => 0.2, :d => 0.15 }
p hash.to_a.map { |el| Array.new(el[1]*100, el[0]) }.flatten.sample
#11 楼 @FenRagwort 2 分搜索的比较好实现，只要算出 accumulated prop (cumulative distribution function CDF) 就行了，像你例子就是算出平行数组
[:a, :b, :c, :d] [0.5, 0.65, 0.85, 1]
sample 个(0,1]然后在第二数组里二分查找，找出 index 从第一个数组取值，accumulate 就是到当前位置为止所有概率之和
alias method 的构造有些小复杂，以前写过个分析的文章 不过 ruby 实现搜了下没找到。其实用二分足够了吧，几千也就 10~14 下。
如果说是要高性能，处理大数据量的话，可以：
hash = { :a => 0.5, :b => 0.15, :c => 0.2, :d => 0.15 }
marker = rand
p hash.inject{ |s, n| s[1] > marker ? s : [n[0], s[1]+n[1]] }[0]
这个算法有个小小的弊病——严格意义上来算，由于 float 的精确度问题，结果是会有偏差的，比如：
0.5+0.15+0.2
# => 0.8500000000000001
测试了一下目前为止的几种算法的性能（各执行 100000 次）。算法包括我的三个，加上@hayeah的一个。
user system total real
fredwu's traditional 1.610000 0.010000 1.620000 ( 1.622086)
fredwu's one liner 1.920000 0.020000 1.940000 ( 1.946811)
fredwu's enumerator 0.180000 0.000000 0.180000 ( 0.180438)
hayeah's 0.480000 0.000000 0.480000 ( 0.480785)
那篇口水比较多 看另一篇吧 http://www.cnblogs.com/miloyip/archive/2010/04/21/1717109.html 用的 javascript
hash = { :a => 0.5, :b => 0.15, :c => 0.2, :d => 0.15 }
cdf = hash.to_a.sort_by {|e| -e.last}
cumulative_probability = 0
cdf.each { |e| cumulative_probability = e[1] = e[1] + cumulative_probability }
cdf.last[1] = 1 # fix float error
marker = rand
result = cdf.find {|e| marker < e.last }
result.first
@doitian 执行速度还是没有之前两个快哦。；）
user system total real
fredwu's traditional 1.790000 0.010000 1.800000 ( 1.832200)
fredwu's one liner 1.840000 0.020000 1.860000 ( 1.864844)
fredwu's enumerator 0.180000 0.000000 0.180000 ( 0.182008)
hayeah's 0.480000 0.000000 0.480000 ( 0.478611)
doitian's 0.780000 0.000000 0.780000 ( 0.785653)
如果是一个很大的 hash，比如：
hash_elements = 10000
big_hash = {}
hash_elements.times { |n| big_hash[n] = 1.0/hash_elements }
Benchmark 只执行一次的话——
user system total real
fredwu's traditional 0.010000 0.000000 0.010000 ( 0.010952)
fredwu's one liner 0.010000 0.000000 0.010000 ( 0.011436)
fredwu's enumerator 0.000000 0.000000 0.000000 ( 0.005906)
hayeah's 0.010000 0.000000 0.010000 ( 0.007418)
doitian's 0.010000 0.000000 0.010000 ( 0.010415)
刚才把这个当作脑筋联系题发给组里的同事们玩了下。一个同事用 Python 写了个——
from random import randint
my_dict = { 'a': 0.5, 'b': 0.15, 'c': 0.2, 'd': 0.15 }
rand_val = randint(1, 100)
start_range = 0
for element in sorted(my_dict.keys()):
current_val = (my_dict[element] * 100) + start_range
if start_range < rand_val <= current_val:
print element
start_range = current_val
ruby 2.0 就会直接有内置 sample by weight 方法了 http://bugs.ruby-lang.org/issues/4147