Python利用帶權(quán)重隨機(jī)數(shù)解決抽獎和游戲爆裝備問題
關(guān)于帶權(quán)隨機(jī)數(shù)
為了幫助理解,先來看三類隨機(jī)問題的對比:
1.已有n條記錄,從中選取m條記錄,選取出來的記錄前后順序不管。
實(shí)現(xiàn)思路:按行遍歷所有記錄,約隔n/m條取一個數(shù)據(jù)即可
2.在1類情況下,還要求選取出來的m條記錄是隨機(jī)排序的
實(shí)現(xiàn)思路: 給n條記錄,分別增加一列標(biāo)記,值為隨機(jī)選取的1至n之間的不重復(fù)數(shù)據(jù)。
3.區(qū)別于1,2類問題, 如果記錄是有權(quán)重的,如何結(jié)合權(quán)重去隨機(jī)選取。 比如A的權(quán)重為10, B的權(quán)重股為5, C的權(quán)重為1, 則隨機(jī)選取4個時可能應(yīng)該出現(xiàn)AABB。
第3類問題便是本文重點(diǎn)了。
實(shí)現(xiàn)思路: 以 A:10, B:5, C:1 三條記錄上隨機(jī)選取4條為例,(是否以權(quán)重排序這個無所謂)
對于
A 10
B 5
C 1
首先,將第n行的數(shù)值賦為第n行加第n-1行的,遞歸執(zhí)行,如下:
A 10
B 15
C 16
然后每次從[1,16]隨機(jī)選取一個數(shù),如果落在[1,10]之間,則選取A,如果落在(10,15]之間則選B,如果落在(16,16]之間則選取C, 圖示如下,誰占的區(qū)間大(權(quán)重高),被選上的概率更大。
在抽獎和游戲爆裝備中的運(yùn)用
帶權(quán)隨機(jī)在游戲開發(fā)中重度使用,各種抽獎和爆裝備等.
運(yùn)營根據(jù)需要來配置各個物品出現(xiàn)的概率.
今天要說的這個帶權(quán)隨機(jī)算法思想很簡單,就是"把所有物品根據(jù)其權(quán)重構(gòu)成一個個區(qū)間,權(quán)重大的區(qū)間大.可以想象成一個餅圖. 然后,扔骰子,看落在哪個區(qū)間,"
舉個栗子,有個年終抽獎,物品是iphone/ipad/itouch.
主辦方配置的權(quán)重是[('iphone', 10), ('ipad', 40), ('itouch', 50)].
用一行代碼即可說明其思想,即random.choice(['iphone']*10 + ['ipad']*40 + ['itouch']*50).
下面,我們寫成一個通用函數(shù).
#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:#遍歷找出骰子所在的區(qū)間 if n<w: break n -= w return x print weighted_random([('iphone', 10), ('ipad', 40), ('itouch', 50)])
上面的代碼夠直觀,不過細(xì)心的會發(fā)現(xiàn),每次都會計(jì)算total,每次都會線性遍歷區(qū)間進(jìn)行減操作.其實(shí)我們可以先存起來,查表就行了.利用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()
相關(guān)文章
Python使用Pandas處理測試數(shù)據(jù)的方法
Pandas是一個功能極其強(qiáng)大的數(shù)據(jù)分析庫,可以高效地操作各種數(shù)據(jù)集,這篇文章主要介紹了Python自動化測試-使用Pandas來高效處理測試數(shù)據(jù),需要的朋友可以參考下2023-02-02Python保存dict字典類型數(shù)據(jù)到Mysql并自動創(chuàng)建表與列
這篇文章主要介紹了Python保存dict字典類型數(shù)據(jù)到Mysql并自動創(chuàng)建表與列,字典是另一種可變?nèi)萜髂P?,且可存儲任意類型對象,想了解更多?nèi)容的小伙伴可以和小編一起進(jìn)入下面文章學(xué)習(xí)更多內(nèi)容,希望對你有所幫助2022-02-02Django+zTree構(gòu)建組織架構(gòu)樹的方法
zTree是一個開源的依靠JQuery實(shí)現(xiàn)的多功能樹插件,具有性能優(yōu)異、配置靈活、功能強(qiáng)大的特點(diǎn),這篇文章主要介紹了Django+zTree構(gòu)建組織架構(gòu)樹,需要的朋友可以參考下2019-08-08Python 詳解通過Scrapy框架實(shí)現(xiàn)爬取CSDN全站熱榜標(biāo)題熱詞流程
Scrapy是用純Python實(shí)現(xiàn)一個為了爬取網(wǎng)站數(shù)據(jù)、提取結(jié)構(gòu)性數(shù)據(jù)而編寫的應(yīng)用框架,用途非常廣泛,框架的力量,用戶只需要定制開發(fā)幾個模塊就可以輕松的實(shí)現(xiàn)一個爬蟲,用來抓取網(wǎng)頁內(nèi)容以及各種圖片,非常之方便2021-11-11python通過ftplib登錄到ftp服務(wù)器的方法
這篇文章主要介紹了python通過ftplib登錄到ftp服務(wù)器的方法,涉及Python使用ftplib模塊的相關(guān)技巧,需要的朋友可以參考下2015-05-05Pycharm直接使用遠(yuǎn)程服務(wù)器代碼并調(diào)試的解決方法
這篇文章主要介紹了Pycharm直接使用遠(yuǎn)程服務(wù)器代碼并調(diào)試的解決方法,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-02-02