随机数的分布

Question

我有两种代码选择：

选项 1

int myFunc() {
  return new Random().nextInt();
}

或者：

选项 2

private static final Random random = new Random();

int myFunc() {
  return random.nextInt();
}

我理解 option 2 更加地道。我想知道 option 1.

的有效性

在 option 1 中，我只会使用给定种子生成的第一个数字。在 option 2 中，我选择一个种子并使用该种子生成 n 数字。 IIUC 随机性保证在这个用例上。

因此，我的问题是，如果我多次调用 option 1，是否可以保证输出分布的均匀性？

Answer 1

Java 使用 System.nanoTime() 和顺序计数器初始化随机种子。这在某种程度上保证了每次调用的种子都是不同的，尽管我不会将其称为密码安全。

从性能的角度来看 - 您真的希望在选项 1 中锁定 Random 的内部状态会比以下所有选项产生更大的性能影响：

访问和递增 volatile long
获取当前系统时间(which is quite expensive)
动态分配
另一个用于垃圾回收的对象

我的建议是对您的实际应用程序进行基准测试以找出答案，但我希望选项 1 是所有三个中最慢的。

Answer 2

快速代码：

// For occasional tasks that just need an average quality random number
ExecutorService threadPool = Executors.newCachedThreadPool();
threadPool.execute( () -> {
  ThreadLocalRandom.current().nextInt(); // Fast and unique!
} );


// For SecureRandom, high quality random number
final Random r = new SecureRandom();
ExecutorService threadPool = Executors.newCachedThreadPool();
threadPool.execute( () -> {
  r.nextInt(); // sun.security.provider.NativePRNG uses singleton.  Can't dodge contention.
} );


// Apache Common Math - Mersenne Twister - decent and non-singleton
int cpu = Runtime.getRuntime().availableProcessors();
ExecutorService executor = Executors.newFixedThreadPool( cpu );
Map<Thread, RandomGenerator> random = new WeakHashMap<>( cpu, 1.0f );

executor.execute( ()-> {
   RandomGenerator r;
   synchronized ( random ) { // Get or create generator.
      r = random.get( Thread.currentThread() );
      if ( r == null ) random.put( Thread.currentThread(), r = new MersenneTwister() );
   }
   r.nextInt( 1000 );
} );

解释：

两个 Random 相同的种子将产生相同的数字。
1. 所以我们会重点关注能不能保证不同的种子。
理论上每个线程中的new Random()并不能保证不同的seed。
1. 新随机由 nanoTime 和一个 "unique" 数字播种。
2. 该数字不能保证唯一，因为它的计算不同步。
3. 至于nanoTime，保证是"at least at good as currentTimeMillis"
4. currentTimeMillis 不保证任何事情，可以 pretty coarse.
5. 在现实生活中，只有old linux systems and Win 98这两个时间是相同的。
实际上，new Random()在每个线程中基本上总是得到不同的种子。
1. 创建线程很昂贵。我的每 50,000 纳秒创建 1 个。那就是 not slow.
2. 50µs 远远高于 nanoTime 的常见粒度，最高可达 a few ten ns。
3. 唯一编号计算(1.2)也很快，所以得到相同编号的情况很少见。
4. 使用 Executors to create a thread pool 避免大量的新线程开销。
zapl ThreadLocalRandom.current().nextInt()。好主意。
1. 它不会创建新的 Random，但它也是一个 linear congruential generator。
2. 它为每个调用线程生成一个新的随机数作为该线程的种子。
3. 它被构建为在多线程中非常快。（见下面的注释。）
4. 它由 SecureRandom 静态播种，产生质量更好的随机数。
"uniformally distributed"只是randomness tests的一小部分。
1. Random 是 somewhat uniform, and its result can be predicted 只给出两个值。
2. SecureRandom guarantees this won't happens。（即加密强度高）
3. 如果您在每个线程中创建一个新的 SecureRandom，则没有种子冲突的风险。
4. 但是目前它的来源是single thread反正没有平行生成。
5. 支持多线程的好RNG，找external help like Apache Common's MT。

Note: Implementation details deduced from Java 8 source code. Future Java version may change; for example, ThreadLocalRandom is using sun.misc.Unsafe to store the seeds, which may be removed in Java 9 forcing ThreadLocalRandom to find a new way to work without contention.

Answer 3

My real question is whether option 1 is mathematically valid.

让我们从选项 2 开始。java.util.Random 使用的随机数生成器在 javadoc 中指定如下：

The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1.)

各种方法的 javadoc 中有更具体的细节。

但关键是我们正在使用由线性同余公式生成的序列，而此类公式具有显着程度的自相关......这可能会有问题。

现在使用选项 1，您每次都使用不同的 Random 实例和新种子，并应用一轮 LC 公式。因此，您将获得一系列可能与种子自相关的数字。但是，种子的生成方式不同，具体取决于 Java 版本。

Java 6 这样做：

 public Random() { this(++seedUniquifier + System.nanoTime()); }
 private static volatile long seedUniquifier = 8682522807148012L;

...这根本不是很随机。如果您以固定间隔创建 Random 个实例，则种子可能间隔很近，因此您的选项 #1 生成的随机数序列可能是自动相关的。

相比之下，Java 7 和 8 这样做：

 public Random() {
     this(seedUniquifier() ^ System.nanoTime());
 }

 private static long seedUniquifier() {
     // L'Ecuyer, "Tables of Linear Congruential Generators of
     // Different Sizes and Good Lattice Structure", 1999
     for (;;) {
         long current = seedUniquifier.get();
         long next = current * 181783497276652981L;
         if (seedUniquifier.compareAndSet(current, next))
             return next;
     }
 }

 private static final AtomicLong seedUniquifier
     = new AtomicLong(8682522807148012L);

上述产生的种子序列可能更接近（真实）随机性。这可能使您的选项 #1 优于选项 #2。

Java 6 到 8 中选项 #1 的缺点是 System.nanoTime() 可能调用涉及系统调用。就是比较贵。

所以简短的回答是 Java 版本特定选项 #1 和选项 #2 中哪个产生更好的质量 "random" 数字......从数学的角度来看。

在这两种情况下，数字的分布在足够大的样本量上是均匀的，尽管我不确定当过程是确定性的时候谈论概率分布是否有意义。

然而，这两种方法都不适合作为 "crypto strength" 随机数生成器。

Answer 4

根据我的经验，使用 "Messerne Twister" 生成器 (see in Apache Commons) . For an even fancier solution, see this.

之类的东西可以在良好的分布和性能之间取得最佳平衡

Answer 5

没有

无法保证选项 1 将产生的数字分布的属性。正如在其他答案中明确指出的那样，java.util.Random 的构造函数的实现取决于系统时间.因此，为了保证您使用选项 1 获得的数字分布的属性，您需要能够保证您的程序为获取任何系统时间而进行的调用所产生的数字分布。程序所在的平台运行.

但是，对于选项 2，可以对一次程序执行期间生成的数字分布做出数学保证。使用线性同余生成器（java.util.Random 使用的伪随机数生成算法）的一些随机性不如其他算法好，但保证分布相对均匀。

这并不一定意味着选项 1 不能满足您的目的。这取决于你在做什么。

随机数的分布

Distribution of Random Numbers

java

random

uniform-distribution