En utilisant boost :: aléatoire pour sélectionner à partir d'un std :: liste où les éléments sont supprimés

Question

Voir cette question connexe sur une utilisation plus générique de la bibliothèque Boost aléatoire.

Mes questions consiste à sélectionner un élément aléatoire d'un std::list, faire une opération, ce qui pourrait inclure potentally retirer l'élément de la liste, puis choisir un autre élément aléatoire, jusqu'à ce qu'une condition soit satisfaite.

Le code de boost et pour regarder en boucle à peu près comme ceci:

// create and insert elements into list
std::list<MyClass> myList;
//[...]

// select uniformly from list indices
boost::uniform_int<> indices( 0, myList.size()-1 );    
boost::variate_generator< boost::mt19937, boost::uniform_int<> > 
  selectIndex(boost::mt19937(), indices);

for( int i = 0; i <= maxOperations; ++i ) {
    int index = selectIndex();
    MyClass & mc = myList.begin() + index;

    // do operations with mc, potentially removing it from myList
    //[...]
}

Mon problème est que dès que les opérations effectuées sur un résultat d'élément dans l'enlèvement d'un élément, le variate_generator a le potentiel de sélectionner un index non valide dans la liste. Je ne pense pas qu'il est logique de recréer complètement le variate_generator chaque fois, surtout si je sème avec le temps (0).

Answer 1

Je suppose que MyClass & mc = myList.begin() + index; est code juste pseudo, comme commencer renvoie un itérateur et je ne pense pas que itérateurs liste (non-accès aléatoire) operator+ de soutien.

Pour autant que je peux dire, avec le générateur de variate vos trois options de base dans ce cas sont:

• Recréer le générateur lorsque vous supprimez un élément.
• Do filtrage sur l'index généré et si elle est> = la taille actuelle de la liste, nouvelle tentative jusqu'à obtenir un index valide. Notez que si vous supprimez un grand nombre d'indices cela pourrait être assez inefficace aussi bien.
• Laissez le nœud dans la liste, mais marquer invalide donc si vous essayez de faire fonctionner sur cet indice en toute sécurité non-ops. Ceci est juste une version différente de la seconde option.

Alternativement vous pouvez concevoir un algorithme de génération d'index différent qui est en mesure d'adapter à la taille de changement de conteneur.

Answer 2

Vous pouvez créer votre propre classe de distribution de uniform_contained_int, qui acceptent un conteneur dans son constructeur, agrège un uniform_int, et reconstitue le uniform_distribution chaque fois que le conteneur change de taille. Regardez le description de la uniform_int qui les méthodes que vous devez mettre en œuvre pour créer votre distribution.

Answer 3

Je pense que vous avez plus à vous soucier de la performance sage. En particulier ceci:

std::list<MyClass> myList;
myList.begin() + index;

est pas une façon particulièrement rapide de geting index-ème élément.

Je le transformer en quelque chose comme ça (qui devrait fonctionner sur une séquence aléatoire de la liste):

X_i ~ U(0, 1) for all i
left <- max_ops
N <- list size
for each element
  if X_i < left/N
    process element
    left--
  N--

à condition que vous n'avez pas besoin de la permutation aléatoire des éléments.