这是一个“足够好”的随机algorithm; 为什么不使用，如果它更快？
我做了一个叫做QuickRandom的类，它的工作就是快速生成随机数。 这非常简单：只取旧的值，乘以一个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; } }
这是我写的testing代码：
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); }
这是一个非常简单的algorithm，只是将前一个double乘以“magic number”double。 我很快把它扔在一起，所以我可以做得更好，但奇怪的是，似乎工作正常。
这是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快几乎4倍。
我记得在某处读到Math.random使用System.nanoTime()和疯狂的模数和划分的东西吨。 这真的有必要吗？ 我的algorithm执行得很快，看起来很随机。
我有两个问题：
- 我的algorithm是否“足够好”（比如说，一个真正的随机数字不是太重要的游戏）？
- 为什么
Math.random这么做似乎只是简单的乘法和切除小数就足够了？
你的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 :###################
如果您重复testing，您将看到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 :
你所描述的是一种称为线性同余生成器的随机生成器 。 发电机的工作原理如下：
- 从种子价值和乘数开始。
- 要生成一个随机数字：
- 乘数乘以种子。
- 设置种子等于这个值。
- 返回这个值。
这个发生器有很多很好的特性，但是作为一个好的随机源存在很大的问题。 上面链接的维基百科文章描述了一些优点和缺点。 总之，如果你需要好的随机值，这可能不是一个很好的方法。
希望这可以帮助！
你的随机数函数是不好的，因为它的内部状态太less – 在任何给定的步骤输出的数字完全取决于以前的数字。 例如，如果我们假设magicNumber是2（例如），那么序列：
0.10 -> 0.20
被类似的序列强烈反映：
0.09 -> 0.18 0.11 -> 0.22
在很多情况下，这会在游戏中产生明显的相关性 – 例如，如果连续调用函数来为对象生成X和Y坐标，对象将会形成清晰的对angular线模式。
除非你有充分的理由相信随机数发生器会减慢你的应用程序（这是非常不可能的），否则没有理由尝试写你自己的应用程序。
真正的问题在于，输出直方图依赖于初始种子远远大部分时间会以接近均匀的输出结束，但是很多时间将具有明显不均匀的输出。
受到这篇文章的启发， 关于php的rand()函数有多糟糕 ，我使用QuickRandom和System.Random了一些随机matrix图像。 这个运行表明有时种子可能会有一个不好的影响（在这种情况下有利于较低的数字），因为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; } } }
你的随机数发生器的一个问题是没有“隐藏状态” – 如果我知道你在最后一次呼叫时返回的随机数，我知道你将发送每一个随机数，直到时间结束，因为只有一个可能的下一个结果，等等等等。
另一个要考虑的是你的随机数发生器的“时期”。 显然，有限的状态大小，等于双数的尾数部分，在循环之前它将只能返回至多2 ^ 52的值。 但是，这是最好的情况 – 你能certificate没有第一，二，三，四…的循环吗？ 如果有的话，你的RNG在这些情况下将会有可怕的退化行为。
另外，您的随机数生成是否对所有的起点都有一个统一的分布？ 如果没有，那么你的RNG将会受到偏见 – 或者更糟的是，根据起始种子的不同，会有不同的偏见。
如果你能回答所有这些问题，真棒。 如果你不能，那么你知道为什么大多数人不重新发明车轮，并使用一个经过validation的随机数发生器;）
（顺便说一句，好的谚语是：最快的代码是不运行的代码，你可以在世界上做最快的随机（），但是如果它不是非常随机的话就不好）
我在开发PRNG时总是做一个普通的testing，
- 将输出转换为char值
- 将字符值写入文件
- 压缩文件
这使我能够快速迭代对“1到20兆字节”序列“足够好”PRNG的想法。 它也提供了一个更好的自上而下的画面，而不仅仅是通过眼睛检查，因为任何“足够好”的PRNG和半个字的状态可能很快超过你的眼睛看循环点的能力。
如果我真的很挑剔，那么我可以采用好的algorithm，对它们运行DIEHARD / NISTtesting，以获得更多的洞察，然后再回头再调整一些。
与频率分析相比，压缩testing的优势在于，构build一个良好的分布很简单：只需输出包含值为0-255的所有字符的256长度块，并且执行100,000次。 但是这个序列有一个长度为256的周期。
偏差分布，即使是小幅度的，也应该由压缩algorithm来选取，特别是如果你给它足够的（比如1兆字节）的序列来处理。 如果某些字符，双字母或n-gram出现的频率较高，则压缩algorithm可以将此分布偏斜编码为有利于频繁出现的代码，并获得较大的压缩量。
由于大多数压缩algorithm都是快速的，而且不需要实现（因为操作系统只是处在周围），压缩testing对于快速评估您可能正在开发的PRNG的合格/不合格非常有用。
祝你好运！
噢，我在上面的rng上进行了这个testing，使用下面的小代码：
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％左右的16％对于这样一个简单的build设来说是相当不错的。 但我仍然认为这是一个失败。
你可以实现的最快的随机生成器是这样的：
XD除了开玩笑之外，除了这里所说的一切外，我想引用testing随机序列“是一个艰巨的任务”[1]，并且有几个testing检查伪随机数的某些属性，你可以find很多在这里： http : //www.random.org/analysis/#2005
评估随机发生器“质量”的一个简单方法是老卡方testing。
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个数。 但是—这是事情的本质—所有价值的发生频率不应该是完全一样的：那不会是随机的！
我们简单地计算每个值出现频率的平方和，按照期望的频率进行缩放，然后减去序列的大小。 这个数字“χ²统计量”可以用math表示为
如果χ²统计量接近r ，则数字是随机的; 如果它太远，那么它们不是。 可以更精确地定义“接近”和“远离”的概念：存在这样的表格，这些表格确切地说明了统计与随机序列的性质之间的关系。 对于我们正在执行的简单testing，统计量应该在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， Calgorithm ，Addinson Wesley Publishing Company，1990，第516-518页
我在JavaScript中快速模拟了您的algorithm ，以评估结果。 它从0到99生成100,000个随机整数，并跟踪每个整数的实例。
我注意到的第一件事是，你比较高的数字更可能得到一个较低的数字。 当seed1很高， seed2很低的时候，你会看到最多的。 在几个例子中，我只有3个数字。
充其量，你的algorithm需要一些改进。
如果Math.Random()函数调用操作系统来获取一天中的时间，则无法将其与您的函数进行比较。 你的function是一个PRNG，而这个function是争取真正的随机数。 苹果和桔子。
你的PRNG可能很快，但是它没有足够的状态信息来实现很长的一段时间，而且它的逻辑还不够完善，甚至没有足够的时间来实现这些状态信息。
Period是PRNG开始重复之前的序列长度。 只要PRNG机器进行状态转换到与过去状态相同的状态，就会发生这种情况。 从那里，它将重复在该州开始的过渡。 PRNG的另一个问题可能是less数独特的序列，以及重复的特定序列上的简并收敛。 也可能有不希望的模式。 例如，假设PRNG在十进制数字打印时看起来是相当随机的，但通过检查二进制数值可以看出，在每次调用时，位4只是在0和1之间切换。 哎呀！
看看Mersenne Twister和其他algorithm。 有办法在周期长度和CPU周期之间取得平衡。 一种基本的方法（在Mersenne Twister中使用）是在状态向量中循环。 也就是说，当一个数字正在生成时，它不是基于整个状态，而是从状态数组开始的几个字进行一些操作。 但是在每个步骤中，algorithm也在arrays中移动，一次一个地加扰内容。
那里有许多伪随机数发生器。 例如Knuth的ranarray ， Mersenne扭曲者 ，或寻找LFSR发电机。 Knuth的巨大的“数值algorithm”分析了该区域，并提出了一些线性同余发生器（简单实施，快速）。
但是我build议你坚持使用java.util.Random或Math.random ，它们速度很快，至less偶尔使用（即游戏等）。 如果你对分布（一些蒙特卡罗程序或者遗传algorithm）只是偏执狂，那么检查一下它们的实现（源代码在某处），然后从你的操作系统或者random.org中以真正的随机数对它们进行种子处理。 。 如果这对安全性至关重要的应用程序是必需的，那么您必须挖掘自己。 在这种情况下，你不应该相信一些彩色的方块和缺less的东西在这里喷出来，我现在闭嘴。
除非从多个线程访问单个Random实例（因为Random是synchronized ），否则随机数生成性能不太可能会成为任何用例的问题。
但是，如果真的是这样，你需要很多随机数字，你的解决scheme太不可靠了。 有时它会给出好的结果，有时会给出可怕的结果（基于初始设置）。
如果你想得到与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类相同的伪随机数。
此代码基于GNU GPL v2许可的OpenJDK 7u中的当前java.util.Random 。
编辑 10个月后：
我刚刚发现，你甚至不必使用上面的代码来获得一个不同步的Random实例。 在JDK中也有一个！
看看Java 7的ThreadLocalRandom类。 里面的代码几乎和我上面的代码一样。 该类只是一个本地线程隔离的Random版本，适合快速生成随机数字。 我能想到的唯一缺点是你不能手动设置它的seed 。
用法示例：
Random random = ThreadLocalRandom.current();
'Random' is more than just about getting numbers…. what you have is pseudo-random
If pseudo-random is good enough for your purposes, then sure, it's way faster (and XOR+Bitshift will be faster than what you have)
Rolf
编辑：
OK, after being too hasty in this answer, let me answer the real reason why your code is faster:
From the JavaDoc for Math.Random()
This method is properly synchronized to allow correct use by more than one thread. However, if many threads need to generate pseudorandom numbers at a great rate, it may reduce contention for each thread to have its own pseudorandom-number generator.
This is likely why your code is faster.
java.util.Random is not much different, a basic LCG described by Knuth. However it has main 2 main advantages/differences:
- thread safe – each update is a CAS which is more expensive than a simple write and needs a branch (even if perfectly predicted single threaded). Depending on the CPU it could be significant difference.
- undisclosed internal state – this is very important for anything non-trivial. You wish the random numbers not to be predictable.
Below it's the main routine generating 'random' integers in 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)); }
If you remove the AtomicLong and the undisclosed sate (ie using all bits of the long ), you'd get more performance than the double multiplication/modulo.
Last note: Math.random should not be used for anything but simple tests, it's prone to contention and if you have even a couple of threads calling it concurrently the performance degrades. One little known historical feature of it is the introduction of CAS in java – to beat an infamous benchmark (first by IBM via intrinsics and then Sun made "CAS from Java")
This is the random function I use for my games. It's pretty fast, and has good (enough) distribution.
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)); } }
