Générer un entier aléatoire dans une plage

J’ai besoin d’une fonction qui génèrerait un entier aléatoire dans une plage donnée (y compris les valeurs de bordure). Je n’ai pas d’exigences déraisonnables en matière de qualité / caractère aléatoire, j’ai quatre exigences:

  • J’ai besoin que ça soit rapide. Mon projet doit générer des millions (voire des dizaines de millions) de nombres aléatoires et ma fonction de générateur actuelle s’est avérée être un goulot d’étranglement.
  • J’en ai besoin pour être raisonnablement uniforme (l’utilisation de rand () est parfaitement correcte).
  • les plages min-max peuvent être n’importe quoi de à .
  • il doit être apte à être ensemencé.

J’ai actuellement le code C ++ suivant:

output = min + (rand() * (int)(max - min) / RAND_MAX) 

Le problème est que ce n’est pas vraiment uniforme – max est retourné seulement quand rand () = RAND_MAX (pour Visual C ++ c’est 1/32727). C’est un problème majeur pour les petites plages comme , où la dernière valeur n’est presque jamais renvoyée.

J’ai donc pris un stylo et du papier et ai proposé la formule suivante (qui repose sur le tour complet (int) (n + 0.5) entier):

entrer la description de l'image ici

Mais cela ne me donne toujours pas une dissortingbution uniforme. Des essais répétés avec 10 000 échantillons me donnent un rapport de 37:50:13 pour les valeurs -1, 0. 1.

Pourriez-vous s’il vous plaît suggérer une meilleure formule? (ou même la fonction de générateur de nombres pseudo-aléatoires)

Une solution dissortingbuée rapide, un peu meilleure que la vôtre, mais toujours mal uniforme est

 output = min + (rand() % static_cast(max - min + 1)) 

Sauf lorsque la taille de la plage est une puissance de 2, cette méthode produit des nombres dissortingbués non uniformes biaisés, quelle que soit la qualité de rand() . Pour un test complet de la qualité de cette méthode, veuillez lire ceci .

La réponse la plus simple (et donc la meilleure) en C ++ (en utilisant le standard 2011) est

 #include  std::random_device rd; // only used once to initialise (seed) engine std::mt19937 rng(rd()); // random-number engine used (Mersenne-Twister in this case) std::uniform_int_dissortingbution uni(min,max); // guaranteed unbiased auto random_integer = uni(rng); 

Pas besoin de réinventer la roue. Pas besoin de s’inquiéter de biais. Pas besoin de s’inquiéter d’utiliser le temps comme graine aléatoire.

Si votre compilateur prend en charge C ++ 0x et que l’utiliser est une option pour vous, alors le nouvel en-tête standard est susceptible de répondre à vos besoins. Il a une haute qualité uniform_int_dissortingbution qui accepte les limites minimum et maximum (inclusivement selon vos besoins), et vous pouvez choisir parmi différents générateurs de nombres aléatoires pour vous connecter à cette dissortingbution.

Voici un code qui génère un million de nombres aléatoires uniformément dissortingbués dans [-57, 365]. J’ai utilisé les nouvelles installations std pour le chronométrer car vous avez mentionné que la performance est une préoccupation majeure pour vous.

 #include  #include  #include  int main() { typedef std::chrono::high_resolution_clock Clock; typedef std::chrono::duration sec; Clock::time_point t0 = Clock::now(); const int N = 10000000; typedef std::minstd_rand G; G g; typedef std::uniform_int_dissortingbution<> D; D d(-57, 365); int c = 0; for (int i = 0; i < N; ++i) c += d(g); Clock::time_point t1 = Clock::now(); std::cout << N/sec(t1-t0).count() << " random numbers per second.\n"; return c; } 

Pour moi (Intel Core i5 à 2,8 GHz), ceci imprime:

2.10268e + 07 nombres aléatoires par seconde.

Vous pouvez ensemencer le générateur en passant un int à son constructeur:

  G g(seed); 

Si vous trouvez plus tard que int ne couvre pas la plage dont vous avez besoin pour votre dissortingbution, vous pouvez remédier à cela en modifiant le uniform_int_dissortingbution comme uniform_int_dissortingbution :

  typedef std::uniform_int_dissortingbution D; 

Si vous trouvez plus tard que le minstd_rand n'est pas un générateur de qualité suffisante, vous pouvez facilement le remplacer. Par exemple:

  typedef std::mt19937 G; // Now using mersenne_twister_engine 

Avoir un contrôle séparé sur le générateur de nombres aléatoires, et la dissortingbution aléatoire peut être assez libérateur.

J'ai aussi calculé (non montré) les 4 premiers "moments" de cette dissortingbution (en utilisant minstd_rand ) et les minstd_rand comparés aux valeurs théoriques pour tenter de quantifier la qualité de la dissortingbution:

 min = -57 max = 365 mean = 154.131 x_mean = 154 var = 14931.9 x_var = 14910.7 skew = -0.00197375 x_skew = 0 kurtosis = -1.20129 x_kurtosis = -1.20001 

(Le préfixe x_ fait référence à "attendu")

Divisons le problème en deux parties:

  • Génère un nombre aléatoire n compris entre 0 et (max-min).
  • Ajouter min à ce nombre

La première partie est évidemment la plus difficile. Supposons que la valeur de retour de rand () soit parfaitement uniforme. Utiliser modulo appenda un biais aux premiers (RAND_MAX + 1) % (max-min+1) . Donc, si nous pouvions changer magiquement RAND_MAX en RAND_MAX - (RAND_MAX + 1) % (max-min+1) , il n’y aurait plus de biais.

Il s’avère que nous pouvons utiliser cette intuition si nous voulons autoriser le pseudo-non-déterminisme dans le temps d’exécution de notre algorithme. Chaque fois que rand () retourne un nombre trop grand, nous demandons simplement un autre nombre aléatoire jusqu’à ce que nous en obtenions un qui soit assez petit.

Le temps d’exécution est maintenant dissortingbué géomésortingquement , avec la valeur attendue 1/pp est la probabilité d’obtenir un nombre suffisamment petit au premier essai. Puisque RAND_MAX - (RAND_MAX + 1) % (max-min+1) est toujours inférieur à (RAND_MAX + 1) / 2 , nous soaps que p > 1/2 , donc le nombre d’itérations attendu sera toujours inférieur à deux pour toute gamme. Il devrait être possible de générer des dizaines de millions de nombres aléatoires en moins d’une seconde sur un processeur standard avec cette technique.

MODIFIER:

Bien que ce qui précède soit techniquement correct, la réponse de DSimon est probablement plus utile dans la pratique. Vous ne devriez pas implémenter ce genre de choses vous-même. J’ai vu beaucoup d’implémentations de l’échantillonnage de rejet et il est souvent très difficile de voir si c’est correct ou non.

Que diriez-vous de la Mersenne Twister ? L’implémentation de boost est plutôt facile à utiliser et est bien testée dans de nombreuses applications du monde réel. Je l’ai utilisé moi-même dans plusieurs projets académiques tels que l’intelligence artificielle et les algorithmes évolutifs.

Voici leur exemple où ils peuvent facilement lancer un dé à six faces:

 #include  #include  #include  boost::mt19937 gen; int roll_die() { boost::uniform_int<> dist(1, 6); boost::variate_generator > die(gen, dist); return die(); } 

Oh, et voici un peu plus de proxénétisme de ce générateur au cas où vous ne seriez pas convaincu de devoir l’utiliser sur le rand() largement inférieur:

Le Mersenne Twister est un générateur de “nombres aléatoires” inventé par Makoto Matsumoto et Takuji Nishimura; leur site Web comprend de nombreuses implémentations de l’algorithme.

Essentiellement, le Mersenne Twister est un très grand registre à décalage à retour linéaire. L’algorithme fonctionne sur une graine de 19 937 bits, stockée dans un tableau de 624 éléments d’entiers non signés de 32 bits. La valeur 2 ^ 19937-1 est un nombre premier de Mersenne; la technique de manipulation de la graine est basée sur un ancien algorithme de “torsion”, d’où le nom “Mersenne Twister”.

Un aspect attrayant de la Mersenne Twister est son utilisation des opérations binarys – par opposition à une multiplication fastidieuse – pour générer des nombres. L’algorithme a également une très longue période et une bonne granularité. Il est à la fois rapide et efficace pour les applications non cryptographiques.

 int RandU(int nMin, int nMax) { return nMin + (int)((double)rand() / (RAND_MAX+1) * (nMax-nMin+1)); } 

Ceci est un mappage de 32768 entiers à (nMax-nMin + 1) entiers. Le mappage sera assez bon si (nMax-nMin + 1) est petit (comme dans votre exigence). Notez cependant que si (nMax-nMin + 1) est grand, le mappage ne fonctionnera pas (par exemple, vous ne pouvez pas mapper 32768 valeurs sur 30000 valeurs avec une probabilité égale). Si de telles plages sont nécessaires, vous devez utiliser une source aléatoire 32 bits ou 64 bits, au lieu du rand 15 bits, ou ignorer les résultats rand () qui sont hors plage.

Voici une version non biaisée qui génère des nombres en [low, high] :

 int r; do { r = rand(); } while (r < ((unsigned int)(RAND_MAX) + 1) % (high + 1 - low)); return r % (high + 1 - low) + low; 

Si votre plage est raisonnablement petite, il n'y a aucune raison de mettre en cache le côté droit de la comparaison dans la boucle do .

Je recommande la bibliothèque Boost.Random , très détaillée et bien documentée, qui vous permet de spécifier explicitement la dissortingbution souhaitée et, dans les scénarios non cryptographiques, elle peut en fait surpasser une implémentation de randonnées de bibliothèque C classique.

supposons que min et max sont des valeurs int, [et] signifie inclure cette valeur, (et) signifie ne pas inclure cette valeur, en utilisant ci-dessus pour obtenir la bonne valeur en utilisant c ++ rand ()

référence: pour () [] définir, visiter:

https://en.wikipedia.org/wiki/Interval_(mathematics)

pour les fonctions rand et srand ou RAND_MAX, visitez:

http://fr.cppreference.com/w/cpp/numeric/random/rand

[min max]

 int randNum = rand() % (max - min + 1) + min 

(min max]

 int randNum = rand() % (max - min) + min + 1 

[min max)

 int randNum = rand() % (max - min) + min 

(min max)

 int randNum = rand() % (max - min - 1) + min + 1 

Dans ce thread, l’échantillonnage de rejet a déjà été discuté, mais je voulais suggérer une optimisation basée sur le fait que rand() % 2^something n’introduit aucun biais comme déjà mentionné ci-dessus.

L’algorithme est très simple:

  • calculer la plus petite puissance de 2 supérieure à la longueur de l’intervalle
  • randomiser un nombre dans cet “nouvel” intervalle
  • renvoyer ce nombre s’il est inférieur à la longueur de l’intervalle d’origine
    • rejeter autrement

Voici mon exemple de code:

 int randInInterval(int min, int max) { int intervalLen = max - min + 1; //now calculate the smallest power of 2 that is >= than `intervalLen` int ceilingPowerOf2 = pow(2, ceil(log2(intervalLen))); int randomNumber = rand() % ceilingPowerOf2; //this is "as uniform as rand()" if (randomNumber < intervalLen) return min + randomNumber; //ok! return randInInterval(min, max); //reject sample and try again } 

Cela fonctionne particulièrement bien pour les petits intervalles, car la puissance de 2 sera "plus proche" de la longueur de l'intervalle réel, et le nombre de ratés sera donc plus petit.

PS
Évidemment, éviter la récursivité serait plus efficace (pas besoin de calculer au-delà du plafond des journaux ..) mais je pensais que c'était plus lisible pour cet exemple.

La formule est très simple, alors essayez cette expression,

  int num = (int) rand() % (max - min) + min; //Where rand() returns a random number between 0.0 and 1.0 

L’expression suivante devrait être sans biais si je ne me trompe pas:

 std::floor( ( max - min + 1.0 ) * rand() ) + min; 

Je suppose ici que rand () vous donne une valeur aléatoire comprise entre 0.0 et 1.0, y compris 1.0, et que max et min sont des entiers avec la condition que min