python的random模块及加权随机算法的python实现方法
(编辑：jimmy 日期: 2024/11/19 浏览：3 次 )
random是用于生成随机数的，我们可以利用它随机生成数字或者选择字符串。
"color: #ff0000">方法一：
最简单的方法可以这样：
把序列按权重值扩展成: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模块及加权随机算法的python实现方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。
下一篇：python 实现红包随机生成算法的简单实例