Explication détaillée du module aléatoire de Python, de l'algorithme aléatoire pondéré et de la méthode d'implémentation

aléatoire est utilisé pour générer des nombres aléatoires. Nous pouvons l'utiliser pour générer des nombres aléatoirement ou sélectionner des chaînes.
•random.seed(x) change la graine du générateur de nombres aléatoires .
Généralement, il n'est pas nécessaire de définir spécifiquement la graine, Python sélectionnera automatiquement la graine.
•random.random() est utilisé pour générer un nombre à virgule flottante aléatoire n,0 <= n < 1
•random.uniform(a,b) est utilisé pour générer un nombre à virgule flottante aléatoire dans une plage spécifiée, généré aléatoire entier a<=n<=b;
•random.randint(a,b) est utilisé pour générer un entier dans une plage spécifiée, a est la limite inférieure, b est la limite supérieure, l'entier aléatoire généré a<=n<=b; si a=b, alors n=a si a>b, erreur
•random.randrange([ start], stop [,step] ) Obtenez un nombre aléatoire à partir de l'ensemble dans la plage spécifiée [start, stop), augmentant de la base spécifiée. La valeur par défaut de la base est 1
•random.choice(sequence) Obtenir un élément aléatoire à partir de la séquence, représenté par le paramètre séquence. Un type ordonné, et non un type spécifique, fait généralement référence à une liste, un tuple, une chaîne, etc.
•random.shuffle(x[,random]) est utilisé pour perturber (mélanger) les éléments d'une liste qui modifieront la liste d'origine
•random.sample(sequence,k) Obtenez au hasard k éléments de la séquence spécifiée et renvoyez-les sous forme un fragment, sans changer la séquence d'origine
Maintenant que nous avons les connaissances de base, implémentons un algorithme aléatoire pondéré :
L'algorithme aléatoire pondéré est généralement utilisé dans les scénarios suivants : Il existe un ensemble S, qui contient quatre éléments, tels que A, B, C et D. À l'heure actuelle, nous voulons en tirer un élément au hasard, mais la probabilité de tirer est différente. Par exemple, nous espérons que la probabilité de tirer A est de 50 %, la probabilité de tirer B et C est de 20 % et la probabilité de tirer A est de 50 %. la probabilité de tirer D est de 10 %. D’une manière générale, on peut attribuer un poids à chaque élément, et la probabilité d’extraction est proportionnelle à ce poids. Ensuite, l'ensemble ci-dessus devient :
{A:5, B:2, C:2, D:1>
Méthode 1 :
La méthode la plus simple peut ressembler à ceci :
Développez la séquence en fonction de la valeur de poids dans : lists=[A,A,A,A,A,B,B,C,C,D], puis sélectionnez-en une au hasard avec random.choice(lists). Bien que la complexité temporelle de cette sélection soit O(1), la quantité de données est importante et la consommation d'espace est trop importante.

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

Méthode 2 :
La méthode la plus courante est la suivante :
Calculez la somme des poids, puis sélectionnez au hasard un nombre compris entre 1 et la somme R, puis parcourez toute la collection et comptez la somme des poids des éléments parcourus. S'il est supérieur ou égal à R, arrêtez le parcours et sélectionnez les éléments rencontrés.
En utilisant l'ensemble ci-dessus comme exemple, la somme est égale à 10. Si le nombre aléatoire est compris entre 1 et 5, le parcours se terminera lorsque le premier nombre sera parcouru. cohérent avec la probabilité sélectionnée.
Lors de la sélection, vous devez parcourir la collection et sa complexité temporelle est 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])])

Méthode 3 :
Vous pouvez d'abord trier la séquence originale en fonction du poids. Lors du parcours de cette manière, les éléments présentant une forte probabilité peuvent être rencontrés rapidement, ce qui réduit le nombre d'éléments à parcourir. (Parce que rnd décrémente le plus rapidement (soustrayez d'abord le plus grand nombre))
Comparez {A:5, B:2, C:2, D:1} et {B:2, C:2, A: 5, D : 1}
L'espérance du nombre d'étapes de parcours pour le premier est 5/10*1+2/10*2+2/10*3+1/10*4=19/10 tandis que l'espérance pour le ce dernier est 2/10* 1+2/10*2+5/10*3+1/10*4=25/10.
Cela améliore la vitesse moyenne de sélection, mais le tri de la séquence originale prend également du temps.
Créez d'abord un préfixe et une séquence de valeurs de poids, puis après avoir généré un nombre aléatoire t, vous pouvez utiliser la méthode de dichotomie pour le trouver à partir de ce préfixe et de cette séquence. Ensuite, la complexité temporelle de la sélection est 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])])

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!