Ruby 按一定的概率随机给出键,怎么实现好

FenRagwort · 发布于 2012年3月31日 · 最后由 quakewang 回复于 2012年4月02日 · 3046 次阅读
1452

比如有一个hash是这样的{a: 0.5, b: 0.15, c: 0.2,d: 0.15},每个值是该键的概率 现在想随机取出一个键,取出的概率等于它的值,如:a有50%的可能被取出,:c有20%的可能性。 该怎么实现好呢?

共收到 30 条回复
188
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

96

这个演算法使用相对的比例。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

188

再来个单行的 ;)

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

186

google Alias Method O(1)时间

186

@ miloyip 这篇 博客 有很详细的说明和比较。

1452

#5楼 @doitian 这个资料很好,非常感谢!

78

#2楼 @hayeah@fredwu 预分配slot那种方式比,这个即使把取 total 的过程提出来只算一遍,整体来说还是要慢太多。

96

#7楼 @ashchan @fredu 主要是省空间。 如果用 1500:1 的比例,不用创一个 1501 长的 array

78

#8楼 @hayeah 相信大部分情况下用整数100能覆盖掉。1500比1这种情况太极端了:)

1452

#1楼 @fredwu 我这是举个例子,实际的哈希可能有几千个sample,每个sample的概率可能0.001,要这样生成数组,得要巨大的数组了,不划算

1452

#2楼 @hayeah 这种方式我看NLTK里的一个功能也是如此实现的

1452

#4楼 @doitian 我看不懂你链接的网页的语言,我只会Ruby、Python、Perl,别名方法怎么样用Ruby实现呢?

186

#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下。

188

如果说是要高性能,处理大数据量的话,可以:

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


188

测试了一下目前为止的几种算法的性能(各执行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)

186

那篇口水比较多 看另一篇吧 http://www.cnblogs.com/miloyip/archive/2010/04/21/1717109.html 用的javascript

96

#14楼 @fredwu 可以使用 rand(100) 这样就不会出现float精度的问题了

186

#14楼 @fredwu CDF可以提前算,如果PDF提前按从大到小排序

values: :a :c :b :d PDF: 0.5 0.2 0.15 0.15 CDF: 0.5 0.7 0.85 1

线性搜索会快很多

186
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

188

@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)

186

#21楼 @fredwu 是整个执行100000次,还是只是产生随机变量值的部分执行100000次?贴下你的测试代码看看

188

#22楼 @doitian 整个执行。hash.to_a_sort_by这里用了很多执行时间——其实我觉得不用sort啊。

188

如果是一个很大的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)

186

#23楼 @fredwu 如果分布不平均,而且是构建1次,用n次的话,排序效果就会很明显,比如概率是1个0.91,9个0.01,91%的情况下只用比较1次

186

#24楼 @fredwu 综合测试了下, 包括benchmark和erorr。error就是实际产生的频率和原来概率分布之间的误差

186

忘了链接 https://gist.github.com/2272325 包括alias method

188

...

188

刚才把这个当作脑筋联系题发给组里的同事们玩了下。一个同事用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


162

ruby 2.0就会直接有内置sample by weight 方法了 http://bugs.ruby-lang.org/issues/4147

#27楼 @doitian alias method这个算法很cool啊,花了1个多小时才看明白...

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册