Python利用带权重随机数解决抽奖和游戏爆装备问题

yipeiwu_com6年前Python基础

关于带权随机数
为了帮助理解,先来看三类随机问题的对比:
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, 图示如下,谁占的区间大(权重高),被选上的概率更大。

2016616155350152.jpg (596×75)

在抽奖和游戏爆装备中的运用
带权随机在游戏开发中重度使用,各种抽奖和爆装备等.
运营根据需要来配置各个物品出现的概率.
今天要说的这个带权随机算法思想很简单,就是"把所有物品根据其权重构成一个个区间,权重大的区间大.可以想象成一个饼图.  然后,扔骰子,看落在哪个区间,"
举个栗子,有个年终抽奖,物品是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利用微信公众号实现报警功能

微信公众号共有三种,服务号、订阅号、企业号。它们在获取AccessToken上各有不同。 其中订阅号比较坑,它的AccessToken是需定时刷新,重复获取将导致上次获取的AccessT...

浅谈python中set使用

浅谈python中set使用 In [2]: a = set() # 常用操作1 In [3]: a Out[3]: set() In [4]: type(a) O...

python读取excel表格生成erlang数据

为了将excel数据自动转换成所需要的erlang数据,听同事说使用python会很方便简单,就自学了两天python,写了一个比较粗糙的python脚本,不过能用,有什么优化的地方请指...

使用python实现希尔、计数、基数基础排序的代码

使用python实现希尔、计数、基数基础排序的代码

希尔排序 希尔排序是一个叫希尔的数学家提出的一种优化版本的插入排序。 首先取一个整数d1=n//2,将元素分为d1个组,每组相邻元素之间的距离为d1,在各组内进行直接插入排序。 取第二个...

在Python中使用poplib模块收取邮件的教程

在Python中使用poplib模块收取邮件的教程

SMTP用于发送邮件,如果要收取邮件呢? 收取邮件就是编写一个MUA作为客户端,从MDA把邮件获取到用户的电脑或者手机上。收取邮件最常用的协议是POP协议,目前版本号是3,俗称POP3。...