詳解python的random模組及加權隨機演算法與實作方法

random是用來產生隨機數的，我們可以利用它隨機產生數字或選擇字串。
•random.seed(x)改變隨機數字產生器的種子seed。
一般不必特別去設定seed，Python會自動選擇seed。
•random.random()    用來產生隨機浮點數n,0 <= n < 1
•random.uniform(a,b)    用來產生一個指定範圍內的隨機浮點數，產生的隨機整數a<=n<=b;
•random.randint(a,b)    用來產生一個指定範圍內的整數，a為下限，b為上限，產生的隨機整數a<=n<=b;若a=b，則n=a；若a>b，報錯
•random.randrange([start], stop [,step] )    從指定範圍[start,stop)內，依指定基數遞增的集合中取得一個隨機數，基數缺省值為1
•random.choice(sequence)    從序列中取得一個隨機元素，參數sequence表示一個有序類型，並不是一種特定類型，泛指list，tuple，字串等
•random.shuffle(x[,random])    用於將一個列表中的元素打亂（洗牌），會改變原始列表
•random.sample(sequence,k)    從指定序列中隨機獲取k個元素作為一個片段返回，不會改變原有序列
那麼現在基礎知識有了，我們來實作一個加權隨機演算法：
加權隨機演算法一般應用在以下場景：有一個集合S，裡面例如有A,B,C,D這四項。這時我們想隨機從中抽取一項，但是抽取的機率不同，例如我們希望抽到A的機率是50%,抽到B和C的機率是20%,D的機率是10%。一般來說，我們可以給各項附一個權重，抽取的機率正比於這個權重。那麼上述集合就成了：
{A:5，B:2，C:2，D:1}
#方法一：
#最簡單的方法可以這樣：
把序列依權重值擴展成:lists=[A,A,A,A,A,B,B,C,C,D],然後random.choice(lists)隨機選一個就行。雖然這樣選取的時間複雜度是O(1)，但是資料量一大，空間消耗量太大了。

# coding:utf-8
import random
def weight_choice(list, weight):
  """
  :param list: 待选取序列
  :param weight: list对应的权重序列
  :return:选取的值
  """
  new_list = []
  for i, val in enumerate(list):
    new_list.extend(val * weight[i])
  return random.choice(new_list)
if name == "main":
  print(weight_choice(['A', 'B', 'C', 'D'], [5, 2, 2, 1]))

方法二：
比較常用的方法是這樣：
計算權重總和sum，然後在1到sum之間隨機選擇一個數字R，之後遍歷整個集合，統計遍歷的項的權重總和，如果大於等於R，就停止遍歷，選擇遇到的項。
還是以上面的集合為例，sum等於10，如果隨機到1-5，則會在遍歷第一個數字的時候就退出遍歷。符合所選的機率。
選取的時候要遍歷集合，它的時間複雜度是O（n）。

# coding:utf-8
import random
list = ['A', 'B', 'C', 'D']
def weight_choice(weight):
  """
  :param weight: list对应的权重序列
  :return:选取的值在原列表里的索引
  """
  t = random.randint(0, sum(weight) - 1)
  for i, val in enumerate(weight):
    t -= val
    if t < 0:
      return i
if name == "main":
  print(list[weight_choice([5, 2, 2, 1])])

方法三：
可以先將原始序列依照權重排序。這樣遍歷的時候，機率高的項可以很快遇到，減少遍歷的項。 （因為rnd遞減的速度最快(先減去最大的數)）
比較{A:5，B:2，C:2，D:1}和{B:2，C:2，A: 5，D:1}
前者遍歷步數的期望是5/10*1+2/10*2+2/10*3+1/10*4=19/10而後者是2/10* 1+2/10*2+5/10*3+1/10*4=25/10。
這樣提高了平均選取速度，但是原始序列排序也需要時間。
先搞一個權重值的前綴和序列，然後在產生一個隨機數t後，可以用二分法來從這個前綴和序列裡找，那麼選取的時間複雜度就是O(logn)了。

# coding:utf-8
import random
import bisect
list = ['A', 'B', 'C', 'D']
def weight_choice(weight):
  """
  :param weight: list对应的权重序列
  :return:选取的值在原列表里的索引
  """
  weight_sum = []
  sum = 0
  for a in weight:
    sum += a
    weight_sum.append(sum)
  t = random.randint(0, sum - 1)
  return bisect.bisect_right(weight_sum, t)
if name == "main":
  print(list[weight_choice([5, 2, 2, 1])])

以上是詳解python的random模組及加權隨機演算法與實作方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！