Effective Java Artikel 47: kennen und nutzen Sie Ihre Bibliotheken - Flawed Zufallszahl-Methode Beispiel

Question

Im Beispiel Josh von der fehlerhaften Zufallsmethode gibt, die eine positive Zufallszahl mit einem oberen n gebunden gegeben erzeugt, ich verstehen nicht, die beide von die Fehler, die er angibt.

Das Verfahren ist vom Buch:

private static final Random rnd = new Random(); 

//Common but deeply flawed 
static int random(int n) { 
    return Math.abs(rnd.nextInt()) % n; 
} 

• Er sagt, dass, wenn n eine kleine Potenz von 2, die Folge von Zufallszahlen, die erzeugt werden, wird sich der Zeit nach kurzer Zeit wiederholen. Warum ist das der Fall? Die Dokumentation für Random.nextInt() sagt Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence. Also sollte es nicht sein, dass, wenn n eine kleine ganze Zahl ist, dann wiederholt sich die Sequenz selbst, warum gilt dies nur für Potenzen von 2?
• Als nächstes sagt er, dass, wenn n keine Potenz von 2 ist, einige Zahlen im Durchschnitt häufiger zurückgegeben werden als andere. Warum tritt dies auf, wenn Random.nextInt() Zufallszahlen erzeugt, die gleichmäßig verteilt sind? (Er stellt ein Code-Snippet zur Verfügung, das dies deutlich zeigt, aber ich verstehe nicht, warum das der Fall ist und wie dies damit zusammenhängt, dass n eine Potenz von 2 ist).

Answer 1

Frage 1: wenn n eine kleine Potenz von 2, die Folge von Zufallszahlen ist, die generiert werden, wiederholt sich nach einer kurzen Zeit.

Dies ist keine Folge von allem, was Josh sagt; es ist einfach eine bekannte Eigenschaft von linear congruential generators. Wikipedia hat folgendes zu sagen:

Ein weiteres Problem von LCGs ist, dass die niederwertigen Bits der generierten Sequenz eine viel kürzere Periode haben als die Sequenz als Ganzes, wenn m auf eine Potenz von 2 gesetzt ist. Im Allgemeinen wird die n-te niederwertigste Ziffer in der Basis-b-Darstellung der Ausgabesequenz, wobei b ^k = m für eine ganze Zahl k ist, mit höchstens Periode ⁿ wiederholt.

Dies wird auch in der Javadoc notiert:

linearen Kongruenz Pseudo-Zufallszahlengeneratoren, wie die von dieser Klasse implementiert sind dafür bekannt, eine kurze Zeit in der Abfolge der Werte ihrer nieder- haben Bits bestellen.

Die andere Version der Funktion, Random.nextInt(int) arbeitet um diesen durch verschiedene Bits in diesem Fall (Hervorhebung von mir) mit:

Der Algorithmus, den Fall behandelt, wobei n eine Potenz von zwei speziell ist: es gibt die korrekte Anzahl von höherwertigen Bits aus dem zugrundeliegenden Pseudozufallszahlengenerator zurück.

Dies ist ein guter Grund, Random.nextInt(int) über lieber mit Random.nextInt() und einen eigenen Bereich Transformation zu tun.

Frage 2: Weiter sagt er, dass, wenn n keine Potenz von 2 ist, werden einige Zahlen im Durchschnitt häufiger als andere zurückgeführt werden.

Es gibt 2 verschiedene Zahlen, die von nextInt() zurückgegeben werden können. Wenn Sie versuchen, sie unter Verwendung von % n in n-Buckets zu setzen, und n ist keine Potenz von 2, haben einige Buckets mehr Zahlen als andere. Dies bedeutet, dass einige Ergebnisse häufiger auftreten als andere, obwohl die ursprüngliche Verteilung einheitlich war.

Schauen wir uns das mit kleinen Zahlen an. Lassen Sie uns sagen nextInt() vier equiprobable Ergebnisse zurückgegeben, 0, 1, 2 und 3 Mal sehen, was passiert, wenn wir % 3 auf sie angewendet passiert:

0 maps to 0 
1 maps to 1 
2 maps to 2 
3 maps to 0 

Wie Sie sehen können, würde der Algorithmus 0 zurück doppelt so häufig wie es wäre, return each von 1 und 2.

Dies passiert nicht, wenn n eine Potenz von Zwei ist, da eine Potenz von Zwei durch die andere teilbar ist. Betrachten n=2:

0 maps to 0 
1 maps to 1 
2 maps to 0 
3 maps to 1 

Hier 0 und 1 erfolgen mit der gleichen Frequenz.

Zusätzliche Ressourcen

Hier sind einige weitere - wenn auch nur tangential relevant - Ressourcen zu LCGs bezogen werden:

• Spectral Tests statistischen Tests verwendet werden, um die Qualität der LCGs zu beurteilen. Lesen Sie mehr here und here.
• A collection of classical pseudorandom number generators with linear structures hat einige hübsche Streudiagramme (der in Java verwendete Generator heißt DRAND48).
• Es gibt eine interessante discussion auf crypto.SE über Vorhersage von Werten aus Java-Generator.

Answer 2

1) Wenn n eine Potenz von 2 ist rnd % n äquivalent einige unteren Bits des Originals auswählen. Es ist bekannt, dass niedrigere Bits von Zahlen, die durch die Art von Generatoren erzeugt werden, die von Java verwendet werden, "weniger zufällig" sind als die höheren Bits. Es ist nur die Eigenschaft der Formel, die zum Erzeugen der Zahlen verwendet wird.

2) Stellen Sie sich vor, dass der größtmögliche Wert, der von random() zurückgegeben wird, 10 ist, und n = 7. Jetzt macht n % 7 die Nummern 7, 8, 9 und 10 in 0, 1, 2, 3. Wenn also die ursprüngliche Zahl gleichmäßig verteilt ist, wird das Ergebnis stark auf die niedrigeren Zahlen ausgerichtet, da sie doppelt so häufig wie 4, 5 und 6 erscheinen. In diesem Fall geschieht dies unabhängig davon, ob n eine Potenz von zwei oder nicht, aber wenn wir statt 10 beispielsweise 15 (also 2^4-1) wählen, dann würde jede n, also eine Zweierpotenz, zu einer gleichmäßigen Verteilung führen, weil es keinen "Überschuss" geben würde "Zahlen, die am Ende des Bereichs liegen, um eine Verzerrung zu bewirken, weil die Gesamtzahl der möglichen Werte genau durch die Anzahl möglicher Reste teilbar wäre.