Detailed explanation of python's random module, weighted random algorithm and implementation method

random is used to generate random numbers. We can use it to randomly generate numbers or select strings.
•random.seed(x) changes the seed of the random number generator.
Generally there is no need to set the seed specifically, Python will automatically select the seed.
•random.random() Used to generate a random floating point number n,0 <= n < 1
•random.uniform(a,b) Used to generate a random floating point number within a specified range, Generated random integer a<=n<=b;
•random.randint(a,b) is used to generate an integer within a specified range, a is the lower limit, b is the upper limit, the generated Random integer a<=n<=b; if a=b, then n=a; if a>b, error
•random.randrange([start], stop [,step] ) Obtain a random number from the set in the specified range [start, stop), increasing by the specified base. The default value of the base is 1
•random.choice(sequence) Obtain a random element from the sequence, represented by the parameter sequence An ordered type, not a specific type, generally refers to list, tuple, string, etc.
•random.shuffle(x[,random]) is used to Disturbing (shuffling) the elements in a list will change the original list
•random.sample(sequence,k) Randomly obtain k elements from the specified sequence and return them as a fragment, without changing the original sequence
Now that we have the basic knowledge, let’s implement a weighted random algorithm:
The weighted random algorithm is generally used in the following scenarios: There is a set S, which contains four items, such as A, B, C, and D. At this time, we want to randomly draw an item from it, but the probability of drawing is different. For example, we hope that the probability of drawing A is 50%, the probability of drawing B and C is 20%, and the probability of drawing D is 10%. Generally speaking, we can attach a weight to each item, and the probability of extraction is proportional to this weight. Then the above set becomes:
{A:5, B:2, C:2, D:1}
Method 1:
The simplest method can be like this:
Expand the sequence according to the weight value into: lists=[A,A,A,A,A,B,B,C,C,D], and then randomly select one with random.choice(lists). Although the time complexity of this selection is O(1), the amount of data is large and the space consumption is too large.

# 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]))

Method 2:
The more commonly used method is this:
Calculate the sum of weights, and then randomly select a number R between 1 and sum. Then traverse the entire collection and count the sum of the weights of the traversed items. If it is greater than or equal to R, stop traversing and select the items encountered.
Still taking the above set as an example, sum is equal to 10. If the random number is 1-5, the traversal will exit when the first number is traversed. consistent with the selected probability.
It is necessary to traverse the collection when selecting, and its time complexity is 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])])

Method 3:
You can first sort the original sequence according to weight. When traversing in this way, items with high probability can be encountered quickly, reducing the number of items to be traversed. (Because rnd decrements the fastest (subtract the largest number first))
Compare {A:5, B:2, C:2, D:1} and {B:2, C:2, A: 5, D: 1}
The expectation of the number of traversal steps for the former is 5/10*1+2/10*2+2/10*3+1/10*4=19/10 while the expectation for the latter is 2/10* 1+2/10*2+5/10*3+1/10*4=25/10.
This improves the average selection speed, but sorting the original sequence also takes time.
First create a prefix and sequence of weight values, and then after generating a random number t, you can use the dichotomy method to find it from this prefix and sequence. Then the time complexity of the selection is 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])])

The above is the detailed content of Detailed explanation of python's random module, weighted random algorithm and implementation method. For more information, please follow other related articles on the PHP Chinese website!