Python利用带权重随机数解决抽奖和游戏爆装备问题
作者:mattkang 发布时间:2023-09-21 10:16:43
关于带权随机数
为了帮助理解,先来看三类随机问题的对比:
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()


猜你喜欢
- 数据库的数据量达到一定程度之后,为避免带来系统性能上的瓶颈。需要进行数据的处理,采用的手段是分区、分片、分库、分表。一、什么是mysql分表
- 本文实例讲述了Python数据结构与算法之完全树与最小堆。分享给大家供大家参考,具体如下:# 完全树 最小堆class CompleteTr
- 在正常项目开发过程中,如果MySQL版本从5.6升级到5.7版本。作为DBA在考虑数据库版本升级带来的影响时,一般会有几个注意点:sql_m
- python生成遍历暴力破解密码(这里已遍历暴力破解rar为例,只提供生成密码以及遍历密码)这个也就是提供一个思路,需求是这样的,我XX的闺
- 1、from子句组装来自不同数据源的数据; 2、where子句基于指定的条件对记录行进行筛选; 3、group&nb
- serializable 串行化(无问题)事务必须以顺序的方式执行,前一个事务提交之前后面的事务无法进行提交,最安全,但是不能并发操作,导致
- 1. 线性表简介线性表是一种线性结构,它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中,除了头尾元素,每个元素都有且只有一
- 可匹配单行,也支持换行匹配[\s\S]*?加上括号,效果更好([\s\S]*?)来源:https://blog.csdn.net/ASUKA
- python中捕获键盘操作一共有两种方法第一种方法:使用pygame中event方法使用方式如下:使用键盘右键为例if event.type
- 1. 使用默认的session, 在ini文件中:from pyramid.session import UnencryptedCookie
- 1 from multiprocessing import Pool,Queue。其中Queue在Pool中不起作用,具体原因未明。解决方案
- 我的机器不知为何,安装MySQL的时候,一到配置那一步就无休止的等待,只好结束任务,然而启动MySQL的时候出现1067错误提示
- andom.sample(list, n)即是从list中随机选取n个不同的元素# -*- coding: utf-8 -*- import
- JDBC(Java Database Connectivity),即Java数据库连接。通过JDBC编程,可以使Java应用程序和数据库进行
- 模型实例方法str():在将对象转换成字符串时会被调用。save():将模型对象保存到数据表中,ORM框架会转换成对应的insert或upd
- 时间处理是我们日常开发中最最常见的需求,例如:获取当前datetime、获取当天date、获取明天/前N天、获取当天开始和结束时
- permuteprediction = input.view(bs, self.num_anchors, self.bbox_a
- 日期的转换及计算对于日期,有时需执行不同时间单位的转换,或者接受字符串格式的日期,转换为 datetime 对象。有时需计算日期的范围,以及
- MacJi “偷懒”翻译了部分,下午冒着被 BOSS 开除的危险将其补完(原文链接)。使用 line-height 垂直居中line-hei
- 大家好,我是Peter~本文讲解的是如何利用Pandas函数求解两个DataFrame的差集、交集、并集。模拟数据模拟一份简单的数据:In