这是一个“足够好”的随机算法吗？如果它更快，为什么不使用它？

performance algorithm random java

2022-08-31 06:57:27

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

这是我的课程全文：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.randomSystem.nanoTime()

我有两个问题：

我的算法是否“足够好”（例如，对于一个游戏，真正的随机数不太重要）？
为什么在看起来只是简单的乘法和切掉小数就足够了的情况下做这么多？Math.random

答案 1

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

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  :

答案 2

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

从种子值和乘数开始。
要生成随机数：
- 将种子乘以乘数。
- 将种子设置为等于此值。
- 返回此值。

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

希望这有帮助！