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， 圖示如下，誰佔的區間大（權重高），被選上的機率較大。

##在抽獎和遊戲爆裝備中的運用

帶權隨機在遊戲開發中重度使用,各種抽獎和爆裝備等.

運營根據需要來配置各個物品出現的機率.
今天要說的這個帶權隨機演算法思想很簡單,就是"把所有物品根據其權重構成一個個區間,權重大的區間大.可以想像成一個餅圖.然後,丟骰子,看落在哪個區間,"

舉個栗子,有個年終抽獎,物品是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([(&#39;iphone&#39;, 10), (&#39;ipad&#39;, 40), (&#39;itouch&#39;, 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利用帶權重隨機數解決抽獎和遊戲爆裝備相關文章請關注PHP中文網！

##