Comment générer des nombres aléatoires pondérés en programmation : échantillonnage par rejet ou recherche itérative ?

Génération de nombres aléatoires pondérés en programmation

Les nombres aléatoires pondérés trouvent une application dans divers scénarios où des valeurs spécifiques dans une plage ont des probabilités différentes d'être sélectionnées. Dans cet article, nous explorons deux approches efficaces pour y parvenir :

La première approche, proposée par l'auteur de la question initiale, implique l'Échantillonnage par rejet. Cette méthode crée une table de recherche remplie avec les éléments de la plage, où chaque élément apparaît un nombre de fois proportionnel à son poids. Par la suite, un index aléatoire est choisi dans la table de recherche pour récupérer le nombre aléatoire. Le compromis réside ici dans la complexité temporelle linéaire de la construction de la table de recherche et dans la consommation potentielle de mémoire pour les spécifications de poids importantes.

Alternativement, la méthode Recherche itérative calcule de manière itérative la somme des poids. tout en parcourant la spécification de poids. Il compare cette somme avec un nombre généré aléatoirement entre 0 et 1. Si la somme dépasse le nombre aléatoire, la valeur correspondante est renvoyée sous forme de nombre aléatoire. Contrairement à l'échantillonnage par rejet, cette approche n'entraîne aucun coût initial mais présente une complexité temporelle moyenne linéaire par rapport au nombre d'entrées dans la spécification de poids.

Pour démontrer les deux approches en JavaScript :

// Rejection Sampling
function weightedRand(spec) {
  var i, j, table = [];
  for (i in spec) for (j = 0; j < spec[i] * 10; j++) table.push(i);
  return function() { return table[Math.floor(Math.random() * table.length)]; };
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});

// Iterative Search
function weightedRand2(spec) {
  var i, sum = 0, r = Math.random();
  for (i in spec) { sum += spec[i]; if (r <= sum) return i; }
}

Le le choix de l'approche dépend des exigences spécifiques de l'application, de l'équilibre entre la complexité temporelle, l'utilisation de la mémoire et le comportement déterministe. L'échantillonnage par rejet offre des recherches en temps constant au détriment de la construction initiale de la table, tandis que la recherche itérative offre une implémentation plus simple avec des performances en temps linéaire. En tirant parti de ces techniques, les programmeurs peuvent générer efficacement des nombres aléatoires pondérés pour leurs différents besoins de programmation.

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!