random是用于生成隨機(jī)數(shù)的，我們可以利用它隨機(jī)生成數(shù)字或者選擇字符串。
•random.seed(x)改變隨機(jī)數(shù)生成器的種子seed。
一般不必特別去設(shè)定seed，Python會自動選擇seed。
•random.random() 用于生成一個隨機(jī)浮點(diǎn)數(shù)n,0 <= n < 1
•random.uniform(a,b) 用于生成一個指定范圍內(nèi)的隨機(jī)浮點(diǎn)數(shù)，生成的隨機(jī)整數(shù)a<=n<=b;
•random.randint(a,b) 用于生成一個指定范圍內(nèi)的整數(shù)，a為下限，b為上限，生成的隨機(jī)整數(shù)a<=n<=b;若a=b，則n=a；若a>b，報錯
•random.randrange([start], stop [,step]) 從指定范圍[start,stop)內(nèi)，按指定基數(shù)遞增的集合中獲取一個隨機(jī)數(shù)，基數(shù)缺省值為1
•random.choice(sequence) 從序列中獲取一個隨機(jī)元素，參數(shù)sequence表示一個有序類型，并不是一種特定類型，泛指list，tuple，字符串等
•random.shuffle(x[,random]) 用于將一個列表中的元素打亂 （洗牌），會改變原始列表
•random.sample(sequence,k) 從指定序列中隨機(jī)獲取k個元素作為一個片段返回，不會改變原有序列
那么現(xiàn)在基礎(chǔ)知識有了，我們來實(shí)現(xiàn)一個加權(quán)隨機(jī)算法：
加權(quán)隨機(jī)算法一般應(yīng)用在以下場景：有一個集合S，里面比如有A,B,C,D這四項(xiàng)。這時我們想隨機(jī)從中抽取一項(xiàng)，但是抽取的概率不同，比如我們希望抽到A的概率是50%,抽到B和C的概率是20%,D的概率是10%。一般來說，我們可以給各項(xiàng)附一個權(quán)重，抽取的概率正比于這個權(quán)重。那么上述集合就成了：
{A:5，B:2，C:2，D:1}
方法一：
最簡單的方法可以這樣：
把序列按權(quán)重值擴(kuò)展成:lists=[A,A,A,A,A,B,B,C,C,D],然后random.choice(lists)隨機(jī)選一個就行。雖然這樣選取的時間復(fù)雜度是O(1)，但是數(shù)據(jù)量一大，空間消耗就太大了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
# coding:utf-8import randomdef weight_choice(list, weight): """ :param list: 待選取序列 :param weight: list對應(yīng)的權(quán)重序列 :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])) |
方法二：
比較常用的方法是這樣：
計(jì)算權(quán)重總和sum，然后在1到sum之間隨機(jī)選擇一個數(shù)R，之后遍歷整個集合，統(tǒng)計(jì)遍歷的項(xiàng)的權(quán)重之和，如果大于等于R，就停止遍歷，選擇遇到的項(xiàng)。
還是以上面的集合為例，sum等于10，如果隨機(jī)到1-5，則會在遍歷第一個數(shù)字的時候就退出遍歷。符合所選取的概率。
選取的時候要遍歷集合，它的時間復(fù)雜度是O（n）。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
# coding:utf-8import randomlist = ['A', 'B', 'C', 'D']def weight_choice(weight): """ :param weight: list對應(yīng)的權(quán)重序列 :return:選取的值在原列表里的索引 """ t = random.randint(0, sum(weight) - 1) for i, val in enumerate(weight): t -= val if t < 0: return iif __name__ == "__main__": print(list[weight_choice([5, 2, 2, 1])]) |
方法三：
可以先對原始序列按照權(quán)重排序。這樣遍歷的時候，概率高的項(xiàng)可以很快遇到，減少遍歷的項(xiàng)。（因?yàn)閞nd遞減的速度最快(先減去最大的數(shù))）
比較{A:5，B:2，C:2，D:1}和{B:2，C:2，A:5，D:1}
前者遍歷步數(shù)的期望是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。
這樣提高了平均選取速度，但是原序列排序也需要時間。
先搞一個權(quán)重值的前綴和序列，然后在生成一個隨機(jī)數(shù)t后，可以用二分法來從這個前綴和序列里找，那么選取的時間復(fù)雜度就是O(logn)了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
# coding:utf-8import randomimport bisectlist = ['A', 'B', 'C', 'D']def weight_choice(weight): """ :param weight: list對應(yīng)的權(quán)重序列 :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模塊及加權(quán)隨機(jī)算法的python實(shí)現(xiàn)方法就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持服務(wù)器之家。
