下面小编就为大家带来一篇 python 的 random 模块及加权随机算法的 python 实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
Python 是一种面向对象、解释型计算机程序设计语言,由 Guido van Rossum 于 1989 年底发明,第一个公开发行版发行于 1991 年。Python 语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是 C/C++)很轻松地联结在一起。
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 模块及加权随机算法的 python 实现方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持 PHPERZ。
来源: