Ich habe eine Klasse namens erstellt QuickRandom, deren Aufgabe es ist, schnell Zufallszahlen zu erzeugen. Es ist ganz einfach: Nehmen Sie einfach den alten Wert, multiplizieren Sie ihn mit a doubleund nehmen Sie den Dezimalteil.

Hier ist meine QuickRandomKlasse in ihrer Gesamtheit:

public class QuickRandom {
    private double prevNum;
    private double magicNumber;

    public QuickRandom(double seed1, double seed2) {
        if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
        prevNum = seed1;
        if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
        magicNumber = seed2;
    }

    public QuickRandom() {
        this(Math.random(), Math.random() * 10);
    }

    public double random() {
        return prevNum = (prevNum*magicNumber)%1;
    }

}

Und hier ist der Code, den ich geschrieben habe, um ihn zu testen:

public static void main(String[] args) {
        QuickRandom qr = new QuickRandom();

        /*for (int i = 0; i < 20; i ++) {
            System.out.println(qr.random());
        }*/

        //Warm up
        for (int i = 0; i < 10000000; i ++) {
            Math.random();
            qr.random();
            System.nanoTime();
        }

        long oldTime;

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            Math.random();
        }
        System.out.println(System.nanoTime() - oldTime);

        oldTime = System.nanoTime();
        for (int i = 0; i < 100000000; i ++) {
            qr.random();
        }
        System.out.println(System.nanoTime() - oldTime);
}

Es ist ein sehr einfacher Algorithmus, der einfach das vorherige Doppel mit einem "magischen Zahlen" -Doppel multipliziert. Ich habe es ziemlich schnell zusammengeschmissen, also könnte ich es wahrscheinlich besser machen, aber seltsamerweise scheint es gut zu funktionieren.

Dies ist eine Beispielausgabe der auskommentierten Zeilen in der mainMethode:

0.612201846732229
0.5823974655091941
0.31062451498865684
0.8324473610354004
0.5907187526770246
0.38650264675748947
0.5243464344127049
0.7812828761272188
0.12417247811074805
0.1322738256858378
0.20614642573072284
0.8797579436677381
0.022122999476108518
0.2017298328387873
0.8394849894162446
0.6548917685640614
0.971667953190428
0.8602096647696964
0.8438709031160894
0.694884972852229

Hm. Ziemlich zufällig. Tatsächlich würde das für einen Zufallszahlengenerator in einem Spiel funktionieren.

Hier ist eine Beispielausgabe des nicht auskommentierten Teils:

5456313909
1427223941

Beeindruckend! Es arbeitet fast viermal schneller als Math.random.

Ich erinnere mich, dass ich irgendwo etwas gelesen habe, das Math.randomgebraucht wurde, System.nanoTime()und jede Menge verrücktes Modul- und Teilungsmaterial. Ist das wirklich notwendig? Mein Algorithmus arbeitet viel schneller und scheint ziemlich zufällig zu sein.

Ich habe zwei Fragen:

• Ist mein Algorithmus „gut genug“ (für, sagen wir, ein Spiel, wo wirklich zufällige Zahlen sind nicht so wichtig)?
• Warum macht Math.randomman so viel, wenn es so aussieht, als würde eine einfache Multiplikation und das Ausschneiden der Dezimalstelle ausreichen?

Ihre QuickRandomImplementierung ist nicht wirklich gleichmäßig verteilt. Die Frequenzen sind im Allgemeinen bei den niedrigeren Werten höher, während Math.random()sie eine gleichmäßigere Verteilung aufweisen. Hier ist eine SSCCE, die das zeigt:

package com.stackoverflow.q14491966;

import java.util.Arrays;

public class Test {

    public static void main(String[] args) throws Exception {
        QuickRandom qr = new QuickRandom();
        int[] frequencies = new int[10];
        for (int i = 0; i < 100000; i++) {
            frequencies[(int) (qr.random() * 10)]++;
        }
        printDistribution("QR", frequencies);

        frequencies = new int[10];
        for (int i = 0; i < 100000; i++) {
            frequencies[(int) (Math.random() * 10)]++;
        }
        printDistribution("MR", frequencies);
    }

    public static void printDistribution(String name, int[] frequencies) {
        System.out.printf("%n%s distribution |8000     |9000     |10000    |11000    |12000%n", name);
        for (int i = 0; i < 10; i++) {
            char[] bar = "                                                  ".toCharArray(); // 50 chars.
            Arrays.fill(bar, 0, Math.max(0, Math.min(50, frequencies[i] / 100 - 80)), '#');
            System.out.printf("0.%dxxx: %6d  :%s%n", i, frequencies[i], new String(bar));
        }
    }

}

Das durchschnittliche Ergebnis sieht folgendermaßen aus:

QR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  11376  :#################################                 
0.1xxx:  11178  :###############################                   
0.2xxx:  11312  :#################################                 
0.3xxx:  10809  :############################                      
0.4xxx:  10242  :######################                            
0.5xxx:   8860  :########                                          
0.6xxx:   9004  :##########                                        
0.7xxx:   8987  :#########                                         
0.8xxx:   9075  :##########                                        
0.9xxx:   9157  :###########                                       

MR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  10097  :####################                              
0.1xxx:   9901  :###################                               
0.2xxx:  10018  :####################                              
0.3xxx:   9956  :###################                               
0.4xxx:   9974  :###################                               
0.5xxx:  10007  :####################                              
0.6xxx:  10136  :#####################                             
0.7xxx:   9937  :###################                               
0.8xxx:  10029  :####################                              
0.9xxx:   9945  :###################    

Wenn Sie den Test wiederholen, werden Sie feststellen, dass die QR-Verteilung abhängig von den anfänglichen Samen stark variiert, während die MR-Verteilung stabil ist. Manchmal erreicht es die gewünschte Gleichverteilung, aber mehr als oft nicht. Hier ist eines der extremeren Beispiele, es geht sogar über die Grenzen des Diagramms hinaus:

QR distribution |8000     |9000     |10000    |11000    |12000
0.0xxx:  41788  :##################################################
0.1xxx:  17495  :##################################################
0.2xxx:  10285  :######################                            
0.3xxx:   7273  :                                                  
0.4xxx:   5643  :                                                  
0.5xxx:   4608  :                                                  
0.6xxx:   3907  :                                                  
0.7xxx:   3350  :                                                  
0.8xxx:   2999  :                                                  
0.9xxx:   2652  :                                                  

Was Sie beschreiben, ist eine Art Zufallsgenerator, der als linearer Kongruenzgenerator bezeichnet wird . Der Generator arbeitet wie folgt:

• Beginnen Sie mit einem Startwert und einem Multiplikator.
• So generieren Sie eine Zufallszahl:
  • Multiplizieren Sie den Startwert mit dem Multiplikator.
  • Setzen Sie den Startwert auf diesen Wert.
  • Geben Sie diesen Wert zurück.

Dieser Generator hat viele schöne Eigenschaften, hat aber als gute Zufallsquelle erhebliche Probleme. Der oben verlinkte Wikipedia-Artikel beschreibt einige der Stärken und Schwächen. Kurz gesagt, wenn Sie gute Zufallswerte benötigen, ist dies wahrscheinlich kein sehr guter Ansatz.

Hoffe das hilft!

Ihre Zufallszahlenfunktion ist schlecht, da sie einen zu geringen internen Status aufweist. Die von der Funktion in einem bestimmten Schritt ausgegebene Zahl hängt vollständig von der vorherigen Zahl ab. Wenn wir zum Beispiel annehmen, dass dies magicNumber2 ist (als Beispiel), dann ist die Sequenz:

0.10 -> 0.20

wird stark durch ähnliche Sequenzen gespiegelt:

0.09 -> 0.18
0.11 -> 0.22

In vielen Fällen führt dies zu merklichen Korrelationen in Ihrem Spiel. Wenn Sie beispielsweise Ihre Funktion nacheinander aufrufen, um X- und Y-Koordinaten für Objekte zu generieren, bilden die Objekte klare diagonale Muster.

Wenn Sie keinen guten Grund zu der Annahme haben, dass der Zufallszahlengenerator Ihre Anwendung verlangsamt (und dies ist SEHR unwahrscheinlich), gibt es keinen guten Grund, Ihre eigene zu schreiben.

Das eigentliche Problem dabei ist, dass das Ausgabehistogramm viel zu stark vom Ausgangswert abhängt - die meiste Zeit wird es eine nahezu gleichmäßige Ausgabe haben, aber die meiste Zeit wird eine deutlich ungleichmäßige Ausgabe vorliegen.

Inspiriert von diesem Artikel darüber, wie schlecht die rand()Funktion von PHP ist , habe ich einige zufällige Matrixbilder mit QuickRandomund erstellt System.Random. Dieser Lauf zeigt, wie manchmal der Samen einen schlechten Effekt haben kann (in diesem Fall zugunsten niedrigerer Zahlen), wenn dies System.Randomziemlich gleichmäßig ist.

QuickRandom

System.Random

Noch schlimmer

Wenn wir initialisieren, QuickRandomwährend new QuickRandom(0.01, 1.03)wir dieses Bild erhalten:

Der Code

using System;
using System.Drawing;
using System.Drawing.Imaging;

namespace QuickRandomTest
{
    public class QuickRandom
    {
        private double prevNum;
        private readonly double magicNumber;

        private static readonly Random rand = new Random();

        public QuickRandom(double seed1, double seed2)
        {
            if (seed1 >= 1 || seed1 < 0) throw new ArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
            prevNum = seed1;
            if (seed2 <= 1 || seed2 > 10) throw new ArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
            magicNumber = seed2;
        }

        public QuickRandom()
            : this(rand.NextDouble(), rand.NextDouble() * 10)
        {
        }

        public double Random()
        {
            return prevNum = (prevNum * magicNumber) % 1;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var rand = new Random();
            var qrand = new QuickRandom();
            int w = 600;
            int h = 600;
            CreateMatrix(w, h, rand.NextDouble).Save("System.Random.png", ImageFormat.Png);
            CreateMatrix(w, h, qrand.Random).Save("QuickRandom.png", ImageFormat.Png);
        }

        private static Image CreateMatrix(int width, int height, Func<double> f)
        {
            var bitmap = new Bitmap(width, height);
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++) {
                    var c = (int) (f()*255);
                    bitmap.SetPixel(x, y, Color.FromArgb(c,c,c));
                }
            }

            return bitmap;
        }
    }
}

Ein Problem mit Ihrem Zufallszahlengenerator ist, dass es keinen "versteckten Zustand" gibt. Wenn ich weiß, welche Zufallszahl Sie beim letzten Anruf zurückgegeben haben, kenne ich jede einzelne Zufallszahl, die Sie bis zum Ende der Zeit senden, da es nur eine gibt mögliches nächstes Ergebnis und so weiter und so fort.

Eine andere zu berücksichtigende Sache ist die "Periode" Ihres Zufallszahlengenerators. Offensichtlich kann bei einer endlichen Zustandsgröße, die dem Mantissenanteil eines Doppels entspricht, vor dem Schleifen nur höchstens 2 ^ 52 Werte zurückgegeben werden. Aber das ist im besten Fall - können Sie beweisen, dass es keine Schleifen der Periode 1, 2, 3, 4 gibt ...? Wenn dies der Fall ist, hat Ihr RNG in diesen Fällen ein schreckliches, entartetes Verhalten.

Wird Ihre Zufallszahlengenerierung außerdem für alle Startpunkte gleichmäßig verteilt sein? Wenn dies nicht der Fall ist, ist Ihr RNG voreingenommen - oder schlimmer noch, je nach Startsamen auf unterschiedliche Weise voreingenommen.

Wenn Sie all diese Fragen beantworten können, ist das großartig. Wenn Sie nicht können, dann wissen Sie, warum die meisten Leute das Rad nicht neu erfinden und einen bewährten Zufallszahlengenerator verwenden;)

(Ein gutes Sprichwort lautet übrigens: Der schnellste Code ist Code, der nicht ausgeführt wird. Sie könnten den schnellsten Zufall () der Welt erstellen, aber es ist nicht gut, wenn er nicht sehr zufällig ist.)

Ein häufiger Test, den ich bei der Entwicklung von PRNGs immer durchgeführt habe, war:

1. Konvertieren Sie die Ausgabe in Zeichenwerte
2. Schreiben Sie einen Zeichenwert in eine Datei
3. Datei komprimieren

Auf diese Weise konnte ich schnell Ideen wiederholen, die PRNGs für Sequenzen von etwa 1 bis 20 Megabyte "gut genug" waren. Es ergab auch ein besseres Bild von oben nach unten, als es nur mit dem Auge zu untersuchen, da jedes "gut genug" PRNG mit einem halben Wort Zustand die Fähigkeit Ihrer Augen, den Zykluspunkt zu sehen, schnell überschreiten könnte.

Wenn ich wirklich wählerisch wäre, könnte ich die guten Algorithmen verwenden und die DIEHARD / NIST-Tests für sie ausführen, um einen besseren Einblick zu erhalten, und dann zurückgehen und weitere Optimierungen vornehmen.

Der Vorteil des Komprimierungstests im Gegensatz zu einer Frequenzanalyse besteht darin, dass es trivial einfach ist, eine gute Verteilung zu erstellen: Geben Sie einfach einen Block mit 256 Längen aus, der alle Zeichen mit den Werten 0 bis 255 enthält, und führen Sie dies 100.000 Mal durch. Diese Sequenz hat jedoch einen Zyklus mit einer Länge von 256.

Eine verzerrte Verteilung, auch mit einem kleinen Rand, sollte von einem Komprimierungsalgorithmus erfasst werden, insbesondere wenn Sie genug (z. B. 1 Megabyte) der Sequenz angeben, um damit zu arbeiten. Wenn einige Zeichen, Bigramme oder n-Gramme häufiger auftreten, kann ein Komprimierungsalgorithmus diesen Verteilungsversatz in Codes codieren, die das häufige Auftreten mit kürzeren Codewörtern begünstigen, und Sie erhalten ein Delta der Komprimierung.

Da die meisten Komprimierungsalgorithmen schnell sind und keine Implementierung erfordern (da sie von Betriebssystemen nur herumliegen), ist der Komprimierungstest sehr nützlich, um ein PRNG, das Sie möglicherweise entwickeln, schnell zu bewerten.

Viel Glück bei Ihren Experimenten!

Oh, ich habe diesen Test mit dem oben genannten Rng durchgeführt und dabei den folgenden kleinen Mod Ihres Codes verwendet:

import java.io.*;

public class QuickRandom {
    private double prevNum;
    private double magicNumber;

    public QuickRandom(double seed1, double seed2) {
        if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1);
        prevNum = seed1;
        if (seed2 <= 1 || seed2 > 10) throw new IllegalArgumentException("Seed 2 must be > 1 and <= 10, not " + seed2);
        magicNumber = seed2;
    }

    public QuickRandom() {
        this(Math.random(), Math.random() * 10);
    }

    public double random() {
        return prevNum = (prevNum*magicNumber)%1;
    }

    public static void main(String[] args) throws Exception {
        QuickRandom qr = new QuickRandom();
        FileOutputStream fout = new FileOutputStream("qr20M.bin");

        for (int i = 0; i < 20000000; i ++) {
            fout.write((char)(qr.random()*256));
        }
    }
}

Die Ergebnisse waren:

Cris-Mac-Book-2:rt cris$ zip -9 qr20M.zip qr20M.bin2
adding: qr20M.bin2 (deflated 16%)
Cris-Mac-Book-2:rt cris$ ls -al
total 104400
drwxr-xr-x   8 cris  staff       272 Jan 25 05:09 .
drwxr-xr-x+ 48 cris  staff      1632 Jan 25 05:04 ..
-rw-r--r--   1 cris  staff      1243 Jan 25 04:54 QuickRandom.class
-rw-r--r--   1 cris  staff       883 Jan 25 05:04 QuickRandom.java
-rw-r--r--   1 cris  staff  16717260 Jan 25 04:55 qr20M.bin.gz
-rw-r--r--   1 cris  staff  20000000 Jan 25 05:07 qr20M.bin2
-rw-r--r--   1 cris  staff  16717402 Jan 25 05:09 qr20M.zip

Ich würde ein PRNG für gut halten, wenn die Ausgabedatei überhaupt nicht komprimiert werden könnte. Um ehrlich zu sein, ich dachte nicht, dass Ihr PRNG so gut abschneiden würde, nur 16% auf ~ 20 Megs sind für eine so einfache Konstruktion ziemlich beeindruckend. Aber ich halte es immer noch für einen Fehlschlag.

Der schnellste Zufallsgenerator, den Sie implementieren können, ist folgender:

XD, Witze auseinander, neben allem, was hier gesagt wird, möchte ich dazu beitragen, dass das Testen von Zufallssequenzen "eine schwierige Aufgabe" ist [1], und es gibt mehrere Tests, die bestimmte Eigenschaften von Pseudozufallszahlen überprüfen Viele davon hier: http://www.random.org/analysis/#2005

Eine einfache Möglichkeit, die "Qualität" des Zufallsgenerators zu bewerten, ist der alte Chi-Quadrat-Test.

static double chisquare(int numberCount, int maxRandomNumber) {
    long[] f = new long[maxRandomNumber];
    for (long i = 0; i < numberCount; i++) {
        f[randomint(maxRandomNumber)]++;
    }

    long t = 0;
    for (int i = 0; i < maxRandomNumber; i++) {
        t += f[i] * f[i];
    }
    return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount);
}

Zitieren [1]

Mit dem χ²-Test soll überprüft werden, ob die produzierten Zahlen angemessen verteilt sind oder nicht. Wenn wir N positive Zahlen kleiner als r erzeugen , erwarten wir ungefähr N / r Zahlen für jeden Wert. Aber - und das ist die Essenz der Sache - die Häufigkeit des Auftretens aller Werte sollte nicht genau gleich sein: das wäre nicht zufällig!

Wir berechnen einfach die Summe der Quadrate der Häufigkeit des Auftretens jedes Werts, skaliert mit der erwarteten Häufigkeit, und subtrahieren dann die Größe der Sequenz. Diese Zahl, die "χ²-Statistik", kann mathematisch ausgedrückt werden als

Wenn die χ²-Statistik nahe an r liegt , sind die Zahlen zufällig; Wenn es zu weit weg ist, sind sie es nicht. Die Begriffe "nah" und "weit weg" können genauer definiert werden: Es gibt Tabellen, die genau angeben, wie sich die Statistik auf Eigenschaften von Zufallssequenzen bezieht. Für den einfachen Test, den wir durchführen, sollte die Statistik innerhalb von 2√r liegen

Verwenden Sie diese Theorie und den folgenden Code:

abstract class RandomFunction {
    public abstract int randomint(int range); 
}

public class test {
    static QuickRandom qr = new QuickRandom();

    static double chisquare(int numberCount, int maxRandomNumber, RandomFunction function) {
        long[] f = new long[maxRandomNumber];
        for (long i = 0; i < numberCount; i++) {
            f[function.randomint(maxRandomNumber)]++;
        }

        long t = 0;
        for (int i = 0; i < maxRandomNumber; i++) {
            t += f[i] * f[i];
        }
        return (((double) maxRandomNumber * t) / numberCount) - (double) (numberCount);
    }

    public static void main(String[] args) {
        final int ITERATION_COUNT = 1000;
        final int N = 5000000;
        final int R = 100000;

        double total = 0.0;
        RandomFunction qrRandomInt = new RandomFunction() {
            @Override
            public int randomint(int range) {
                return (int) (qr.random() * range);
            }
        }; 
        for (int i = 0; i < ITERATION_COUNT; i++) {
            total += chisquare(N, R, qrRandomInt);
        }
        System.out.printf("Ave Chi2 for QR: %f \n", total / ITERATION_COUNT);        

        total = 0.0;
        RandomFunction mathRandomInt = new RandomFunction() {
            @Override
            public int randomint(int range) {
                return (int) (Math.random() * range);
            }
        };         
        for (int i = 0; i < ITERATION_COUNT; i++) {
            total += chisquare(N, R, mathRandomInt);
        }
        System.out.printf("Ave Chi2 for Math.random: %f \n", total / ITERATION_COUNT);
    }
}

Ich habe folgendes Ergebnis erhalten:

Ave Chi2 for QR: 108965,078640
Ave Chi2 for Math.random: 99988,629040

Was für QuickRandom weit entfernt von r (außerhalb von r ± 2 * sqrt(r)) ist

Das heißt, QuickRandom könnte schnell sein, ist aber (wie in anderen Antworten angegeben) nicht gut als Zufallszahlengenerator

[1] SEDGEWICK ROBERT, Algorithmen in C , Addinson Wesley Publishing Company, 1990, Seiten 516 bis 518

Ich habe ein kurzes Modell Ihres Algorithmus in JavaScript zusammengestellt, um die Ergebnisse auszuwerten. Es generiert 100.000 zufällige Ganzzahlen von 0 bis 99 und verfolgt die Instanz jeder Ganzzahl.

Das erste, was mir auffällt, ist, dass Sie eher eine niedrige als eine hohe Zahl erhalten. Sie sehen dies am meisten, wenn seed1es hoch und seed2niedrig ist. In einigen Fällen habe ich nur 3 Zahlen erhalten.

Bestenfalls muss Ihr Algorithmus etwas verfeinert werden.

Wenn die Math.Random()Funktion das Betriebssystem aufruft, um die Uhrzeit abzurufen, können Sie sie nicht mit Ihrer Funktion vergleichen. Ihre Funktion ist ein PRNG, während diese Funktion nach echten Zufallszahlen strebt. Äpfel und Orangen.

Ihr PRNG ist zwar schnell, verfügt jedoch nicht über genügend Statusinformationen, um einen langen Zeitraum zu erreichen, bevor es wiederholt wird (und seine Logik ist nicht ausgefeilt genug, um auch nur die Zeiträume zu erreichen, die mit so vielen Statusinformationen möglich sind).

Punkt ist die Länge der Sequenz, bevor sich Ihr PRNG zu wiederholen beginnt. Dies geschieht, sobald die PRNG-Maschine einen Zustandsübergang in einen Zustand durchführt, der mit einem früheren Zustand identisch ist. Von dort aus werden die Übergänge wiederholt, die in diesem Zustand begonnen haben. Ein weiteres Problem bei PRNGs kann eine geringe Anzahl eindeutiger Sequenzen sowie eine entartete Konvergenz bei einer bestimmten Sequenz sein, die sich wiederholt. Es kann auch unerwünschte Muster geben. Angenommen, ein PRNG sieht ziemlich zufällig aus, wenn die Zahlen dezimal gedruckt werden. Eine Überprüfung der binären Werte zeigt jedoch, dass Bit 4 bei jedem Aufruf einfach zwischen 0 und 1 wechselt. Hoppla!

Schauen Sie sich den Mersenne Twister und andere Algorithmen an. Es gibt Möglichkeiten, ein Gleichgewicht zwischen der Periodenlänge und den CPU-Zyklen herzustellen. Ein grundlegender Ansatz (der im Mersenne Twister verwendet wird) besteht darin, im Zustandsvektor herumzulaufen. Das heißt, wenn eine Zahl erzeugt wird, basiert sie nicht auf dem gesamten Zustand, sondern nur auf einigen Wörtern aus dem Zustandsarray, die einigen Bitoperationen unterliegen. Bei jedem Schritt bewegt sich der Algorithmus jedoch auch im Array und verschlüsselt den Inhalt jeweils ein wenig.

Es gibt viele, viele Pseudozufallszahlengeneratoren. Zum Beispiel Knuths Ranarray , der Mersenne-Twister , oder suchen Sie nach LFSR-Generatoren. Knuths monumentale "Seminumerische Algorithmen" analysieren das Gebiet und schlagen einige lineare Kongruenzgeneratoren vor (einfach zu implementieren, schnell).

Aber ich würde vorschlagen, dass Sie sich einfach an java.util.Randomoder halten Math.random, sie sind schnell und zumindest für den gelegentlichen Gebrauch in Ordnung (dh Spiele und dergleichen). Wenn Sie in der Distribution nur paranoid sind (ein Monte-Carlo-Programm oder ein genetischer Algorithmus), überprüfen Sie deren Implementierung (Quelle ist irgendwo verfügbar) und geben Sie ihnen eine wirklich zufällige Zahl, entweder von Ihrem Betriebssystem oder von random.org . Wenn dies für eine Anwendung erforderlich ist, bei der die Sicherheit von entscheidender Bedeutung ist, müssen Sie sich selbst ausgraben. Und da Sie in diesem Fall nicht glauben sollten, was für ein farbiges Quadrat mit fehlenden Bits hier herausspritzt, werde ich jetzt die Klappe halten.

Es ist sehr unwahrscheinlich, dass die Leistung bei der Zufallszahlengenerierung für einen von Ihnen entwickelten Anwendungsfall ein Problem darstellt, es sei denn, Sie greifen Randomüber mehrere Threads auf eine einzelne Instanz zu (weil dies der Fall Randomist synchronized).

Wenn dies jedoch wirklich der Fall ist und Sie schnell viele Zufallszahlen benötigen, ist Ihre Lösung viel zu unzuverlässig. Manchmal liefert es gute Ergebnisse, manchmal liefert es schreckliche Ergebnisse (basierend auf den Anfangseinstellungen).

Wenn Sie die gleichen Zahlen möchten, die RandomIhnen die Klasse nur schneller gibt, können Sie die Synchronisation dort entfernen:

public class QuickRandom {

    private long seed;

    private static final long MULTIPLIER = 0x5DEECE66DL;
    private static final long ADDEND = 0xBL;
    private static final long MASK = (1L << 48) - 1;

    public QuickRandom() {
        this((8682522807148012L * 181783497276652981L) ^ System.nanoTime());
    }

    public QuickRandom(long seed) {
        this.seed = (seed ^ MULTIPLIER) & MASK;
    }

    public double nextDouble() {
        return (((long)(next(26)) << 27) + next(27)) / (double)(1L << 53);
    }

    private int next(int bits) {
        seed = (seed * MULTIPLIER + ADDEND) & MASK;
        return (int)(seed >>> (48 - bits));
    }

}

Ich habe einfach den java.util.RandomCode genommen und die Synchronisation entfernt, was zu einer doppelten Leistung im Vergleich zum Original auf meinem Oracle HotSpot JVM 7u9 führt. Es ist immer noch langsamer als Ihr QuickRandom, aber es liefert viel konsistentere Ergebnisse. Um genau zu sein, gibt es für dieselben seedWerte und Single-Threaded-Anwendungen dieselben Pseudozufallszahlen wie für die ursprüngliche RandomKlasse.

_{Dieser Code basiert auf dem aktuellen Code java.util.Randomin OpenJDK 7u, der unter GNU GPL v2 lizenziert ist .}

BEARBEITEN 10 Monate später:

Ich habe gerade festgestellt, dass Sie nicht einmal meinen obigen Code verwenden müssen, um eine nicht synchronisierte RandomInstanz zu erhalten. Es gibt auch eine im JDK!

Schauen Sie sich die ThreadLocalRandomKlasse von Java 7 an . Der darin enthaltene Code ist fast identisch mit meinem obigen Code. Die Klasse ist einfach eine vom lokalen Thread isolierte RandomVersion, die zum schnellen Generieren von Zufallszahlen geeignet ist. Der einzige Nachteil, den ich mir vorstellen kann, ist, dass Sie ihn nicht seedmanuell einstellen können .

Anwendungsbeispiel:

Random random = ThreadLocalRandom.current();

Bei 'Random' geht es nicht nur darum, Zahlen zu erhalten. Was Sie haben, ist pseudozufällig

Wenn Pseudozufällig für Ihre Zwecke gut genug ist, ist es sicher viel schneller (und XOR + Bitshift ist schneller als das, was Sie haben).

Rolf

Bearbeiten:

OK, nachdem ich in dieser Antwort zu voreilig war, möchte ich den wahren Grund beantworten, warum Ihr Code schneller ist:

Aus dem JavaDoc für Math.Random ()

Diese Methode ist ordnungsgemäß synchronisiert, um die korrekte Verwendung durch mehr als einen Thread zu ermöglichen. Wenn jedoch viele Threads Pseudozufallszahlen mit einer hohen Rate generieren müssen, kann dies die Konkurrenz für jeden Thread verringern, einen eigenen Pseudozufallszahlengenerator zu haben.

Dies ist wahrscheinlich der Grund, warum Ihr Code schneller ist.

java.util.Random ist nicht viel anders, eine von Knuth beschriebene grundlegende LCG. Es hat jedoch zwei Hauptvorteile / -unterschiede:

• Thread-sicher - Jedes Update ist ein CAS, das teurer als ein einfaches Schreiben ist und eine Verzweigung benötigt (selbst wenn es perfekt vorhergesagt ist). Je nach CPU kann es sich um einen signifikanten Unterschied handeln.
• Unbekannter interner Zustand - dies ist sehr wichtig für alles, was nicht trivial ist. Sie möchten, dass die Zufallszahlen nicht vorhersehbar sind.

Unten ist es die Hauptroutine, die 'zufällige' Ganzzahlen in java.util.Random generiert.

  protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
          oldseed = seed.get();
          nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

Wenn Sie AtomicLong und den nicht genannten Status entfernen (dh alle Bits von verwenden long), erhalten Sie mehr Leistung als bei der doppelten Multiplikation / Modulo.

Letzte Anmerkung: Math.randomSollte nur für einfache Tests verwendet werden, ist es anfällig für Konflikte, und wenn Sie sogar ein paar Threads haben, die es gleichzeitig aufrufen, verschlechtert sich die Leistung. Ein wenig bekanntes historisches Merkmal ist die Einführung von CAS in Java - um einen berüchtigten Benchmark zu übertreffen (zuerst von IBM über Intrinsics und dann von Sun über "CAS from Java").

Dies ist die Zufallsfunktion, die ich für meine Spiele verwende. Es ist ziemlich schnell und hat eine gute (ausreichende) Verteilung.

public class FastRandom {

    public static int randSeed;

      public static final int random()
      {
        // this makes a 'nod' to being potentially called from multiple threads
        int seed = randSeed;

        seed    *= 1103515245;
        seed    += 12345;
        randSeed = seed;
        return seed;
      }

      public static final int random(int range)
      {
        return ((random()>>>15) * range) >>> 17;
      }

      public static final boolean randomBoolean()
      {
         return random() > 0;
      }

       public static final float randomFloat()
       {
         return (random()>>>8) * (1.f/(1<<24));
       }

       public static final double randomDouble() {
           return (random()>>>8) * (1.0/(1<<24));
       }
}