Effective Java Item 47: Connaissez et utilisez vos bibliothèques – Exemple de méthode avec un nombre entier aléatoire imparfait
Dans l’exemple donné par Josh à propos de la méthode aléatoire imparfaite qui génère un nombre aléatoire positif avec une limite supérieure donnée n , je ne comprends pas les deux défauts qu’il énonce.
La méthode du livre est la suivante:
private static final Random rnd = new Random(); //Common but deeply flawed static int random(int n) { return Math.abs(rnd.nextInt()) % n; }
- Il dit que si n est une petite puissance de 2, la séquence de nombres aléatoires générés se répète après une courte période de temps. pourquoi est-ce le cas? La documentation de
Random.nextInt()indiqueReturns the next pseudorandom, uniformly dissortingbuted int value from this random number generator's sequence.Donc, ne devrait pas être que si n est un petit entier alors la séquence se répète, pourquoi cela s’applique-t-il seulement aux puissances de 2? - Ensuite, il dit que si n n’est pas une puissance de 2, certains nombres seront retournés en moyenne plus fréquemment que d’autres. Pourquoi cela se produit-il si
Random.nextInt()génère des entiers aléatoires uniformément répartis? (Il fournit un extrait de code qui démontre clairement cela, mais je ne comprends pas pourquoi c’est le cas, et comment cela est lié à n étant une puissance de 2).
- Générer une dissortingbution de probabilité
- pourcentages aléatoires java
- API Hibernate Criteria: obtenez n lignes aléatoires
- Algorithme pour générer des nombres aléatoires de Poisson et binomiaux?
- Générer un nombre aléatoire avec max, min et moyenne (moyenne) en Java
- UUID.randomUUID () peut-il être utilisé comme mot de passe à utilisation unique?
- Comment générer une permutation aléatoire en Java?
- Aléatoire sur ThreadLocalRandom
- Quel est l’avantage de semer un générateur de nombres aléatoires avec uniquement des nombres premiers?
- SecureRandom avec NativePRNG vs SHA1PRNG
Question 1: si n est une petite puissance de 2, la séquence de nombres aléatoires générés se répète après une courte période de temps.
Ce n’est pas un corollaire de ce que dit Josh; c’est plutôt une propriété connue des générateurs linéaires congruentiels . Wikipedia a ceci à dire:
Un autre problème des GLC est que les bits de poids faible de la séquence générée ont une période beaucoup plus courte que la séquence dans son ensemble si m est défini sur une puissance de 2. En général, le nième chiffre le moins significatif de la base b représentation de la séquence de sortie, où b k = m pour un entier k, se répète avec au plus la période b n .
Ceci est également noté dans le Javadoc :
Les générateurs de nombres pseudo-aléatoires congruentiels linéaires tels que celui implémenté par cette classe sont connus pour avoir de courtes périodes dans la séquence de valeurs de leurs bits de poids faible.
L’autre version de la fonction, Random.nextInt(int) , contourne ce Random.nextInt(int) en utilisant différents bits dans ce cas (c’est le mien):
L’algorithme traite le cas où n est une puissance de deux spécialement: il renvoie le nombre correct de bits de poids fort du générateur de nombres pseudo-aléatoires sous-jacent.
C’est une bonne raison de préférer Random.nextInt(int) à utiliser Random.nextInt() et à effectuer votre propre transformation de plage.
Question 2: Ensuite, il dit que si n est pas une puissance de 2, certains nombres seront retournés en moyenne plus souvent que d’autres.
Il y a 2 32 nombres distincts qui peuvent être retournés par nextInt() . Si vous essayez de les placer dans n compartiments en utilisant % n , et n n’est pas une puissance de 2, certains compartiments auront plus de nombres que d’autres. Cela signifie que certains résultats se produiront plus fréquemment que d’autres, même si la dissortingbution initiale était uniforme.
Regardons ceci en utilisant de petits nombres. Disons que nextInt() renvoyé quatre résultats équiprobables, 0, 1, 2 et 3. Voyons ce qui se passe si nous leur appliquons % 3 :
0 maps to 0 1 maps to 1 2 maps to 2 3 maps to 0
Comme vous pouvez le voir, l’algorithme renvoie 0 deux fois plus fréquemment que 1 et 2.
Cela ne se produit pas lorsque n est une puissance de deux, puisqu’un pouvoir de deux est divisible par l’autre. Considérons n=2 :
0 maps to 0 1 maps to 1 2 maps to 0 3 maps to 1
Ici, 0 et 1 se produisent avec la même fréquence.
Ressources additionnelles
Voici quelques ressources supplémentaires, même si elles sont tangentiellement pertinentes, liées aux GLC:
- Les tests spectraux sont des tests statistiques utilisés pour évaluer la qualité des GLC. Lisez plus ici et ici .
- Une collection de générateurs de nombres pseudo-aléatoires classiques avec des structures linéaires a quelques jolis nuages de points (le générateur utilisé en Java est appelé DRAND48 ).
- Il y a une discussion intéressante sur crypto.SE concernant la prédiction des valeurs du générateur Java.
1) Lorsque n est une puissance de 2, rnd % n équivaut à sélectionner quelques bits inférieurs de l’original. Les bits inférieurs de nombres générés par le type de générateurs utilisés par Java sont connus pour être “moins aléatoires” que les bits supérieurs. C’est juste la propriété de la formule utilisée pour générer les nombres.
2) Imaginons que la plus grande valeur possible, retournée par random() soit 10 et n = 7 . Maintenant, faites n % 7 cartographie les numéros 7, 8, 9 et 10 dans 0, 1, 2, 3 respectivement. Par conséquent, si le nombre original est uniformément dissortingbué, le résultat sera fortement biaisé par rapport aux nombres inférieurs, car ils apparaîtront deux fois plus souvent que 4, 5 et 6. Dans ce cas, cela se produit que n soit une puissance de deux ou non, mais si au lieu de 10 nous choisissons, disons, 15 (soit 2 ^ 4-1), alors n , c’est-à-dire une puissance de deux, donnerait une dissortingbution uniforme, car il n’y aurait pas “d’excès” “les nombres laissés à la fin de la plage pour provoquer un biais, car le nombre total de valeurs possibles serait exactement divisible par le nombre de rests possibles.