java 中的快速实值随机生成器

Question

java.util.Random.nextDouble() 对我来说很慢，我需要一些非常快的东西。

我做了一些 google 搜索，我只找到了基于整数的快速随机生成器。这里有关于区间 <0, 1) 的实数的任何信息吗？

Answer 1

您可以在初始化程序时创建一个随机双精度数组，然后重复它。这要快得多，但随机值会自行重复。

Answer 2

您可以通过以下方式修改基于整数的 RNG 以在区间 [0,1) 中输出双精度值：

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

但是，如果 randInt() 生成一个 32 位整数，这不会填充双精度数的所有位，因为双精度数有 53 个尾数位。您显然可以生成两个随机整数来填充所有尾数位。或者您可以查看 Ramdom.nextDouble() 实现的源代码。它几乎肯定会使用整数 RNG 并将输出简单地转换为双精度数。

至于性能，性能最好的随机数生成器是线性同余生成器。其中，我推荐使用 Numerical Recipes 生成器。您可以从维基百科查看更多关于 LCG 的信息：http://en.wikipedia.org/wiki/Linear_congruential_generator

不过，如果你想要好的随机性和性能不是那么重要，我认为Mersenne Twister是最好的选择。它还有一个维基百科页面：http://en.wikipedia.org/wiki/Mersenne_Twister

最近有一个名为 PCG 的随机数生成器，在 http://www.pcg-random.org/ 中进行了解释。这本质上是 LCG 的 post 处理步骤，提高了 LCG 输出的随机性。请注意，PCG 比 LCG 慢，因为它只是 LCG 的 post 处理步骤。因此，如果性能非常重要而随机性质量不那么重要，则要使用 LCG 而不是 PCG。

请注意，我提到的 none 个生成器是加密安全的。如果您需要将这些值用于加密应用程序，则应该使用加密安全算法。但是，我真的不相信双打会用于密码学。

Answer 3

恕我直言，您应该 接受 juhist 的回答 - 这就是原因。

nextDouble 很慢，因为它对 next() 进行了两次调用 - 它就写在文档中。

所以你最好的选择是：

使用快速 64 位生成器，将其转换为双精度（MT、PCG、xorshift*、ISAAC64、...）
直接生成双打

这是一个过长的基准测试，其中包含 java 的 Random、LCG（与 java.util.Random 一样糟糕）和 Marsaglia 的通用生成器（生成双打的版本）。

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 4

如果您需要快速的东西并且可以访问 Java8，我可以推荐 java.utils SplittableRandom。它更快（~两倍快）并且具有更好的统计分布。

如果您需要更快或更好的算法，我可以推荐这些专门的 XorShift 变体之一：

XorShift128PlusRandom（更快更好）
XorShift1024StarPhiRandom（速度差不多，周期更长）

有关这些算法及其质量的信息可在 this big PRNG comparison 中找到。

我做了一个独立的性能比较你可以在这里找到详细的结果和代码：github.com/tobijdc/PRNG-Performance

此外Apache Commons RNG has a performance test of all their implemented algoritms

TLDR

永远不要使用 java.util.Random，请使用 java.util.SplittableRandom。如果您需要更快或更好的 PRNG，请使用 XorShift 变体。

Answer 5

请注意，所有这些解决方案都遗漏了一个基本事实（直到几周前我才意识到这一点）：使用乘法从 64 位转换为双精度数会浪费大量时间。 DSI 实用程序 (http://dsiutils.di.unimi.it/) 中 xorshift128+ 和 xorshift1024+ 的实现使用直接位操作，结果令人印象深刻。

在

查看 nextDouble() 的基准

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

质量报告在

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

java 中的快速实值随机生成器

Fast real valued random generator in java

java

performance

random

double

generator