溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
需求
有一個抽獎應用，從所有參與的用戶抽出K位中獎用戶(K=獎品數量)，且要根據每位用戶擁有的抽獎碼數量作為權重。
如假設有三個用戶及他們的權重是: A(1), B(1), C(2)。希望抽到A的概率為25%，抽到B的概率為25%, 抽到C的概率為50%。
分析
比較直觀的做法是把兩個C放到列表中抽選，如[A, B, C, C]， 使用Python內置的函數random.choice[A, B, C, C], 這樣C抽到的概率即為50%。
這個辦法的問題是權重比較大的時候，浪費內存空間。
更一般的方法是，將所有權重加和4，然后從[0, 4)區間里隨機挑選一個值，將A, B, C占用不同大小的區間。[0,1)是A, [1,2)是B, [2,4)是C。
使用Python的函數random.ranint(0, 3)或者int(random.random()*4)均可產生0-3的隨機整數R。判斷R在哪個區間即選擇哪個用戶。
接下來是尋找隨機數在哪個區間的方法，
一種方法是按順序遍歷列表并保存已遍歷的元素權重綜合S，一旦S大于R，就返回當前元素。
from operator import itemgetter
users = [('A', 1), ('B', 1), ('C', 2)]
total = sum(map(itemgetter(1), users))
rnd = int(random.random()*total) # 0~3
s = 0
for u, w in users:
s += w
if s > rnd:
return u
不過這種方法的復雜度是O(N)， 因為要遍歷所有的users。
可以想到另外一種方法，先按順序把累積加的權重排成列表，然后對它使用二分法搜索，二分法復雜度降到O(logN)(除去其他的處理)
users = [('A', 1), ('B', 1), ('C', 2)]
cum_weights = list(itertools.accumulate(map(itemgetter(1), users))) # [1, 2, 4]
total = cum_weights[-1]
rnd = int(random.random()*total) # 0~3
hi = len(cum_weights) - 1
index = bisect.bisect(cum_weights, rnd, 0, hi)
return users(index)[0]
Python內置庫random的choices函數(3.6版本后有)即是如此實現，random.choices函數簽名為 random.choices(population, weights=None, *, cum_weights=None, k=1) population是待選列表， weights是各自的權重，cum_weights是可選的計算好的累加權重（兩者選一），k是抽選數量（有回置抽選）。 源碼如下:
def choices(self, population, weights=None, *, cum_weights=None, k=1):
"""Return a k sized list of population elements chosen with replacement.
If the relative weights or cumulative weights are not specified,
the selections are made with equal probability.
"""
random = self.random
if cum_weights is None:
if weights is None:
_int = int
total = len(population)
return [population[_int(random() * total)] for i in range(k)]
cum_weights = list(_itertools.accumulate(weights))
elif weights is not None:
raise TypeError('Cannot specify both weights and cumulative weights')
if len(cum_weights) != len(population):
raise ValueError('The number of weights does not match the population')
bisect = _bisect.bisect
total = cum_weights[-1]
hi = len(cum_weights) - 1
return [population[bisect(cum_weights, random() * total, 0, hi)]
for i in range(k)]
更進一步
因為Python內置的random.choices是有回置抽選，無回置抽選函數是random.sample，但該函數不能根據權重抽選（random.sample(population, k)）。
原生的random.sample可以抽選個多個元素但不影響原有的列表，其使用了兩種算法實現, 保證了各種情況均有良好的性能。 (源碼地址：random.sample)
第一種是部分shuffle，得到K個元素就返回。 時間復雜度是O(N)，不過需要復制原有的序列，增加內存使用。
result = [None] * k n = len(population) pool = list(population) # 不改變原有的序列 for i in range(k): j = int(random.random()*(n-i)) result[k] = pool[j] pool[j] = pool[n-i-1] # 已選中的元素移走，后面未選中元素填上 return result
而第二種是設置一個已選擇的set，多次隨機抽選，如果抽中的元素在set內，就重新再抽，無需復制新的序列。 當k相對n較小時，random.sample使用該算法，重復選擇元素的概率較小。
selected = set()
selected_add = selected.add # 加速方法訪問
for i in range(k):
j = int(random.random()*n)
while j in selected:
j = int(random.random()*n)
selected_add(j)
result[j] = population[j]
return result
抽獎應用需要的是帶權無回置抽選算法，結合random.choices和random.sample的實現寫一個函數weighted_sample。
一般抽獎的人數都比獎品數量大得多，可選用random.sample的第二種方法作為無回置抽選，當然可以繼續優化。
代碼如下：
def weighted_sample(population, weights, k=1):
"""Like random.sample, but add weights.
"""
n = len(population)
if n == 0:
return []
if not 0 <= k <= n:
raise ValueError("Sample larger than population or is negative")
if len(weights) != n:
raise ValueError('The number of weights does not match the population')
cum_weights = list(itertools.accumulate(weights))
total = cum_weights[-1]
if total <= 0: # 預防一些錯誤的權重
return random.sample(population, k=k)
hi = len(cum_weights) - 1
selected = set()
_bisect = bisect.bisect
_random = random.random
selected_add = selected.add
result = [None] * k
for i in range(k):
j = _bisect(cum_weights, _random()*total, 0, hi)
while j in selected:
j = _bisect(cum_weights, _random()*total, 0, hi)
selected_add(j)
result[i] = population[j]
return result
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
