Comment puis-je générer des nombres aléatoires pondérés à l'aide de la bibliothèque Boost ?

Nombres aléatoires pondérés dans Boost

La bibliothèque Boost offre une fonctionnalité étendue de génération de nombres aléatoires. Bien qu'il offre une génération simple de nombres aléatoires, il ne prend pas en charge les nombres aléatoires pondérés. Cet article explore les techniques de mise en œuvre de la sélection de nombres aléatoires pondérés à l'aide des fonctions Boost brutes.

Algorithme de randomisation pondéré

Pour générer un nombre aléatoire pondéré, nous pouvons utiliser l'algorithme suivant :

1. Calculez la somme de tous les poids.
2. Générez un nombre aléatoire entre 0 et la somme des poids (inclus).
3. Soustrayez itérativement les poids du nombre aléatoire jusqu'à ce qu'il devienne négatif. L'index de l'élément actuel est le nombre pondéré sélectionné.

Adaptation à Boost

Cet algorithme peut être adapté à Boost comme suit :

using namespace boost;

int weightedRandom(const std::vector<int>& weights) {
  // Calculate the sum of weights
  int sum = accumulate(weights.begin(), weights.end(), 0);

  // Generate a random number between 0 and the sum
  variate_generator<mt19937, uniform_int_distribution<int>> rand(generator());
  int rnd = rand(sum);

  // Traverse weights and subtract until random number becomes negative
  for (size_t i = 0; i < weights.size(); ++i) {
    if (rnd - weights[i] < 0) {
      return i;
    }
    rnd -= weights[i];
  }

  // Should never reach here
  assert(false);
}

Optimisation pour des poids inchangés

Si les poids sont rarement modifiés et que le La liste est raisonnablement longue, nous pouvons l'optimiser en précalculant les sommes de poids cumulées et en utilisant la recherche binaire.

Échantillonnage de réservoir pour une taille de liste inconnue

Pour les listes de taille inconnue, échantillonnage de réservoir peut être utilisé avec des poids adaptations.

Conclusion

Bien que Boost ne dispose pas d'une fonction de nombres aléatoires pondérés dédiée, les techniques présentées permettent une génération efficace et précise à l'aide des fonctions Boost brutes.

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!