Comment effectuer efficacement une sélection aléatoire pondérée avec remplacement ?

Sélection aléatoire pondérée avec et sans remplacement

La sélection d'éléments aléatoires dans une liste avec ou sans remplacement est une tâche courante en programmation. Bien qu'il existe des méthodes établies pour la sélection non pondérée et la sélection pondérée sans remplacement, la sélection d'éléments pondérés avec remplacement pose un défi unique.

Méthode d'alias pour la sélection pondérée avec remplacement

Une L'une des approches les plus efficaces pour ce scénario est la méthode Alias. Cela implique de créer des compartiments de taille égale qui représentent efficacement la liste pondérée.

Étapes de mise en œuvre :

1. Normaliser les poids : Ajuster les poids afin leur somme est égale à 1,0, représentant les probabilités de sélection.
2. Créer des partitions : Déterminez la plus petite puissance de 2 supérieure au nombre d'éléments et créez autant de partitions.
3. Attribuer des poids : Placez l'élément avec le plus petit poids dans une partition vide, en la remplissant autant que possible.
4. Remplir les partitions : Si une partition n'est pas pleine, ajoutez le élément ayant le poids le plus élevé pour remplir l'espace restant.
5. Répéter : continuez à attribuer des poids jusqu'à ce que tous les éléments soient pris en compte.

Sélection de l'exécution :

1. Générez un nombre aléatoire entre 0 et 1.
2. Décalez le nombre en fonction du logarithme du nombre de partitions (en supposant que le décalage de bits soit rapide sur votre plateforme ).
3. Si la partition est divisée, utilisez la partie décimale du nombre décalé pour décider quel élément sélectionner.

Avantages de la méthode Alias :

• Sélection rapide et efficace avec remplacement.
• Évite la méthode du réservoir pour les grandes sélections.
• Simple à mettre en œuvre et efficace en mémoire.

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!