Comment sélectionner efficacement un élément aléatoire à partir d’un std :: set

Utilisez boost::container::flat_set place:

 boost::container::flat_set set; // ... auto it = set.begin() + rand() % set.size(); 

Les insertions et les suppressions deviennent O (N) cependant, je ne sais pas si c’est un problème. Vous avez toujours des recherches O (log N) et le fait que le conteneur soit contigu donne une amélioration globale qui l’emporte souvent sur la perte d’insertions et de suppressions O (log N).

Qu’en est-il d’un prédicat pour find (ou lower_bound ) qui provoque une traversée aléatoire de l’arbre? Vous devrez lui indiquer la taille de l’ensemble pour qu’il puisse estimer la hauteur de l’arbre et parfois se terminer avant les nœuds d’extrémité.

Edit: j’ai compris que le problème avec ceci est que std::lower_bound prend un prédicat mais n’a aucun comportement semblable à un arbre (en interne, il utilise std::advance qui est discuté dans les commentaires d’une autre réponse). std::set<>::lower_bound utilise le prédicat de l’ensemble, qui ne peut pas être aléatoire et qui a toujours un comportement similaire à celui d’un ensemble.

Aha , vous ne pouvez pas utiliser un prédicat différent, mais vous pouvez utiliser un prédicat mutable. Puisque std::set transmet l’object de prédicat par valeur, vous devez utiliser un predicate & comme prédicat afin de pouvoir l’atteindre et le modifier (en le réglant en mode “aléatoire”).

Voici un exemple quasi-fonctionnel. Malheureusement, je ne peux pas envelopper mon cerveau autour du prédicat aléatoire correct, mon aléa n’est donc pas excellent, mais je suis sûr que quelqu’un peut comprendre cela:

 #include  #include  #include  #include  using namespace std; template  struct RandomPredicate { RandomPredicate() : size(0), randomize(false) { } bool operator () (const T& a, const T& b) { if (!randomize) return a < b; int r = rand(); if (size == 0) return false; else if (r % size == 0) { size = 0; return false; } else { size /= 2; return r & 1; } } size_t size; bool randomize; }; int main() { srand(time(0)); RandomPredicate pred; set & > s(pred); for (int i = 0; i < 100; ++i) s.insert(i); pred.randomize = true; for (int i = 0; i < 100; ++i) { pred.size = s.size(); set >::iterator it = s.lower_bound(0); cout << *it << endl; } } 

Mon test aléatoire à moitié cuit est ./demo | sort -u | wc -l ./demo | sort -u | wc -l ./demo | sort -u | wc -l pour voir combien d'entiers uniques je sors. Avec un plus grand échantillon, essayez ./demo | sort | uniq -c | sort -n ./demo | sort | uniq -c | sort -n ./demo | sort | uniq -c | sort -n pour rechercher des motifs indésirables.

Si vous pouviez accéder à l’arbre rouge-noir sous-jacent (en supposant qu’il en existe un), vous pourriez accéder à un nœud aléatoire dans O (log n) en choisissant L / R comme les bits successifs d’un ceil(log2(n)) entier aléatoire. . Cependant, vous ne pouvez pas, car la structure de données sous-jacente n’est pas exposée par la norme.

La solution de Xeo consistant à placer des iterators dans un vecteur est de définir un temps et un espace O (n), mais globalement amortie. Cela se compare favorablement à std::next , qui est le temps O (n).

Vous pouvez utiliser la méthode std::advance :

 set  myset; //insert some elements into myset int rnd = rand() % myset.size(); set  :: const_iterator it(myset.begin()); advance(it, rnd); //now 'it' points to your random element 

Une autre façon de faire, probablement moins aléatoire:

 int mini = *myset().begin(), maxi = *myset().rbegin(); int rnd = rand() % (maxi - mini + 1) + mini; int rndresult = *myset.lower_bound(rnd); 

Si l’ensemble ne se met pas à jour fréquemment ou si vous n’avez pas besoin d’exécuter cet algorithme fréquemment, conservez une copie en miroir des données dans un vector (ou copiez simplement l’ensemble sur un vecteur au besoin) et sélectionnez-la de manière aléatoire.

Une autre approche, comme le montre un commentaire, consiste à conserver un vecteur d’iterators dans l’ensemble (ils ne sont invalidés que lors de la suppression d’éléments pour un set ) et à sélectionner un iterator de manière aléatoire.

Enfin, si vous n’avez pas besoin d’un jeu d’arborescence, vous pouvez utiliser vector ou deque comme conteneur sous-jacent et sortinger / unique-ify si nécessaire.

Vous pouvez le faire en maintenant un tableau normal de valeurs. lorsque vous insérez dans l’ensemble, vous ajoutez l’élément à la fin du tableau ( O (1) ), puis, lorsque vous souhaitez générer un nombre aléatoire, vous pouvez également le récupérer dans le tableau de O (1) .

Le problème survient lorsque vous souhaitez supprimer des éléments du tableau. La méthode la plus naïve prendrait O (n) , ce qui pourrait être assez efficace pour vos besoins. Cependant, ceci peut être amélioré en O (log n) en utilisant la méthode suivante;

Conservez, pour chaque index i du tableau, prfx[i] , qui représente le nombre d’éléments non supprimés compris entre 0...i dans le tableau. Conservez une arborescence de segments dans laquelle vous conservez le maximum de prfx[i] contenu dans chaque plage.

La mise à jour de l’arborescence des segments peut être effectuée en O (log n) par suppression. Désormais, lorsque vous souhaitez accéder au nombre aléatoire, vous interrogez l’arborescence de segment pour rechercher l’index “réel” du nombre (en recherchant la plage la plus ancienne dans laquelle le maximum prfx est égal à l’index aléatoire). Cela rend la génération de nombres aléatoires de complexité O (log n) .