这是一个"足够好"的随机算法; 如果速度更快,为什么不使用？

Question

我做了一个叫做的课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

哇!它的执行速度几乎快4倍Math.random.

我记得在某处Math.random使用了System.nanoTime()大量的模数和分数.这真的有必要吗？我的算法执行速度更快,看起来很随机.

我有两个问题:

• 我的算法"足够好"(例如,游戏中,真正随机数字不是太重要)？
• Math.random当看起来只是简单的乘法和切掉小数就足够了,为什么这么做呢？

Answer 1

您的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  :                                                  

Answer 2

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

• 从种子值和乘数开始.
• 要生成随机数:
  • 乘以乘数的种子.
  • 将种子设置为等于此值.
  • 返回此值.

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

希望这可以帮助!

Answer 3

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

0.10 -> 0.20

被类似的序列强烈反映:

0.09 -> 0.18
0.11 -> 0.22

在许多情况下,这会在游戏中产生明显的相关性 - 例如,如果连续调用函数生成对象的X和Y坐标,对象将形成清晰的对角线模式.

除非你有充分的理由相信随机数生成器正在减慢你的应用程序(这是非常不可能的),所以没有充分的理由去尝试编写自己的应用程序.

Answer 4

这个问题的真正问题在于它的输出直方图在很大程度上取决于初始种子 - 大部分时间它会以接近均匀的输出结束,但很多时候会有明显不均匀的输出.

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

QuickRandom

System.Random

更糟

如果我们QuickRandom在new 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;
        }
    }
}

Answer 5

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

另一件需要考虑的事情是随机数生成器的"周期".显然,对于有限状态大小,等于double的尾数部分,它只能在循环之前返回最多2 ^ 52个值.但这是最好的情况 - 你能证明没有第1,2,3,4期的循环......？如果有,那么你的RNG在这些情况下会有可怕的退化行为.

此外,您的随机数生成是否会为所有起点分布均匀？如果没有,那么你的RNG将会有偏见 - 或者更糟糕的是,取决于起始种子,会有不同的偏见.

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

(顺便说一下,一个好的格言是:最快的代码是不运行的代码.你可以在世界上制作最快的随机(),但如果它不是非常随机则没有好处)

Answer 6

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

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

这让我可以快速迭代对于大约1到20兆字节序列的"足够好"PRNG的想法.它还提供了一个更好的自上而下的图片而不仅仅是通过眼睛检查它,因为任何"足够好"的PRNG具有半字状态可能很快超过你的眼睛看周期点的能力.

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

与频率分析相反,压缩测试的优点在于,通常很容易构建良好的分布:只需输出包含值为0到255的所有字符的256长度块,并执行100,000次.但是这个序列的长度为256.

偏差分布,即使是很小的余量,也应该通过压缩算法来获取,特别是如果你给它足够的(比如1兆字节)序列.如果更频繁地出现某些字符,双字节或n-gram,则压缩算法可以将此分布偏差编码为有利于频繁出现的代码,并使用较短的代码字,并获得压缩增量.

由于大多数压缩算法都很快,并且它们不需要实现(因为操作系统只是在它们周围),压缩测试对于快速评估您可能正在开发的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不会那么好,对于这样一个简单的结构,只有16%的~20 Megs相当令人印象深刻.但我仍然认为这是一个失败.

Answer 7

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

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

评估随机发生器"质量"的一种简单方法是旧的Chi Square测试.

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]

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

我们简单地计算每个值的出现频率的平方和,按预期频率进行缩放,然后减去序列的大小.该数字"χ2统计量"可以数学表示为

如果χ2统计量接近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出版公司,1990年,第516至518页

Answer 8

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

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

充其量,您的算法需要一些精炼.

Answer 9

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

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

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

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

Answer 10

那里有许多很多伪随机数发生器.例如Knuth的ranarray,Mersenne twister或者寻找LFSR发生器.Knuth的巨大"Seminumerical算法"分析了该区域,并提出了一些线性同余生成器(易于实现,快速).

但我建议你坚持java.util.Random或者Math.random,他们禁食,至少可以偶尔使用(比如游戏等).如果你只是偏执的分布(一些蒙特卡罗程序,或遗传算法),检查他们的实现(来源在某处可用),并从你的操作系统或random.org播种一些真正的随机数..如果某些安全性至关重要的应用程序需要这样做,那么您必须自己挖掘.在那种情况下,你不应该相信这里有一些缺少比特的彩色方块,我现在会闭嘴.

Answer 11

这是非常不可能的随机数生成性能将是任何使用情况下的一个问题,你来了,除非访问单个Random从多个线程实例(因为Random是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));
    }

}

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

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

编辑 10个月后:

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

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

用法示例:

Random random = ThreadLocalRandom.current();