Hızlı gerçek değerli rasgele jeneratör java

Question

java.util.Random.nextDouble() benim için yavaş ve gerçekten hızlı bir şeye ihtiyacım var.

Bazı Google aramaları yaptım ve yalnızca tamsayı tabanlı hızlı rastgele jeneratörler buldum. < 0, 1) aralıklarından gerçek rakamlar için bir şey var mı?

Answer 1

, ben java.utilsSplitableRandom tavsiye edebilir. Daha hızlıdır (iki kat daha hızlıdır) ve daha iyi istatistiksel dağılımı vardır.

Bir daha da hızlı veya daha iyi bir algoritma gerekirse ben bu uzman XorShift varyantları birini önerebilir:

• Xoroshiro128+ (hızlı & iyi)
• XorShift1024* (benzer hız, daha uzun süre)

Bu algoritmalar ve bunların kalitesi hakkında bilgi this big PRNG comparison içinde bulunabilir. github.com/tobijdc/PRNG-Performance

TLDR

java.util.SplittableRandom kullanın java.util.Random asla kullanmayın:

Ben bağımsız Performans karşılaştırma ayrıntılı sonuçları ve kodu buraya bulabilirsiniz yaptı. Daha hızlı veya daha iyi PRNG'ye ihtiyacınız varsa, bir XorShift varyantı kullanın.

Answer 2

Programınızı başlattığınızda rastgele iki katmanlar oluşturabilir ve ardından tekrarlayabilirsiniz. Bu çok daha hızlı ama rastgele değerler kendilerini yeniden canlandırıyor.

Answer 3

Yapabilirdin şu şekilde aralık [0,1) çıkış çiftler arasında bir tamsayıdır göre bir rasgele sayı üreteci değiştirin: randint() 32 bitlik bir sayı üretir halinde

double randDouble = randInt()/(RAND_INT_MAX + 1.0) 

Bununla birlikte, bu olmaz çiftteki tüm bitleri doldurun çünkü çiftin 53 mantissa biti vardır. Açıkça tüm mantissa bitlerini doldurmak için iki rastgele tamsayı üretebilirsiniz. Ya da Ramdom.nextDouble() uygulamasının kaynak koduna bir göz atabilirsiniz. Neredeyse bir tamsayı RNG kullanır ve çıktıyı iki katına dönüştürür.

Performans açısından, en iyi performans gösteren rasgele sayı üreteçleri lineer uyumlu jeneratörlerdir. Bunlardan Sayısal Tarifler jeneratörünü kullanmanızı tavsiye ederim. LCG'ler hakkında daha fazla bilgiyi Vikipedi'den edinebilirsiniz:

Ancak, iyi bir rasgelelik ve performans istiyorsanız, bu önemli değil, Mersenne Twister en iyi seçimdir. Ayrıca bir Vikipedi sayfası: http://en.wikipedia.org/wiki/Mersenne_Twister

http://www.pcg-random.org/'da açıklanan PCG adı verilen yeni bir rasgele sayı üreteci var. Bu, LCG çıktısının rasgeleliğini artıran LCG için bir işlem sonrası aşamadır. PCG'nin LCG'den daha yavaş olduğunu unutmayın, çünkü bu sadece LCG için bir işlem sonrası adımdır. Böylece performans çok önemli ve rastgelelik kalitesi önemli değilse, PCG yerine LCG kullanmak istersiniz.

Belirttiğim jeneratörlerden hiçbirinin kriptografik olarak güvenli olmadığını unutmayın. Kriptografik uygulamalar için değerlere ihtiyacınız varsa, şifreli olarak güvenli bir algoritma kullanmalısınız. Ancak, iki katın şifreleme için kullanılacağına gerçekten inanmıyorum.

Answer 4

nextDouble darboğaz olduğunu göstermek için gerçekten kıyaslama veya profilleme yaptınız mı? MersenneTwister veya L'Ecuyer'ın streams library gibi alternatiflerine baktınız mı? Onları kıyaslama ile denemenizi tavsiye ederim, ama bedava öğle yemeği diye bir şey yoktur. Hızdaki gelişmeler muhtemelen bir maliyet pahasına olacak ve bunun tersi de doğru olacaktır.

Answer 5

Imho, sadece juhist'in cevabını kabul etmelisiniz - işte neden.

nextDouble yavaştır, çünkü sonraki iki çağrı yapar() - belgede tam olarak yazılmıştır.

yüzden en iyi seçenek vardır:

• kullanımı hızlı 64 bit jeneratör, o iki katına (MT, PDR, xorshift *, ISAAC64, ...)
• çiftler oluşturmak dönüştürmek doğrudan

Burada java's Random, bir LCG (java.util.Random kadar kötü) ve Marsaglia'nın evrensel jeneratörü (iki kat üretme sürümü) ile çok uzun bir değerlendirme var.Eğer hızlı bir şeye ihtiyacım ve Java8 erişiminiz varsa

import java.util.*; 

public class d01 { 
    private static long sec(double x) 
    { 
     return (long) (x * (1000L*1000*1000)); 
    } 
    // ns/op: nanoseconds to generate a double 
    // loop until it takes a second. 
    public static double ns_op(Random r) 
    { 
     long nanos = -1; 
     int n; 
     for(n = 1; n < 0x12345678; n *= 2) { 
      long t0 = System.nanoTime(); 
      for(int i = 0; i < n; i++) 
       r.nextDouble(); 
      nanos = System.nanoTime() - t0; 
      if(nanos >= sec(1)) 
       break; 
      if(nanos < sec(0.1)) 
       n *= 4; 
     } 
     return nanos/(double)n; 
    } 
    public static void bench(Random r) 
    { 
     System.out.println(ns_op(r) + " " + r.toString()); 
    } 

    public static void main(String[] args) 
    { 
     for(int i = 0; i < 3; i++) { 
      bench(new Random()); 
      bench(new LCG64(new Random().nextLong())); 
      bench(new UNI_double(new Random().nextLong())); 
     } 
    } 
} 

// straight from wikipedia 
class LCG64 extends java.util.Random { 
    private long x; 
    public LCG64(long seed) { 
     this.x = seed; 
    } 
    @Override 
    public long nextLong() { 
     x = x * 6364136223846793005L + 1442695040888963407L; 
     return x; 
    } 
    @Override 
    public double nextDouble(){ 
     return (nextLong() >>> 11) * (1.0/9007199254740992.0); 
    } 
    @Override 
    protected int next(int nbits) 
    { 
     throw new RuntimeException("TODO"); 
    } 
} 


class UNI_double extends java.util.Random { 
    // Marsaglia's UNIversal random generator extended to double precision 
    // G. Marsaglia, W.W. Tsang/Statistics & Probability Letters 66 (2004) 183 – 187 
    private final double[] U = new double[98]; 
    static final double r=9007199254740881.0/9007199254740992.; 
    static final double d=362436069876.0/9007199254740992.0; 
    private double c=0.; 
    private int i=97,j=33; 
    @Override 
    public double nextDouble(){ 
      double x; 

      x=U[i]- U[j]; 
      if(x<0.0) 
       x=x+1.0; 
      U[i]=x; 

      if(--i==0) i=97; 
      if(--j==0) j=97; 

      c=c-d; 
      if(c<0.0) 
       c=c+r; 

      x=x-c; 
      if(x<0.) 
       return x+1.; 
      return x; 
     } 
    //A two-seed function for filling the static array U[98] one bit at a time 
    private 
     void fillU(int seed1, int seed2){ 
      double s,t; 
      int x,y,i,j; 
      x=seed1; 
      y=seed2; 

      for (i=1; i<98; i++){ 
       s= 0.0; 
       t=0.5; 

       for (j=1; j<54; j++){ 
        x=(6969*x) % 65543; 
        // typo in the paper: 
        //y=(8888*x) % 65579; 
        //used forthe demo in the last page of the paper. 
        y=(8888*y) % 65579; 
        if(((x^y)& 32)>0) 
         s=s+t; 
        t=.5*t; 
       } 
       if(x == 0) 
        throw new IllegalArgumentException("x"); 
       if(y == 0) 
        throw new IllegalArgumentException("y"); 
       U[i]=s; 
      } 
     } 

    // Marsaglia's test code is useless because of a typo in fillU(): 
    // x=(6969*x)%65543; 
    // y=(8888*x)% 65579; 

    public UNI_double(long seed) 
    { 
     Random r = new Random(seed); 
     for(;;) { 
      try { 
       fillU(r.nextInt(), r.nextInt()); 
       break; 
      } catch(Exception e) { 
       // loop again 
      } 
     } 
    } 

    @Override 
    protected int next(int nbits) 
    { 
     throw new RuntimeException("TODO"); 
    } 
} 

Answer 6

Tüm bu çözümlerin temel bir gerçeği (birkaç hafta öncesine kadar farkında değildim) özlediğini unutmayın: bir çarpma kullanarak 64 bit'ten bir çifte geçmek büyük bir zaman kaybıdır. DSI yardımcı programlarında (http://dsiutils.di.unimi.it/) xorshift128 + ve xorshift1024 + 'nın uygulanması, doğrudan bit manipülasyonunu kullanır ve sonuçlar etkileyici olur.

http://dsiutils.di.unimi.it/docs/it/unimi/dsi/util/package-summary.html#package.description

de nextDouble() için testlerini görün ve kalite

http://prng.di.unimi.it/