Choisir N ​​nombres aléatoires d'un ensemble

Question

J'ai un ensemble trié (std :: set pour être précis) qui contient des éléments avec un poids assigné. Je veux choisir au hasard N éléments de cet ensemble, alors que les éléments de poids plus élevé devraient avoir une plus grande probabilité d'être choisis. Tout élément peut être choisi plusieurs fois.

Je veux faire ceci aussi efficacement que possible - Je veux éviter toute copie de l'ensemble (il pourrait devenir très grand) et courir au moment O (N) si c'est possible. J'utilise C++ et je voudrais m'en tenir à une solution STL + Boost uniquement.

Est-ce que quelqu'un sait s'il existe une fonction dans STL/Boost qui effectue cette tâche? Si non, comment en mettre un en œuvre?

Answer 1

Vous devez calculer (et éventuellement mettre en cache, si vous considérez les performances) la somme de tous les poids de votre ensemble. Ensuite, générez N nombres aléatoires allant jusqu'à cette valeur. Enfin, parcourez votre ensemble en comptant la somme des poids que vous avez rencontrés jusqu'à présent. Inspecter tous les nombres aléatoires (restants). Si le nombre se situe entre la valeur précédente et la valeur suivante de la somme, insérez la valeur de l'ensemble et supprimez votre nombre aléatoire. Arrêtez lorsque votre liste de nombres aléatoires est vide ou que vous avez atteint la fin de l'ensemble.

Answer 2

Je ne connais pas les bibliothèques, mais on dirait que vous avez une roue de roulette lestée. Voici une référence avec un pseudo-code, bien que le contexte soit lié aux algorithmes génétiques: http://www.cse.unr.edu/~banerjee/selection.htm

En ce qui concerne «aussi efficacement que possible», cela dépend de certaines caractéristiques des données. Dans l'application de la roue de roulette pondérée, lors de la recherche de l'index, vous pouvez envisager une recherche binaire à la place. Cependant, ce n'est pas le cas si chaque fente de la roue de la roulette est également probable, il peut donc être logique de les examiner dans l'ordre de leurs poids.

Answer 3

Beaucoup dépend de la quantité de stockage supplémentaire que vous souhaitez dépenser pour accélérer la sélection.

Si vous n'êtes pas prêt à utiliser de stockage supplémentaire, la réponse de @Alex Emelianov est à peu près ce que je pensais de poster. Si vous souhaitez utiliser du stockage supplémentaire (et éventuellement une structure de données différente de std::set), vous pouvez créer un arbre (comme un ensemble utilise) mais à chaque nœud de l'arbre, vous stockez également le nombre (pondéré) d'éléments à gauche de ce nœud. Cela vous permettra de mapper d'un nombre généré à la valeur associée correcte avec la complexité logarithmique (plutôt que linéaire).