随机数的分布

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

快速代码:

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

说明:

1. 两个Random相同的种子将产生相同的数字.
   1. 因此,我们将关注我们是否可以保证不同的种子.

2. 理论上,new Random()在每个线程中都不保证不同的种子.

   1. 新的Random由nanoTime和一个"唯一"数字播种.
   2. 该数字不保证唯一,因为其计算不同步.
   3. 至于nanoTime,它保证"至少与currentTimeMillis一样好"
   4. currentTimeMillis不保证任何东西,可能非常 粗糙.
   5. 在现实生活中,两次在旧的Linux系统和Win 98上是相同的.

3. 在实践中,new Random()在每个线程中基本上总是得到不同的种子.

   1. 创建线程很昂贵.我的每50,000英尺创造1个.这并不 慢.
   2. 50μs远高于nanoTime的常见粒度,高达几十ns.
   3. 唯一数字计算(1.2)也很快,因此获得相同的数字是非常罕见的.
   4. 使用Executors创建一个线程池,以避免繁重的新线程开销.

4. zapl 建议 ThreadLocalRandom.current().nextInt().很好的主意.

   1. 它不会创建新的Random,但它也是一个线性同余生成器.
   2. 它为每个调用线程生成一个新的随机数作为该线程的种子.
   3. 它在多线程中构建得非常快.(见下面的注释.)
   4. 它是静态播种的SecureRandom,可产生质量更好的随机数.

5. "统一分布"只是随机性 测试的一小部分.

   1. Random在某种程度上是统一的,只需给出两个值即可预测其结果.
   2. SecureRandom保证不会发生这种情况.(即密码强)
   3. 如果SecureRandom在每个线程中创建一个新的,则不存在种子冲突的风险.
   4. 但目前它的来源仍然是单线程,没有并行生成.
   5. 对于支持多线程的优秀RNG,请查找Apache Common的MT等外部帮助.

注意:从Java 8源代码推导出的实现细节.未来的Java版本可能会改变; 例如,ThreadLocalRandom使用sun.misc.Unsafe储存的种子,这可以被移除 Java中9迫使ThreadLocalRandom找到没有争到全新的工作方式.

Answer 2

我真正的问题是选项 1 在数学上是否有效。

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

该类使用 48 位种子，并使用线性同余公式对其进行修改。（参见 Donald Knuth，《计算机编程的艺术》，第 2 卷，第 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()可能的调用涉及系统调用。那是相对昂贵的。

所以简短的回答是，从数学角度来看，选项 #1 和选项 #2 中哪一个产生更好质量的“随机”数字是 Java 版本特有的。

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

然而，这两种方法都不适合作为“加密强度”随机数生成器。