Python利用带权重随机数解决抽奖和游戏爆装备问题_python教程-查字典教程网
Python利用带权重随机数解决抽奖和游戏爆装备问题
Python利用带权重随机数解决抽奖和游戏爆装备问题
发布时间:2016-12-28 来源:查字典编辑
摘要:关于带权随机数为了帮助理解,先来看三类随机问题的对比:1.已有n条记录,从中选取m条记录,选取出来的记录前后顺序不管。实现思路:按行遍历所有...

关于带权随机数

为了帮助理解,先来看三类随机问题的对比:

1.已有n条记录,从中选取m条记录,选取出来的记录前后顺序不管。

实现思路:按行遍历所有记录,约隔n/m条取一个数据即可

2.在1类情况下,还要求选取出来的m条记录是随机排序的

实现思路: 给n条记录,分别增加一列标记,值为随机选取的1至n之间的不重复数据。

3.区别于1,2类问题, 如果记录是有权重的,如何结合权重去随机选取。 比如A的权重为10, B的权重股为5, C的权重为1, 则随机选取4个时可能应该出现AABB。

第3类问题便是本文重点了。

实现思路: 以 A:10, B:5, C:1 三条记录上随机选取4条为例,(是否以权重排序这个无所谓)

对于

A 10

B 5

C 1

首先,将第n行的数值赋为第n行加第n-1行的,递归执行,如下:

A 10

B 15

C 16

然后每次从[1,16]随机选取一个数,如果落在[1,10]之间,则选取A,如果落在(10,15]之间则选B,如果落在(16,16]之间则选取C, 图示如下,谁占的区间大(权重高),被选上的概率更大。

在抽奖和游戏爆装备中的运用

带权随机在游戏开发中重度使用,各种抽奖和爆装备等.

运营根据需要来配置各个物品出现的概率.

今天要说的这个带权随机算法思想很简单,就是"把所有物品根据其权重构成一个个区间,权重大的区间大.可以想象成一个饼图. 然后,扔骰子,看落在哪个区间,"

举个栗子,有个年终抽奖,物品是iphone/ipad/itouch.

主办方配置的权重是[('iphone', 10), ('ipad', 40), ('itouch', 50)].

用一行代码即可说明其思想,即random.choice(['iphone']*10 + ['ipad']*40 + ['itouch']*50).

下面,我们写成一个通用函数.

#coding=utf-8 import random def weighted_random(items): total = sum(w for _,w in items) n = random.uniform(0, total)#在饼图扔骰子 for x, w in items:#遍历找出骰子所在的区间 if n<w: break n -= w return x print weighted_random([('iphone', 10), ('ipad', 40), ('itouch', 50)])

上面的代码够直观,不过细心的会发现,每次都会计算total,每次都会线性遍历区间进行减操作.其实我们可以先存起来,查表就行了.利用accumulate+bisect二分查找.

物品越多,二分查找提升的性能越明显.

#coding=utf-8 class WeightRandom: def __init__(self, items): weights = [w for _,w in items] self.goods = [x for x,_ in items] self.total = sum(weights) self.acc = list(self.accumulate(weights)) def accumulate(self, weights):#累和.如accumulate([10,40,50])->[10,50,100] cur = 0 for w in weights: cur = cur+w yield cur def __call__(self): return self.goods[bisect.bisect_right(self.acc , random.uniform(0, self.total))] wr = WeightRandom([('iphone', 10), ('ipad', 40), ('itouch', 50)]) print wr()

相关阅读
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  • 最新python学习
    热门python学习
    脚本专栏子分类