Saya membuat kelas yang dipanggil QuickRandom, dan tugasnya adalah menghasilkan angka acak dengan cepat. Ini sangat sederhana: ambil saja nilai lama, kalikan dengan double, dan ambil bagian desimal.

Inilah QuickRandomkelas saya secara keseluruhan:

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

}

Dan ini kode yang saya tulis untuk mengujinya:

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

Ini adalah algoritma yang sangat sederhana yang hanya mengalikan ganda sebelumnya dengan "angka ajaib" ganda. Saya melemparkannya bersama dengan cukup cepat, jadi saya mungkin bisa membuatnya lebih baik, tetapi anehnya, itu sepertinya berfungsi dengan baik.

Ini adalah contoh keluaran dari baris komentar dalam mainmetode:

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 Cukup acak. Bahkan, itu akan bekerja untuk generator angka acak dalam game.

Berikut adalah contoh output dari bagian yang tidak dikomentari:

5456313909
1427223941

Wow! Ia melakukan hampir 4 kali lebih cepat daripada Math.random.

Saya ingat pernah membaca di suatu tempat yang Math.randomdigunakan System.nanoTime()dan banyak modulus dan hal-hal divisi gila. Apakah itu benar-benar perlu? Algoritma saya bekerja jauh lebih cepat dan sepertinya cukup acak.

Saya punya dua pertanyaan:

• Apakah algoritma saya "cukup baik" (untuk, mengatakan, permainan, di mana benar-benar nomor acak yang tidak terlalu penting)?
• Mengapa Math.randommelakukan begitu banyak ketika tampaknya hanya perkalian sederhana dan memotong desimal sudah cukup?

QuickRandomImplementasi Anda belum benar-benar distribusi yang seragam. Frekuensi umumnya lebih tinggi pada nilai yang lebih rendah sementara Math.random()memiliki distribusi yang lebih seragam. Inilah SSCCE yang menunjukkan bahwa:

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

}

Hasil rata-rata terlihat seperti ini:

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

Jika Anda mengulang tes, Anda akan melihat bahwa distribusi QR sangat bervariasi, tergantung pada benih awal, sementara distribusi MR stabil. Kadang-kadang mencapai distribusi seragam yang diinginkan, tetapi lebih sering tidak. Inilah salah satu contoh yang lebih ekstrem, bahkan di luar batas grafik:

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  :                                                  

Apa yang Anda gambarkan adalah jenis generator acak yang disebut generator kongruensial linier . Generator bekerja sebagai berikut:

• Mulai dengan nilai seed dan multiplier.
• Untuk menghasilkan angka acak:
  • Lipat gandakan benih dengan pengganda.
  • Atur seed sama dengan nilai ini.
  • Kembalikan nilai ini.

Generator ini memiliki banyak sifat yang bagus, tetapi memiliki masalah signifikan sebagai sumber acak yang baik. Artikel Wikipedia yang tertaut di atas menjelaskan beberapa kekuatan dan kelemahan. Singkatnya, jika Anda membutuhkan nilai acak yang baik, ini mungkin bukan pendekatan yang sangat baik.

Semoga ini membantu!

Fungsi angka acak Anda buruk, karena memiliki status internal terlalu sedikit - angka yang dihasilkan oleh fungsi pada setiap langkah yang diberikan sepenuhnya tergantung pada angka sebelumnya. Misalnya, jika kita asumsikan magicNumber2 (dengan contoh), maka urutannya:

0.10 -> 0.20

sangat dicerminkan oleh urutan yang sama:

0.09 -> 0.18
0.11 -> 0.22

Dalam banyak kasus, ini akan menghasilkan korelasi yang nyata dalam permainan Anda - misalnya, jika Anda membuat panggilan berturut-turut ke fungsi Anda untuk menghasilkan koordinat X dan Y untuk objek, objek akan membentuk pola diagonal yang jelas.

Kecuali Anda memiliki alasan yang kuat untuk percaya bahwa penghasil angka acak memperlambat aplikasi Anda (dan ini SANGAT tidak mungkin), tidak ada alasan bagus untuk mencoba dan menulis sendiri.

Masalah sebenarnya dengan hal ini adalah bahwa histogram outputnya tergantung pada seed awal yang jauh ke banyak - sebagian besar waktu akan berakhir dengan output yang seragam dekat tetapi banyak waktu akan memiliki output yang jelas tidak seragam.

Terinspirasi oleh artikel ini tentang betapa buruknya rand()fungsi php , saya membuat beberapa gambar matriks acak menggunakan QuickRandomdan System.Random. Proses ini menunjukkan bagaimana kadang-kadang benih dapat memiliki efek buruk (dalam hal ini mendukung angka yang lebih rendah) di mana seperti System.Randomcukup seragam.

QuickRandom

System.Random

Lebih buruk lagi

Jika kami menginisialisasi QuickRandomsaat new QuickRandom(0.01, 1.03)kami mendapatkan gambar ini:

Kode

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

Satu masalah dengan generator nomor acak Anda adalah bahwa tidak ada 'keadaan tersembunyi' - jika saya tahu nomor acak apa yang Anda kembalikan pada panggilan terakhir, saya tahu setiap nomor acak tunggal yang akan Anda kirim sampai akhir waktu, karena hanya ada satu mungkin hasil selanjutnya, dan seterusnya dan seterusnya.

Hal lain yang perlu dipertimbangkan adalah 'periode' generator nomor acak Anda. Jelas dengan ukuran keadaan terbatas, sama dengan bagian mantissa dari suatu ganda, itu hanya akan dapat mengembalikan paling banyak 2 ^ 52 nilai sebelum perulangan. Tapi itu dalam kasus terbaik - dapatkah Anda membuktikan bahwa tidak ada loop periode 1, 2, 3, 4 ...? Jika ada, RNG Anda akan memiliki perilaku yang buruk dan merosot dalam kasus-kasus itu.

Selain itu, akankah pembangkitan angka acak Anda memiliki distribusi yang seragam untuk semua titik awal? Jika tidak, maka RNG Anda akan menjadi bias - atau lebih buruk, bias dengan cara yang berbeda tergantung pada benih awal.

Jika Anda bisa menjawab semua pertanyaan ini, luar biasa. Jika Anda tidak bisa, maka Anda tahu mengapa kebanyakan orang tidak menemukan kembali roda dan menggunakan generator nomor acak yang terbukti;)

(Omong-omong, pepatah yang baik adalah: Kode tercepat adalah kode yang tidak berjalan. Anda bisa membuat acak tercepat () di dunia, tetapi tidak baik jika tidak terlalu acak)

Satu tes umum yang selalu saya lakukan ketika mengembangkan PRNG adalah untuk:

1. Konversi output ke nilai char
2. Tulis nilai karakter ke file
3. File kompres

Ini biarkan saya dengan cepat beralih pada ide-ide yang "cukup baik" PRNG untuk urutan sekitar 1 hingga 20 megabyte. Ini juga memberikan gambar top down yang lebih baik daripada hanya memeriksanya dengan mata, karena setiap PRNG "cukup baik" dengan setengah kata negara dapat dengan cepat melebihi kemampuan mata Anda untuk melihat titik siklus.

Jika saya benar-benar pilih-pilih, saya mungkin mengambil algoritma yang baik dan menjalankan tes DIEHARD / NIST pada mereka, untuk mendapatkan lebih banyak wawasan, dan kemudian kembali dan tweak lagi.

Keuntungan dari tes kompresi, yang bertentangan dengan analisis frekuensi adalah bahwa, pada dasarnya mudah untuk membangun distribusi yang baik: cukup output blok panjang 256 yang berisi semua karakter nilai 0 - 255, dan lakukan ini 100.000 kali. Tetapi urutan ini memiliki siklus panjang 256.

Distribusi miring, bahkan dengan margin kecil, harus diambil oleh algoritma kompresi, terutama jika Anda memberikannya cukup (katakanlah 1 megabyte) dari urutan untuk bekerja dengannya. Jika beberapa karakter, atau bigrams, atau n-gram lebih sering terjadi, suatu algoritma kompresi dapat menyandikan kemiringan distribusi ini ke kode-kode yang mendukung kejadian yang sering terjadi dengan kata-kata kode yang lebih pendek, dan Anda mendapatkan delta kompresi.

Karena sebagian besar algoritma kompresi cepat, dan mereka tidak memerlukan implementasi (seperti OS hanya berbaring di sekitar), tes kompresi adalah yang sangat berguna untuk dengan cepat lulus / gagal untuk PRNG yang mungkin Anda kembangkan.

Semoga berhasil dengan eksperimen Anda!

Oh, saya melakukan tes ini pada rng yang Anda miliki di atas, menggunakan mod kecil kode Anda berikut:

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

Hasilnya adalah:

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

Saya akan menganggap PRNG bagus jika file output tidak dapat dikompresi sama sekali. Sejujurnya, saya tidak berpikir PRNG Anda akan melakukannya dengan baik, hanya 16% pada ~ 20 Meg cukup mengesankan untuk konstruksi yang sederhana. Tapi saya masih menganggapnya gagal.

Generator acak tercepat yang dapat Anda terapkan adalah ini:

XD, bercanda terpisah, selain semua yang dikatakan di sini, saya ingin berkontribusi mengutip bahwa pengujian urutan acak "adalah tugas yang sulit" [1], dan ada beberapa tes yang memeriksa properti tertentu dari nomor pseudo-acak, Anda dapat menemukan banyak dari mereka di sini: http://www.random.org/analysis/#2005

Salah satu cara sederhana untuk mengevaluasi "kualitas" generator acak adalah uji Chi Square lama.

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

Mengutip [1]

Gagasan tes χ² adalah untuk memeriksa apakah angka-angka yang dihasilkan tersebar secara wajar atau tidak. Jika kita menghasilkan angka positif N lebih kecil dari r , maka kita berharap mendapatkan sekitar N / r angka dari setiap nilai. Tapi --- dan ini adalah inti dari masalah ini --- frekuensi dari semua nilai tidak boleh persis sama: itu tidak akan acak!

Kami hanya menghitung jumlah kuadrat dari frekwensi kemunculan setiap nilai, diskalakan oleh frekuensi yang diharapkan, dan kemudian mengurangi ukuran urutan. Angka ini, "statistik χ²," dapat dinyatakan secara matematis sebagai

Jika statistik χ² dekat dengan r , maka angkanya acak; jika terlalu jauh, maka mereka tidak. Gagasan "tutup" dan "jauh" dapat lebih tepat didefinisikan: ada tabel yang menunjukkan dengan tepat bagaimana menghubungkan statistik dengan sifat-sifat urutan acak. Untuk tes sederhana yang kami lakukan, statistik harus dalam 2r

Menggunakan teori ini dan kode berikut:

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

Saya mendapat hasil sebagai berikut:

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

Yang, untuk QuickRandom, jauh dari r (di luar r ± 2 * sqrt(r))

Yang mengatakan, QuickRandom bisa cepat tetapi (seperti yang dinyatakan dalam jawaban lain) tidak baik sebagai penghasil angka acak

[1] SEDGEWICK ROBERT, Algoritma di C , Addinson Wesley Publishing Company, 1990, halaman 516 hingga 518

Saya mengumpulkan mock-up cepat dari algoritma Anda dalam JavaScript untuk mengevaluasi hasilnya. Ini menghasilkan 100.000 bilangan bulat acak dari 0 - 99 dan melacak contoh setiap bilangan bulat.

Hal pertama yang saya perhatikan adalah bahwa Anda lebih mungkin mendapatkan angka rendah daripada angka tinggi. Anda paling sering melihat ini ketika seed1sedang tinggi dan seed2rendah. Dalam beberapa contoh, saya hanya mendapatkan 3 angka.

Paling-paling, algoritme Anda perlu disempurnakan.

Jika Math.Random()fungsi memanggil sistem operasi untuk mendapatkan waktu, maka Anda tidak dapat membandingkannya dengan fungsi Anda. Fungsi Anda adalah PRNG, sedangkan fungsi itu berjuang untuk angka acak nyata. Apel dan jeruk.

PRNG Anda mungkin cepat, tetapi tidak memiliki informasi status yang cukup untuk mencapai periode yang lama sebelum diulang (dan logikanya tidak cukup canggih bahkan untuk mencapai periode yang mungkin dengan informasi negara sebanyak itu).

Periode adalah panjang urutan sebelum PRNG Anda mulai terulang. Ini terjadi segera setelah mesin PRNG membuat transisi keadaan ke keadaan yang identik dengan beberapa keadaan masa lalu. Dari sana, itu akan mengulangi transisi yang dimulai di negara itu. Masalah lain dengan PRNG adalah jumlah sekuens unik yang rendah, serta merosotnya konvergensi pada sekuens tertentu yang berulang. Bisa juga ada pola yang tidak diinginkan. Sebagai contoh, misalkan PRNG terlihat cukup acak ketika angka-angka dicetak dalam desimal, tetapi pemeriksaan nilai-nilai dalam biner menunjukkan bahwa bit 4 hanya beralih antara 0 dan 1 pada setiap panggilan. Ups!

Lihatlah Mersenne Twister dan algoritma lainnya. Ada beberapa cara untuk mencapai keseimbangan antara panjang periode dan siklus CPU. Salah satu pendekatan dasar (digunakan dalam Mersenne Twister) adalah untuk berputar-putar dalam vektor negara. Dengan kata lain, ketika angka sedang dihasilkan, itu tidak didasarkan pada seluruh negara, hanya pada beberapa kata dari subjek array negara untuk operasi bit sedikit. Tetapi pada setiap langkah, algoritme juga bergerak dalam array, mengacak konten sedikit demi sedikit.

Ada banyak, banyak generator angka acak pseudo di luar sana. Misalnya milik Knuth ranah , twister Mersenne , atau cari generator LFSR. "Algoritma seminarial" monumental Knuth menganalisa area tersebut, dan mengusulkan beberapa generator kongruensi linear (mudah diterapkan, cepat).

Tapi saya sarankan Anda tetap berpegang pada java.util.Randomatau Math.random, mereka cepat dan setidaknya OK untuk penggunaan sesekali (yaitu, game dan semacamnya). Jika Anda hanya paranoid pada distribusi (beberapa program Monte Carlo, atau algoritma genetika), periksa implementasinya (sumber tersedia di suatu tempat), dan seed mereka dengan beberapa nomor yang benar-benar acak, baik dari sistem operasi Anda atau dari random.org . Jika ini diperlukan untuk beberapa aplikasi di mana keamanan sangat penting, Anda harus menggali sendiri. Dan seperti dalam kasus itu Anda tidak harus percaya apa kotak berwarna dengan semburan bit hilang di sini, saya akan diam sekarang.

Sangat tidak mungkin bahwa kinerja pembuatan angka acak akan menjadi masalah untuk setiap kasus penggunaan yang Anda buat kecuali mengakses satu Randominstance dari beberapa utas (karena Randommemang demikian synchronized).

Namun, jika itu benar - benar terjadi dan Anda membutuhkan banyak angka acak dengan cepat, solusi Anda terlalu tidak dapat diandalkan. Terkadang memberikan hasil yang baik, terkadang memberikan hasil yang mengerikan (berdasarkan pengaturan awal).

Jika Anda ingin angka yang sama dengan yang diberikan Randomkelas, hanya lebih cepat, Anda bisa menghilangkan sinkronisasi di sana:

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

}

Saya hanya mengambil java.util.Randomkode dan menghapus sinkronisasi yang menghasilkan dua kali kinerja dibandingkan dengan yang asli pada Oracle HotSpot JVM 7u9 saya. Masih lebih lambat dari Anda QuickRandom, tetapi memberikan hasil yang jauh lebih konsisten. Tepatnya, untuk nilai yang sama seeddan aplikasi berulir tunggal, ini memberikan angka pseudo-acak yang sama dengan Randomkelas aslinya .

_{Kode ini didasarkan pada arus java.util.Randomdi OpenJDK 7u yang dilisensikan di bawah GNU GPL v2 .}

EDIT 10 bulan kemudian:

Saya baru saja menemukan bahwa Anda bahkan tidak perlu menggunakan kode saya di atas untuk mendapatkan Randomcontoh yang tidak disinkronkan . Ada satu di JDK juga!

Lihatlah ThreadLocalRandomkelas Java 7 . Kode di dalamnya hampir identik dengan kode saya di atas. Kelas ini hanya Randomversi yang diisolasi secara lokal yang cocok untuk menghasilkan angka acak dengan cepat. Satu-satunya downside yang dapat saya pikirkan adalah bahwa Anda tidak dapat mengatur seedsecara manual.

Contoh penggunaan:

Random random = ThreadLocalRandom.current();

'Acak' lebih dari sekedar tentang mendapatkan angka .... apa yang Anda miliki adalah pseudo-acak

Jika pseudo-random cukup baik untuk keperluan Anda, maka tentu saja, itu jauh lebih cepat (dan XOR + Bitshift akan lebih cepat daripada yang Anda miliki)

Rolf

Edit:

Oke, setelah terlalu tergesa-gesa dalam jawaban ini, izinkan saya menjawab alasan sebenarnya mengapa kode Anda lebih cepat:

Dari JavaDoc untuk Math.Random ()

Metode ini disinkronkan dengan benar untuk memungkinkan penggunaan yang benar oleh lebih dari satu utas. Namun, jika banyak utas perlu menghasilkan nomor pseudorandom pada tingkat yang tinggi, ini dapat mengurangi pertikaian untuk setiap utas untuk memiliki generator nomor pseudorandom sendiri.

Ini mungkin mengapa kode Anda lebih cepat.

java.util.Random tidak jauh berbeda, LCG dasar yang dijelaskan oleh Knuth. Namun memiliki 2 keunggulan / perbedaan utama:

• utas aman - setiap pembaruan adalah CAS yang lebih mahal daripada penulisan sederhana dan membutuhkan cabang (bahkan jika diprediksi secara tunggal). Tergantung pada CPU itu bisa menjadi perbedaan yang signifikan.
• keadaan internal yang dirahasiakan - ini sangat penting untuk apa pun yang non-sepele. Anda ingin nomor acak tidak dapat diprediksi.

Di bawah ini adalah rutin utama yang menghasilkan bilangan bulat 'acak' di 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));
    }

Jika Anda menghapus AtomicLong dan sate yang dirahasiakan (yaitu menggunakan semua bit dari long ), Anda akan mendapatkan lebih banyak kinerja daripada multiplikasi ganda / modulo.

Catatan terakhir: Math.randomtidak boleh digunakan untuk apa pun kecuali tes sederhana, itu rawan pertengkaran dan jika Anda bahkan memiliki beberapa utas menyebutnya bersamaan kinerja menurun. Satu fitur historis yang sedikit diketahui dari itu adalah pengenalan CAS di java - untuk mengalahkan tolok ukur yang terkenal (pertama oleh IBM melalui intrinsik dan kemudian Sun membuat "CAS dari Jawa")

Ini adalah fungsi acak yang saya gunakan untuk game saya. Ini cukup cepat, dan memiliki distribusi yang cukup (cukup).

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