Python random模块详解与加权随机算法实现

random模块主要用于生成随机数，可用于随机生成数值或从字符串中随机选取元素。

•random.seed(x)：用于设定随机数生成器的种子seed。

通常无需手动设置seed，Python会自动处理种子选择。

•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实现方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持本站。