171

我创建了一个名为 的类QuickRandom,它的工作是快速生成随机数。这真的很简单:只需取旧值,乘以 a double,然后取小数部分。

这是我QuickRandom的全部课程:

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

这是一个非常简单的算法,只需将前一个双精度数乘以一个“幻数”双精度数。我很快就把它拼凑起来,所以我可能会做得更好,但奇怪的是,它似乎工作得很好。

这是方法中注释掉的行的示例输出main

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

嗯。很随意。事实上,这适用于游戏中的随机数生成器。

以下是未注释部分的示例输出:

5456313909
1427223941

哇!它的执行速度比Math.random.

我记得在某个地方读到Math.randomSystem.nanoTime()很多疯狂的模数和除法的东西。这真的有必要吗?我的算法执行得更快,而且看起来很随机。

我有两个问题:

  • 我的算法是否“足够好”(例如,对于真正随机数不太重要的游戏)?
  • Math.random当看起来只是简单的乘法和去掉小数就足够了,为什么要做这么多呢?
4

14 回答 14

351

您的QuickRandom实现并没有真正均匀分布。频率通常在较低值处较高,同时Math.random()具有更均匀的分布。这是一个SSCCE,它表明:

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

}

平均结果如下所示:

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

如果你重复测试,你会看到 QR 分布变化很大,这取决于初始种子,而 MR 分布是稳定的。有时它会达到所需的均匀分布,但通常不会。这是一个更极端的例子,它甚至超出了图表的边界:

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  :                                                  
于 2013-01-24T01:14:59.650 回答
133

您所描述的是一种称为线性同余生成器的随机生成器。生成器的工作原理如下:

  • 从种子值和乘数开始。
  • 要生成随机数:
    • 将种子乘以乘数。
    • 将种子设置为等于该值。
    • 返回这个值。

这个生成器有很多不错的属性,但是作为一个好的随机源存在很大的问题。上面链接的维基百科文章描述了一些优点和缺点。简而言之,如果您需要好的随机值,这可能不是一个很好的方法。

希望这可以帮助!

于 2013-01-24T00:51:55.133 回答
113

您的随机数函数很差,因为它的内部状态太少——函数在任何给定步骤输出的数字完全取决于前一个数字。例如,如果我们假设它magicNumber是 2(举例来说),那么序列:

0.10 -> 0.20

由相似的序列强烈反映:

0.09 -> 0.18
0.11 -> 0.22

在许多情况下,这会在您的游戏中产生明显的相关性——例如,如果您连续调用您的函数来为对象生成 X 和 Y 坐标,那么这些对象将形成清晰的对角线图案。

除非您有充分的理由相信随机数生成器会降低您的应用程序的速度(这不太可能),否则没有充分的理由尝试自己编写。

于 2013-01-24T00:53:06.607 回答
110

真正的问题是它的输出直方图很大程度上依赖于初始种子——大部分时间它会以接近均匀的输出结束,但很多时候会有明显不均匀的输出。

这篇关于 phprand()功能QuickRandom有多糟糕的文章的启发,我使用和制作了一些随机矩阵图像System.Random。此运行显示有时种子可能会产生不良影响(在这种情况下有利于较低的数字),因为System.Random它是非常均匀的。

QuickRandom

System.Random

更糟

如果我们QuickRandomnew QuickRandom(0.01, 1.03)得到这个图像时进行初始化:

编码

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;
        }
    }
}
于 2013-01-25T17:03:19.357 回答
37

您的随机数生成器的一个问题是没有“隐藏状态” - 如果我知道您在最后一次通话中返回的随机数,我知道您将发送的每个随机数直到时间结束,因为只有一个可能的下一个结果,依此类推。

要考虑的另一件事是随机数生成器的“周期”。显然,对于有限状态大小,等于双精度数的尾数部分,它在循环之前最多只能返回 2^52 个值。但这是最好的情况——你能证明不存在周期 1、2、3、4...的循环吗?如果有,在这些情况下,您的 RNG 将出现糟糕的、退化的行为。

此外,您的随机数生成是否会针对所有起点均匀分布?如果没有,那么您的 RNG 将有偏见 - 或者更糟糕的是,根据起始种子的不同,以不同的方式产生偏见。

如果你能回答所有这些问题,那就太棒了。如果你不能,那么你知道为什么大多数人不重新发明轮子并使用经过验证的随机数生成器;)

(顺便说一句,一句好的格言是:最快的代码是不运行的代码。你可以制作世界上最快的 random(),但如果不是很随机就不好)

于 2013-01-24T00:54:40.383 回答
36

我在开发 PRNG 时经常做的一项常见测试是:

  1. 将输出转换为 char 值
  2. 将字符值写入文件
  3. 压缩文件

这让我可以快速迭代对于大约 1 到 20 兆字节的序列“足够好”的 PRNG 的想法。它还提供了比仅用肉眼检查更好的自上而下的图片,因为任何“足够好”的带有半个字状态的 PRNG 都可能很快超过您的眼睛看到循环点的能力。

如果我真的很挑剔,我可能会采用好的算法并对它们进行 DIEHARD/NIST 测试,以获得更多的洞察力,然后再回去进行更多的调整。

与频率分析相比,压缩测试的优势在于,很容易构建一个良好的分布:只需输出一个包含 0 - 255 值的所有字符的 256 长度块,然后执行 100,000 次。但是这个序列有一个长度为 256 的循环。

一个偏斜的分布,即使是很小的幅度,也应该被压缩算法拾取,特别是如果你给它足够的序列(比如 1 兆字节)来处理它。如果某些字符、bigrams 或 n-grams 更频繁地出现,压缩算法可以将此分布倾斜编码为有利于使用较短代码字的频繁出现的代码,并且您会获得压缩增量。

由于大多数压缩算法速度很快,并且它们不需要实现(因为操作系统只是将它们放在周围),因此压缩测试对于快速评估您可能正在开发的 PRNG 的通过/失败非常有用。

祝你的实验好运!

哦,我在上面的 rng 上执行了这个测试,使用你的代码的以下小模块:

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

结果是:

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

如果输出文件根本无法压缩,我会认为 PRNG 很好。老实说,我不认为你的 PRNG 会做得这么好,对于这样一个简单的结构来说,大约 20 Megs 上只有 16% 是相当可观的。但我仍然认为这是失败的。

于 2013-01-24T21:12:21.047 回答
33

您可以实现的最快的随机生成器是:

在此处输入图像描述

XD,除了笑话,除了这里所说的一切,我想贡献一下,引用测试随机序列“是一项艰巨的任务”[1],并且有几个测试可以检查伪随机数的某些属性,你可以找到一个这里有很多:http ://www.random.org/analysis/#2005

评估随机生成器“质量”的一种简单方法是旧的卡方检验。

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

引用 [1]

χ² 检验的思想是检查产生的数字是否合理分布。如果我们生成N个小于r的正数,那么我们期望得到每个值的N / r个数。但是——这就是问题的本质——所有值的出现频率不应该完全相同:那不会是随机的!

我们只需计算每个值出现频率的平方和,按预期频率缩放,然后减去序列的大小。这个数字,“χ² 统计量”,可以在数学上表示为

卡方公式

如果 χ² 统计量接近r,则数字是随机的;如果它太远,那么它们不是。“近”和“远”的概念可以更精确地定义:存在的表格准确地说明了统计数据与随机序列的属性之间的关系。对于我们正在执行的简单测试,统计量应该在 2√r

使用这个理论和以下代码:

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

我得到以下结果:

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

其中,对于 QuickRandom,远离r (在 之外 r ± 2 * sqrt(r)

话虽如此, QuickRandom 可能很快,但(如另一个答案中所述)不如随机数生成器


[1] SEDGEWICK ROBERT,C 语言算法,Addinson Wesley Publishing Company,1990 年,第 516 至 518 页

于 2013-01-29T02:25:33.763 回答
14

我在 JavaScript 中对您的算法进行了快速模拟,以评估结果。它从 0 到 99 生成 100,000 个随机整数并跟踪每个整数的实例。

我注意到的第一件事是你更有可能得到一个低数字而不是一个高数字。seed1你在高和seed2低时看到这个最多。在某些情况下,我只得到了 3 个数字。

充其量,您的算法需要一些改进。

于 2013-01-24T01:13:55.620 回答
8

如果Math.Random()函数调用操作系统来获取一天中的时间,那么您无法将其与您的函数进行比较。您的函数是 PRNG,而该函数正在争取真正的随机数。苹果和橙子。

您的 PRNG 可能很快,但它没有足够的状态信息来在它重复之前实现很长的周期(并且它的逻辑不够复杂,甚至无法实现有那么多状态信息可能实现的周期)。

周期是您的 PRNG 开始重复之前的序列长度。只要 PRNG 机器将状态转换到与某个过去状态相同的状态,就会发生这种情况。从那里开始,它将重复从该状态开始的转换。PRNG 的另一个问题可能是唯一序列数量少,以及在重复的特定序列上的退化收敛。也可能存在不希望的模式。例如,假设 PRNG 在以十进制打印数字时看起来相当随机,但对二进制值的检查表明,每次调用时位 4 只是在 0 和 1 之间切换。哎呀!

看看 Mersenne Twister 和其他算法。有一些方法可以在周期长度和 CPU 周期之间取得平衡。一种基本方法(在 Mersenne Twister 中使用)是在状态向量中循环。也就是说,在生成一个数的时候,并不是基于整个状态,而是基于状态数组中的几个字进行几位操作。但在每一步,算法也会在数组中移动,一次一点点地打乱内容。

于 2013-01-24T06:20:00.607 回答
7

那里有很多很多的伪随机数生成器。例如 Knuth 的ranarrayMersenne twister或寻找 LFSR 生成器。Knuth 具有里程碑意义的“半数值算法”分析了该领域,并提出了一些线性同余生成器(实现简单、快速)。

但我建议你坚持使用java.util.Randomor Math.random,它们速度很快,至少可以偶尔使用(即游戏等)。如果您只是对分布(一些蒙特卡罗程序或遗传算法)感到偏执,请检查它们的实现(源在某处可用),并用一些真正的随机数播种它们,无论是来自您的操作系统还是来自random.org . 如果某些安全性至关重要的应用程序需要这样做,您将不得不自己挖掘。在那种情况下,你不应该相信这里会出现什么带有缺失位的彩色方块,我现在就闭嘴。

于 2013-01-24T13:17:40.930 回答
7

对于您提出的任何用例,随机数生成性能不太可能成为问题,除非Random从多个线程访问单个实例(因为Randomis synchronized)。

但是,如果情况确实如此,并且您需要快速获取大量随机数,那么您的解决方案就太不可靠了。有时它给出了很好的结果,有时它给出了可怕的结果(基于初始设置)。

如果你想要班级给你的相同数字Random,只是更快,你可以摆脱那里的同步:

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

}

我只是获取了代码并删除了同步,与我的 Oracle HotSpot JVM 7u9 上的原始性能相比,java.util.Random这导致了两倍的性能。它仍然比你的慢QuickRandom,但它提供了更一致的结果。准确地说,对于相同的seed值和单线程应用程序,它提供与原始类相同的伪随机数。Random


此代码基于java.util.RandomOpenJDK 7u中的当前版本,该版本在GNU GPL v2下获得许可。


10个月后编辑:

我刚刚发现您甚至不必使用我上面的代码来获取未同步的Random实例。JDK 中也有一个!

看看 Java 7 的ThreadLocalRandom类。它里面的代码几乎和我上面的代码一样。该类只是一个本地线程隔离Random版本,适用于快速生成随机数。我能想到的唯一缺点是你不能seed手动设置它。

示例用法:

Random random = ThreadLocalRandom.current();
于 2013-01-28T14:07:03.550 回答
3

java.util.Random 差别不大,是 Knuth 描述的基本 LCG。然而,它有两个主要优点/区别:

  • 线程安全 - 每次更新都是一个 CAS,它比简单的写入更昂贵,并且需要一个分支(即使完美预测为单线程)。根据 CPU 的不同,它可能会有很大的不同。
  • 未公开的内部状态——这对于任何重要的事情都非常重要。您希望随机数不可预测。

下面是在 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));
    }

如果您删除 AtomicLong 和未公开的状态(即使用 的所有位long),您将获得比双倍乘法/模数更高的性能。

最后一点:Math.random除了简单的测试之外,不应该用于任何事情,它很容易发生争用,如果你甚至有几个线程同时调用它,性能就会下降。它的一个鲜为人知的历史特征是在 java 中引入 CAS - 以击败一个臭名昭著的基准(首先由 IBM 通过内在函数,然后 Sun 制作了“来自 Java 的 CAS”)

于 2013-01-25T00:52:51.173 回答
3

“随机”不仅仅是获取数字......你所拥有的是伪随机

如果伪随机足以满足您的目的,那么可以肯定,它会更快(并且 XOR+Bitshift 会比您拥有的更快)

罗尔夫

编辑:

好的,在回答得太仓促之后,让我回答一下您的代码更快的真正原因:

来自 Math.Random() 的 JavaDoc

此方法已正确同步,以允许多个线程正确使用。但是,如果许多线程需要以很高的速率生成伪随机数,则可能会减少每个线程对拥有自己的伪随机数生成器的争用。

这可能就是您的代码更快的原因。

于 2013-01-24T00:44:32.797 回答
0

这是我在游戏中使用的随机函数。它非常快,并且具有良好(足够)的分布。

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));
       }
}
于 2014-06-05T13:24:17.960 回答