亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python實現(xiàn)一個帶權(quán)無回置隨機(jī)抽選函數(shù)的方法

系統(tǒng) 1587 0

需求

有一個抽獎應(yīng)用,從所有參與的用戶抽出K位中獎用戶(K=獎品數(shù)量),且要根據(jù)每位用戶擁有的抽獎碼數(shù)量作為權(quán)重。

如假設(shè)有三個用戶及他們的權(quán)重是: A(1), B(1), C(2)。希望抽到A的概率為25%,抽到B的概率為25%, 抽到C的概率為50%。

分析

比較直觀的做法是把兩個C放到列表中抽選,如[A, B, C, C], 使用Python內(nèi)置的函數(shù)random.choice[A, B, C, C], 這樣C抽到的概率即為50%。

這個辦法的問題是權(quán)重比較大的時候,浪費(fèi)內(nèi)存空間。

更一般的方法是,將所有權(quán)重加和4,然后從[0, 4)區(qū)間里隨機(jī)挑選一個值,將A, B, C占用不同大小的區(qū)間。[0,1)是A, [1,2)是B, [2,4)是C。

使用Python的函數(shù)random.ranint(0, 3)或者int(random.random()*4)均可產(chǎn)生0-3的隨機(jī)整數(shù)R。判斷R在哪個區(qū)間即選擇哪個用戶。

接下來是尋找隨機(jī)數(shù)在哪個區(qū)間的方法,

一種方法是按順序遍歷列表并保存已遍歷的元素權(quán)重綜合S,一旦S大于R,就返回當(dāng)前元素。

            
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


          

不過這種方法的復(fù)雜度是O(N), 因為要遍歷所有的users。

可以想到另外一種方法,先按順序把累積加的權(quán)重排成列表,然后對它使用二分法搜索,二分法復(fù)雜度降到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內(nèi)置庫random的choices函數(shù)(3.6版本后有)即是如此實現(xiàn),random.choices函數(shù)簽名為 random.choices(population, weights=None, *, cum_weights=None, k=1) population是待選列表, weights是各自的權(quán)重,cum_weights是可選的計算好的累加權(quán)重(兩者選一),k是抽選數(shù)量(有回置抽選)。 源碼如下:

            
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)]

          

更進(jìn)一步

因為Python內(nèi)置的random.choices是有回置抽選,無回置抽選函數(shù)是random.sample,但該函數(shù)不能根據(jù)權(quán)重抽選(random.sample(population, k))。

原生的random.sample可以抽選個多個元素但不影響原有的列表,其使用了兩種算法實現(xiàn), 保證了各種情況均有良好的性能。 (源碼地址:random.sample)

第一種是部分shuffle,得到K個元素就返回。 時間復(fù)雜度是O(N),不過需要復(fù)制原有的序列,增加內(nèi)存使用。

            
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

          

而第二種是設(shè)置一個已選擇的set,多次隨機(jī)抽選,如果抽中的元素在set內(nèi),就重新再抽,無需復(fù)制新的序列。 當(dāng)k相對n較小時,random.sample使用該算法,重復(fù)選擇元素的概率較小。

            
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

          

抽獎應(yīng)用需要的是帶權(quán)無回置抽選算法,結(jié)合random.choices和random.sample的實現(xiàn)寫一個函數(shù)weighted_sample。

一般抽獎的人數(shù)都比獎品數(shù)量大得多,可選用random.sample的第二種方法作為無回置抽選,當(dāng)然可以繼續(xù)優(yōu)化。

代碼如下:

            
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: # 預(yù)防一些錯誤的權(quán)重
    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


          

以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 99久久999久久久综合精品涩 | 国产第一区二区三区在线观看 | 色偷偷亚洲天堂 | 日韩欧美亚洲综合一区二区 | 激情欧美一区二区三区中文字幕 | 国产精品嫩草影院奶水 | 性欧美高清come | h视频国产 | 99久久国产综合精品女不卡 | 欧美在线一级毛片观看 | 免看一级一片一在线看 | 午夜精品福利在线 | 久久久精品 | 天天久久狠狠伊人第一麻豆 | 久久免费资源福利资源站 | 92精品国产成人观看免费 | 久久欧美精品 | 亚洲国产激情在线一区 | 欧美国产伦久久久久 | 91久久精品国产免费一区 | 国产 高清 在线 | 欧美性网 | 麻豆国产原创最新在线视频 | 国产精品亚洲片在线观看麻豆 | 欧美一区二区三区在观看 | 国产高清精品在线 | 国产精品久久久久久久成人午夜 | 激情在线播放免费视频高清 | 国产福利第一视频 | 久久亚洲影院 | 免费中文字幕在线观看 | 真实偷拍激情啪啪对白 | 香蕉久久综合精品首页 | 四虎成人在线 | 亚洲成人免费在线视频 | 久久99精品视香蕉蕉 | 久久久免费观成人影院 | 天天操综合网 | 日本视频中文字幕 | 中国特级黄一级真人毛片 | 日韩欧美成人免费中文字幕 |