Quelle approche est la meilleure pour générer un nombre aléatoire pondéré : table de recherche ou sommation itérative ?

Générer un nombre aléatoire pondéré : alternatives efficaces à l'échantillonnage par rejet

Alors que l'échantillonnage par rejet est une approche simple pour sélectionner un nombre aléatoire avec des probabilités pondérées , ce n'est peut-être pas la solution la plus efficace dans tous les scénarios. Voici deux stratégies alternatives avec des caractéristiques de performance distinctes :

Table de recherche à temps constant (via une fonction d'ordre supérieur)

Cette approche consiste à créer une table de recherche à partir du poids spécification et renvoyant une fonction qui récupère les valeurs de la table. Les avantages incluent :

• Sélection de valeur à temps constant
• Mise en œuvre simple à l'aide d'une fonction d'ordre supérieur

Cependant, cette stratégie nécessite un temps linéaire pour construire le tableau et peut consommer une mémoire importante pour les spécifications volumineuses ou les poids avec des valeurs petites ou précises.

Itératif Sommation

Dans cette stratégie, un nombre aléatoire est généré dans la plage [0,1) et comparé de manière itérative à la somme cumulée des poids. Si le nombre aléatoire se situe dans la somme cumulée pour une valeur particulière, cette valeur est renvoyée. Les avantages de cette approche incluent :

• Aucun coût initial de construction de la table
• Performance moyenne linéaire par rapport au nombre d'entrées

Cependant, cette approche peut être plus gourmand en calcul qu'en temps constant recherche.

Conclusion

Le choix de l'approche dépend des exigences spécifiques de l'application. La recherche en temps constant est idéale pour les scénarios critiques en termes de performances, tandis que la sommation itérative est plus adaptée aux scénarios avec des spécifications importantes ou des poids avec des valeurs petites ou précises.

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!