乐者为王

Do one thing, and do it well.

带权随机函数

  • 设计抽奖活动时,我们总是要控制抽奖物品出现的概率,让好的东西很难被抽到;
  • 设计游戏打怪时,我们要控制打怪时的命中概率,要控制宝物掉出的概率;
  • 网站的置顶广告,我们也要根据广告主的广告费用控制广告的出现时间;
  • 设计负载均衡算法时,我们要根据服务器的性能控制服务器被选中的可能。

深入思考这些需求,你会发现它们都有相通的概念:每次从多个候选项中随机选取其中一项,要求每个候选项的出现都有一定的概率。

假设有这样的候选项和对应概率:a:20%,b:25%,c:40%,d:15%。现在,把每个候选项的概率用一个称之为权重的正整数表示(最简单的方法是把百分符号去掉)。那么,

1
实际概率 = 候选项权重 / 权重总和 * 100%

事实上,权重的总和不一定要等于100,可以是任意大小。

算法描述

依次将各候选项的权重从原点开始放在x轴坐标上首尾相连。这样,每个候选项对应一个取值区间,在总区间范围内随机选取一个值,该值所在区间就对应了选中的项。

random-with-weight

Ruby代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def random(weight)
  # 获取所有候选项的权重总和
  total_weight = weight.inject { |r, e| r + e }

  # 随机选取一个介于0到权重总和之间的整数
  rand_value = rand(total_weight)  # [0, total_weight)

  # 扫描所有候选项,并且保留候选项权重的累积数。
  # 每当随机数小于累积数时,就停止并选出当前项。
  weight_barrier = 0
  weight.each_index do |i|
    weight_barrier += weight[i]

    break i if rand_value < weight_barrier
  end
end

该实现不能保证每个候选项都恰好按正确的比例被选中,但当次数足够多时,应该会十分接近预先设定的比例。

实际案例

要求写int[] get_weight(int[] weight)函数,返回的是权重的索引。其中weight是权重的数字数组,最终的结果是要大概保证按照给定的比例。

  • 比如weight为[1, 2, 2],那么权重比例为1:2:2,执行10次后,大概的输出是0 1 1 0 1 1 2 2 2 2;
  • 比如weight为[100, 0],那么权重比例为100:0,执行10次后,大概的输出是0 0 0 0 0 0 0 0 0 0;
  • 比如weight为[1, 1],那么权重比例为1:1,执行10次后,大概的输出是0 1 0 1 0 0 1 1 0 1。
1
2
3
4
5
6
7
8
9
10
11
12
def get_weight(weight)
  10.times.map { random(weight) }
end

weight = [1, 2, 2]
puts get_weight(weight).join(' ')

weight = [100, 0]
puts get_weight(weight).join(' ')

weight = [1, 1]
puts get_weight(weight).join(' ')

Comments