Python의 Random 모듈, Weighted Random 알고리즘 및 구현 방법에 대한 자세한 설명

random은 무작위로 숫자를 생성하거나 문자열을 선택하는 데 사용할 수 있습니다.
•random.seed(x)는 난수 생성기 의 시드를 변경합니다.
일반적으로 시드를 특별히 설정할 필요는 없으며, Python이 자동으로 시드를 선택합니다.
•random.random()은 임의의 부동 소수점 숫자 n,0 <= n < 1을 생성하는 데 사용됩니다.
•random.uniform(a,b)는 임의의 부동 소수점 숫자를 생성하는 데 사용됩니다. 지정된 범위, 생성된 무작위 정수 a<=n<=b;
•random.randint(a,b)는 지정된 범위 내에서 정수를 생성하는 데 사용됩니다. a는 하한입니다. b는 상한값입니다. a=b인 경우 생성된 임의의 정수 a<=n<=b; a>b인 경우 n=a, 오류
•random.randrange( start], stop [,step] ) 지정된 범위 [start, stop)의 집합에서 난수를 얻어 지정된 진수만큼 증가합니다. 기본 값은 1
•random.choice(sequence)입니다. 매개변수 시퀀스로 표시되는 시퀀스에서 임의의 요소를 얻습니다. 특정 유형이 아닌 순서가 지정된 유형은 일반적으로 목록, 튜플, 문자열 등을 나타냅니다.
•random.shuffle(x[,random])은 목록의 요소를 교란(셔플링)하여 원래 목록을 변경하는 데 사용됩니다.
•random.sample(sequence,k) 지정된 시퀀스에서 k개의 요소를 무작위로 가져와 다음과 같이 반환합니다. 원본 시퀀스를 변경하지 않고 조각
이제 기본 지식이 있으므로 가중 무작위 알고리즘을 구현해 보겠습니다.
가중 무작위 알고리즘은 일반적으로 다음 시나리오에서 사용됩니다. 4개를 포함하는 집합 S가 있습니다. A, B, C, D와 같은 항목입니다. 이때, 그 중에서 무작위로 아이템을 뽑고 싶은데 뽑을 확률이 다릅니다. 예를 들어 A를 뽑을 확률은 50%, B와 C를 뽑을 확률은 20%, D를 뽑을 확률은 10%입니다. 일반적으로 각 항목에 가중치를 부여할 수 있으며, 추출 확률은 이 가중치에 비례합니다. 그러면 위의 집합은 다음과 같습니다:
{A:5, B:2, C:2, D:1}
방법 1:
가장 간단한 방법은 다음과 같습니다.
가중치 값에 따라 시퀀스를 다음과 같이 확장합니다: listed=[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]))

방법 2:
더 일반적으로 사용되는 방법은 다음과 같습니다.
가중치의 합을 계산한 후 1과 합 사이의 숫자 R을 무작위로 선택합니다. 그런 다음 전체 컬렉션을 순회하고 순회된 항목의 가중치 합계를 계산합니다. R보다 크거나 같으면 순회를 중지하고 발견된 항목을 선택합니다.
위 세트를 예로 들면 합은 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])])

방법 3:
먼저 원본 시퀀스를 가중치에 따라 정렬할 수 있습니다. 이렇게 순회하면 확률이 높은 아이템을 빠르게 만날 수 있어 순회해야 하는 항목의 개수가 줄어듭니다. (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)입니다.

위 내용은 Python의 Random 모듈, Weighted Random 알고리즘 및 구현 방법에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!