Stworzyłem klasę QuickRandom, której zadaniem jest szybkie tworzenie liczb losowych. To naprawdę proste: po prostu weź starą wartość, pomnóż przez a doublei weź część dziesiętną.

Oto moja QuickRandomklasa w całości:

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;
    }

}

A oto kod, który napisałem, aby go przetestować:

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);
}

Jest to bardzo prosty algorytm, który po prostu mnoży poprzednią wartość podwójną przez podwójną „magiczną liczbę”. Złożyłem to dość szybko, więc prawdopodobnie mógłbym to ulepszyć, ale dziwne, wydaje się, że działa dobrze.

Oto przykładowe dane wyjściowe zakomentowanych wierszy w mainmetodzie:

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. Całkiem losowo. W rzeczywistości działałoby to w przypadku generatora liczb losowych w grze.

Oto przykładowe dane wyjściowe części nieskomentowanej:

5456313909
1427223941

Łał! Działa prawie 4 razy szybciej niż Math.random.

Pamiętam, że czytałem gdzieś, że Math.randomużywano System.nanoTime()i mnóstwo szalonych rzeczy dotyczących modułu i podziału. Czy to naprawdę konieczne? Mój algorytm działa znacznie szybciej i wydaje się dość przypadkowy.

Mam dwa pytania:

• Czy mój algorytm „wystarczająco dobre” (o, powiedzmy, na stadionie, gdzie naprawdę liczb losowych nie są zbyt ważne)?
• Dlaczego robi Math.randomtak dużo, kiedy wydaje się, że wystarczy zwykłe pomnożenie i wycięcie ułamka dziesiętnego?

Twoja QuickRandomimplementacja nie ma tak naprawdę jednolitej dystrybucji. Częstotliwości są generalnie wyższe przy niższych wartościach, przy Math.random()bardziej równomiernym rozkładzie. Oto SSCCE, które pokazuje, że:

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));
        }
    }

}

Średni wynik wygląda następująco:

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  :###################    

Jeśli powtórzysz test, zobaczysz, że rozkład QR różni się znacznie, w zależności od początkowych nasion, podczas gdy rozkład MR jest stabilny. Czasami osiąga pożądany jednolity rozkład, ale częściej nie. Oto jeden z bardziej ekstremalnych przykładów, nawet poza granicami wykresu:

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  :                                                  

To, co opisujesz, to rodzaj generatora losowego zwanego generatorem liniowym kongruencjalnym . Generator działa w następujący sposób:

• Zacznij od wartości początkowej i mnożnika.
• Aby wygenerować liczbę losową:
  • Pomnóż ziarno przez mnożnik.
  • Ustaw ziarno równe tej wartości.
  • Zwróć tę wartość.

Ten generator ma wiele fajnych właściwości, ale jako dobre źródło losowe ma poważne problemy. Powyższy artykuł w Wikipedii opisuje niektóre z mocnych i słabych stron. Krótko mówiąc, jeśli potrzebujesz dobrych wartości losowych, prawdopodobnie nie jest to zbyt dobre podejście.

Mam nadzieję że to pomoże!

Twoja funkcja liczb losowych jest słaba, ponieważ ma zbyt mały stan wewnętrzny - liczba wyjściowa funkcji w dowolnym kroku jest całkowicie zależna od poprzedniej liczby. Na przykład, jeśli przyjmiemy, że magicNumberjest to 2 (przykładowo), to sekwencja:

0.10 -> 0.20

jest silnie odzwierciedlone przez podobne sekwencje:

0.09 -> 0.18
0.11 -> 0.22

W wielu przypadkach spowoduje to zauważalne korelacje w Twojej grze - na przykład, jeśli wykonasz kolejne wywołania funkcji w celu wygenerowania współrzędnych X i Y dla obiektów, obiekty te utworzą wyraźne ukośne wzory.

Jeśli nie masz dobrego powodu, aby sądzić, że generator liczb losowych spowalnia twoją aplikację (a jest to BARDZO mało prawdopodobne), nie ma powodu, aby próbować pisać własny.

Prawdziwym problemem jest to, że jego wyjściowy histogram jest bardzo zależny od początkowego ziarna - przez większość czasu będzie to prawie jednolity wynik, ale przez większość czasu będzie miał wyraźnie niejednolity wynik.

Zainspirowany tym artykułem o tym, jak zła jest rand()funkcja php , stworzyłem kilka losowych obrazów macierzy przy użyciu QuickRandomi System.Random. Ten przebieg pokazuje, jak czasami ziarno może mieć zły wpływ (w tym przypadku faworyzując niższe liczby), gdy System.Randomjest dość jednolite.

QuickRandom

System.Random

Nawet gorzej

Jeśli mamy zainicjować QuickRandomjak new QuickRandom(0.01, 1.03)mamy do tego pliku:

Kod

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;
        }
    }
}

Jednym z problemów z generatorem liczb losowych jest to, że nie ma `` stanu ukrytego '' - jeśli wiem, jaką liczbę losową zwróciłeś podczas ostatniego połączenia, znam każdą liczbę losową, którą wyślesz do końca czasu, ponieważ jest tylko jedna możliwy następny wynik i tak dalej i tak dalej.

Inną rzeczą do rozważenia jest „okres” generatora liczb losowych. Oczywiście przy skończonym rozmiarze stanu, równym części mantysy podwójnej, będzie w stanie zwrócić najwyżej 2 ^ 52 wartości przed zapętleniem. Ale to w najlepszym przypadku - czy możesz udowodnić, że nie ma pętli okresu 1, 2, 3, 4 ...? Jeśli tak, twój RNG będzie miał w takich przypadkach okropne, zdegenerowane zachowanie.

Ponadto, czy generowanie liczb losowych będzie miało jednolity rozkład dla wszystkich punktów początkowych? Jeśli tak się nie stanie, Twój RNG będzie stronniczy - lub, co gorsza, na różne sposoby, w zależności od początkowego ziarna.

Jeśli potrafisz odpowiedzieć na wszystkie te pytania, super. Jeśli nie możesz, to wiesz, dlaczego większość ludzi nie wymyśla koła na nowo i używa sprawdzonego generatora liczb losowych;)

(Nawiasem mówiąc, dobrym porzekadłem jest: najszybszym kodem jest kod, który nie działa. Możesz zrobić najszybszą random () na świecie, ale nie jest dobrze, jeśli nie jest zbyt losowa)

Jednym z powszechnych testów, które zawsze wykonywałem podczas tworzenia PRNG, było:

1. Konwertuj dane wyjściowe na wartości znaków
2. Wpisz wartość znaków do pliku
3. Skompresuj plik

To pozwoliło mi szybko iterować pomysły, które były „wystarczająco dobre” PRNG dla sekwencji około 1 do 20 megabajtów. Dało to również lepszy obraz z góry na dół niż tylko oglądanie go na oko, ponieważ każdy „dostatecznie dobry” PRNG z półsłowiem stanu może szybko przekroczyć zdolność twoich oczu do zobaczenia punktu cyklu.

Gdybym był naprawdę wybredny, mógłbym wziąć dobre algorytmy i przeprowadzić na nich testy DIEHARD / NIST, aby uzyskać więcej wglądu, a następnie wrócić i trochę poprawić.

Zaletą testu kompresji, w przeciwieństwie do analizy częstotliwości, jest to, że w trywialny sposób łatwo jest zbudować dobry rozkład: po prostu wyślij blok o długości 256, zawierający wszystkie znaki o wartościach od 0 do 255, i zrób to 100 000 razy. Ale ta sekwencja ma cykl o długości 256.

Wypaczony rozkład, nawet z niewielkim marginesem, powinien zostać wychwycony przez algorytm kompresji, szczególnie jeśli dasz mu wystarczającą ilość (powiedzmy 1 megabajt) sekwencji do pracy. Jeśli niektóre znaki, bigramy lub n-gramów występują częściej, algorytm kompresji może zakodować to odchylenie dystrybucji do kodów, które faworyzują częste wystąpienia z krótszymi słowami kodowymi, a otrzymasz deltę kompresji.

Ponieważ większość algorytmów kompresji jest szybkich i nie wymagają implementacji (ponieważ systemy operacyjne mają je po prostu w pobliżu), test kompresji jest bardzo przydatny do szybkiego oceniania wyniku pozytywnego / negatywnego dla PRNG, który możesz tworzyć.

Powodzenia w eksperymentach!

Och, wykonałem ten test na rng, który masz powyżej, używając następującego małego moda twojego kodu:

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));
        }
    }
}

Wyniki były następujące:

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

Uznałbym PRNG za dobry, gdyby plik wyjściowy nie mógł być w ogóle skompresowany. Szczerze mówiąc, nie sądziłem, że twój PRNG poradzi sobie tak dobrze, tylko 16% na ~ 20 Megs jest imponujące jak na tak prostą konstrukcję. Ale nadal uważam to za porażkę.

Najszybszym generatorem losowym, jaki możesz zaimplementować, jest:

XD, poza żartami, poza tym wszystkim, co tutaj zostało powiedziane, chciałbym wnieść swój wkład, powołując się na to, że testowanie losowych sekwencji „jest trudnym zadaniem” [1], a jest kilka testów, które sprawdzają pewne właściwości liczb pseudolosowych, można znaleźć wiele z nich tutaj: http://www.random.org/analysis/#2005

Jednym z prostych sposobów oceny „jakości” generatora losowego jest stary test Chi-kwadrat.

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);
}

Cytując [1]

Ideą testu χ² jest sprawdzenie, czy uzyskane liczby są rozsądnie rozłożone. Jeśli wygenerujemy N liczb dodatnich mniejszych niż r , spodziewalibyśmy się, że uzyskamy około N / r liczb dla każdej wartości. Ale - i na tym polega istota sprawy - częstości występowania wszystkich wartości nie powinny być dokładnie takie same: to nie byłoby przypadkowe!

Po prostu obliczamy sumę kwadratów częstości występowania każdej wartości, przeskalowaną przez oczekiwaną częstotliwość, a następnie odejmujemy rozmiar ciągu. Ta liczba, „statystyka χ²”, może być wyrażona matematycznie jako

Jeśli statystyka χ² jest bliska r , to liczby są losowe; jeśli jest zbyt daleko, to nie są. Pojęcia „blisko” i „daleko” można zdefiniować dokładniej: istnieją tabele, które dokładnie mówią, jak odnoszą się statystyki do właściwości ciągów losowych. W przypadku prostego testu, który wykonujemy, statystyka powinna mieścić się w granicach 2√r

Korzystając z tej teorii i następującego kodu:

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);
    }
}

Otrzymałem następujący wynik:

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

Który w przypadku QuickRandom jest daleko od r (poza r ± 2 * sqrt(r))

To powiedziawszy, QuickRandom może być szybki, ale (jak stwierdzono w innych odpowiedziach) nie jest dobry jako generator liczb losowych

[1] SEDGEWICK ROBERT, Algorithms in C , Addinson Wesley Publishing Company, 1990, strony 516 do 518

Ułożyła szybki makiety swojego algorytmu w JavaScript, aby ocenić wyniki. Generuje 100 000 losowych liczb całkowitych od 0 do 99 i śledzi wystąpienie każdej liczby całkowitej.

Pierwszą rzeczą, jaką zauważyłem, jest to, że prawdopodobieństwo uzyskania niskiej liczby jest większe niż dużej. Widzisz to najbardziej, gdy seed1jest wysoki i seed2niski. W kilku przypadkach uzyskałem tylko 3 liczby.

W najlepszym przypadku twój algorytm wymaga dopracowania.

Jeśli Math.Random()funkcja wywołuje system operacyjny w celu uzyskania godziny, nie można jej porównać z funkcją. Twoja funkcja to PRNG, podczas gdy ta funkcja dąży do uzyskania prawdziwych liczb losowych. Jabłka i pomarańcze.

Twój PRNG może być szybki, ale nie ma wystarczających informacji o stanie, aby osiągnąć długi okres, zanim się powtórzy (a jego logika nie jest wystarczająco wyrafinowana, aby osiągnąć nawet okresy, które są możliwe przy tak dużej ilości informacji o stanie).

Okres to długość sekwencji, zanim PRNG zacznie się powtarzać. Dzieje się tak, gdy tylko maszyna PRNG przechodzi do stanu, który jest identyczny z jakimś poprzednim stanem. Stamtąd powtórzy przejścia, które rozpoczęły się w tym stanie. Innym problemem związanym z PRNG może być mała liczba unikalnych sekwencji, a także zdegenerowana zbieżność w konkretnej sekwencji, która się powtarza. Mogą również występować niepożądane wzory. Na przykład przypuśćmy, że PRNG wygląda dość losowo, gdy liczby są drukowane w postaci dziesiętnej, ale sprawdzenie wartości w systemie binarnym pokazuje, że bit 4 po prostu przełącza się między 0 a 1 przy każdym wywołaniu. Ups!

Spójrz na Mersenne Twister i inne algorytmy. Istnieją sposoby na osiągnięcie równowagi między długością okresu a cyklami procesora. Jedną z podstawowych metod (stosowanych w Mersenne Twister) jest cykliczne poruszanie się po wektorze stanu. Oznacza to, że kiedy generowana jest liczba, nie jest ona oparta na całym stanie, tylko na kilku słowach z tablicy stanów podlegających kilku operacjom bitowym. Ale na każdym kroku algorytm porusza się również po tablicy, po trochu szyfrując zawartość.

Istnieje wiele, wiele generatorów liczb pseudolosowych. Na przykład ranarray Knutha , twister Mersenne lub poszukaj generatorów LFSR. Monumentalne "algorytmy seminumeryczne" Knutha analizują ten obszar i proponują pewne liniowe generatory kongruencjalne (proste w implementacji, szybkie).

Ale sugerowałbym, abyś po prostu trzymał się java.util.Randomlub Math.random, są one szybkie i przynajmniej OK do sporadycznego użytku (np. Gry i tym podobne). Jeśli jesteś paranoikiem w dystrybucji (jakiś program Monte Carlo lub algorytm genetyczny), sprawdź ich implementację (źródło jest gdzieś dostępne) i zasyp je jakąś naprawdę losową liczbą, albo z twojego systemu operacyjnego, albo z random.org . Jeśli jest to wymagane w przypadku aplikacji, w których bezpieczeństwo ma kluczowe znaczenie, będziesz musiał się kopać. I tak jak w takim przypadku nie powinniście wierzyć w to, co wylewa tutaj jakiś kolorowy kwadrat z brakującymi kawałkami, zamknę się teraz.

Jest bardzo mało prawdopodobne, aby wydajność generowania liczb losowych była problemem w każdym przypadku użycia, który wymyśliłeś, chyba że uzyskujesz dostęp do pojedynczej Randominstancji z wielu wątków (ponieważ Randomjest synchronized).

Jeśli jednak tak jest naprawdę i potrzebujesz szybko wielu liczb losowych, Twoje rozwiązanie jest zbyt niewiarygodne. Czasami daje dobre rezultaty, czasami daje okropne rezultaty (na podstawie początkowych ustawień).

Jeśli chcesz uzyskać te same liczby, które Randomdaje ci klasa, tylko szybciej, możesz pozbyć się tam synchronizacji:

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));
    }

}

Po prostu wziąłem java.util.Randomkod i usunąłem synchronizację, co daje dwukrotnie wyższą wydajność w porównaniu z oryginałem na mojej Oracle HotSpot JVM 7u9. Nadal jest wolniejszy niż twój QuickRandom, ale daje znacznie bardziej spójne wyniki. Aby być precyzyjnym, dla tych samych seedwartości i aplikacji jednowątkowych daje te same liczby pseudolosowe, co oryginalna Randomklasa.

_{Ten kod jest oparty na aktualnej wersji java.util.RandomOpenJDK 7u, która jest licencjonowana w ramach GNU GPL v2 .}

EDYCJA 10 miesięcy później:

Właśnie odkryłem, że nie musisz nawet używać mojego kodu powyżej, aby uzyskać niezsynchronizowaną Randominstancję. Jest też jeden w JDK!

Spójrz na ThreadLocalRandomklasę Java 7 . Kod wewnątrz jest prawie identyczny z moim kodem powyżej. Klasa jest po prostu Randomwersją izolowaną przez lokalne wątki, odpowiednią do szybkiego generowania liczb losowych. Jedynym minusem, jaki przychodzi mi do głowy, jest to, że nie możesz ustawić go seedręcznie.

Przykładowe użycie:

Random random = ThreadLocalRandom.current();

„Losowe” to coś więcej niż tylko zdobywanie liczb… to, co masz, jest pseudolosowe

Jeśli pseudolosowość jest wystarczająco dobra do twoich celów, to na pewno jest o wiele szybsza (a XOR + Bitshift będzie szybszy niż to, co masz)

Rolf

Edytować:

OK, po zbyt pochopnym udzieleniu odpowiedzi, pozwól mi odpowiedzieć na prawdziwy powód, dla którego twój kod jest szybszy:

Z JavaDoc dla Math.Random ()

Ta metoda jest odpowiednio zsynchronizowana, aby umożliwić prawidłowe użycie przez więcej niż jeden wątek. Jeśli jednak wiele wątków musi generować liczby pseudolosowe z dużą szybkością, może to zmniejszyć rywalizację o każdy wątek, aby mieć swój własny generator liczb pseudolosowych.

Prawdopodobnie dlatego twój kod jest szybszy.

java.util.Random niewiele różni się od podstawowego LCG opisanego przez Knutha. Jednak ma główne 2 główne zalety / różnice:

• bezpieczeństwo wątków - każda aktualizacja jest CAS, która jest droższa niż zwykły zapis i wymaga rozgałęzienia (nawet jeśli doskonale przewidziano jeden wątek). W zależności od procesora może to być znacząca różnica.
• nieujawniony stan wewnętrzny - jest to bardzo ważne w przypadku wszystkiego, co nie jest trywialne. Chcesz, aby liczby losowe nie były przewidywalne.

Poniżej znajduje się główna procedura generująca „losowe” liczby całkowite w java.util.Random.

  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));
    }

Jeśli usuniesz AtomicLong i nieujawnioną wartość (tj. Używając wszystkich bitów long), uzyskasz większą wydajność niż podwójne mnożenie / modulo.

Ostatnia uwaga: Math.randomnie powinien być używany do niczego poza prostymi testami, jest podatny na spory, a jeśli masz nawet kilka wątków wywołujących go jednocześnie, wydajność spada. Jedną mało znaną historyczną cechą tego rozwiązania jest wprowadzenie CAS w Javie - aby pokonać niesławny test porównawczy (najpierw przez IBM przez intrinsics, a potem Sun stworzył "CAS z Java")

To jest funkcja losowa, której używam w moich grach. Jest dość szybki i ma dobrą (wystarczającą) dystrybucję.

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));
       }
}