随机数的分布

7

我有两个代码选项:

选项1

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

或者:

选项2

private static final Random random = new Random();

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

我知道“选项2”更为惯用。我想问一下“选项1”的有效性。
在“选项1”中,我只会使用给定种子生成的第一个数字。在“选项2”中,我选择一个种子并使用该种子生成“n”个数字。如果我理解正确,随机性的保证是基于这种用法的。
因此,我的问题是,如果我多次调用“选项1”,是否有任何保证输出的分布均匀?

2
选择第三个选项:ThreadLocalRandom.current().nextInt()。另外,您关于同时生成随机数的说法是错误的,详情请参考https://dev59.com/lHnZa4cB1Zd3GeqPoErj#20060801,它不仅使用时间进行初始化。 - zapl
谢谢,我没意识到这点。我会更新问题的。 - Benjy Kessler
5个回答

10
快速代码:
// 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. 相同种子的两个随机数生成器会产生相同的数字。
    1. 因此我们将关注是否能够保证不同的种子。
  2. 理论上,每个线程中的new Random()不能保证不同的种子。

    1. new RandomnanoTime和一个“唯一”数字种子。
    2. 该数字无法保证唯一,因为其计算未进行同步。
    3. 至于nanoTime,它保证“至少与currentTimeMillis一样好”
    4. currentTimeMillis没有保证,可能会相当 粗略
    5. 在现实生活中,只有旧Linux系统和Win 98上的两个时间相同。
  3. 实际上,每个线程中的new Random()基本上总是获得不同的种子。

    1. 创建线程是昂贵的。我的程序每50,000ns创建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寻找一种新的方法来避免竞争。

谢谢。你说“在每个新线程中使用new Random()不能保证均匀分布。”能否详细解释一下?为什么时钟的性能与随机性有关?正如zapl所说,即使两次调用Random的时间完全相同,它也会给出不同的种子。为什么启动线程的时间会对分布的随机性产生负面影响?能否提供一些来源资料? - Benjy Kessler
在理论上,以完美的并行执行方式同时创建两个随机数生成器应该会产生具有相同种子的两个随机数生成器,这是从Java 8 u92开始的。但是,“完全相同的时间”和“完美的并行执行”很难实现。我的意思是,因为线程需要相对较长的时间来创建,仅仅是纳秒级别的时间偏差就足以确保你的随机数生成器在实践中获得不同的种子(第二点),即使不能保证它们是不同的(第一点)。 - Sheepy
抱歉,我认为我的问题不够清晰。随机数生成器(RNG)的工作方式是将一个随机数转换为另一个随机数。因此,从一个“随机”数字开始,您可以生成任意数量的“随机”数字。关键在于你用的是一个类似随机的数字开始,输出的随机性取决于种子的随机性。在我的情况下,我正在使用不同的模型。我没有使用一个“随机” 种子开始,而是使用 n 个高度相关的种子。我的问题是,我是否仍然能够保证均匀性(均匀性,而不是随机性)。 - Benjy Kessler

4
我的真正问题是选项1是否在数学上有效。
我们从选项2开始。 java.util.Random使用的随机数生成器在javadoc中规定如下:
该类使用一个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版本。
在两种情况下,数字的分布将在足够大的样本大小上均匀,尽管当过程是确定性的时,谈论概率分布可能没有意义。
然而,无论哪种方法都不适合作为“加密强度”随机数生成器。

谢谢,那非常有趣。您提到System.nanoTime很昂贵。如果您只使用seedUniquifier作为种子而不调用默认构造函数会发生什么?我可以在启动时计算seedUniquifier() ^ System.nanoTime()一次,然后将其用作我的初始种子,以避免每次运行都获得相同的序列。结果是否会自相关? - Benjy Kessler
1
“你提到System.nanoTime很昂贵。” - 相对来说是昂贵的。 - Stephen C
“我可以在启动时计算seedUniquifier() ^ System.nanoTime(),然后将其用作我的初始种子,以避免每次运行获得相同的序列。那么结果会自相关吗?” - 是的。我认为是这样。但您可以进行测试。谷歌搜索“测试自相关性”以获取一些线索。 - Stephen C

1

编号。

不能保证选项1生成的数字分布的属性。正如其他答案中所明确的那样,java.util.Random的构造器实现取决于系统时间。因此,为了对选项1生成的数字分布的属性做出保证,您需要能够对程序在任何平台上获取系统时间的调用所产生的数字分布做出保证。

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

这并不一定意味着选项1不能满足您的需求。这取决于您要做什么。


通过在每次调用时调用新的RNG,他正在调用种子算法以启动第一个数字。播种算法本身是否在整个范围内均匀?不太可能。 “正如可以看到的那样,给定来自java.util.Random的两个整数,我们可以预测所有未来生成的整数。”(https://jazzy.id.au/2010/09/20/cracking_random_number_generators_part_1.html)他没有使用RNG,而是使用了糟糕的种子算法。 - ingyhere

0

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

从性能角度来看,您真的希望在选项1中锁定Random的内部状态比以下所有操作都要慢吗:

  • 访问和递增易失性长整型
  • 获取当前系统时间(相当昂贵
  • 动态分配
  • 另一个需要垃圾回收的对象

我的建议是对您的实际应用程序进行基准测试以找出答案,但我预计选项1将是三个选项中最慢的。


谢谢。我更感兴趣的是了解“密码学安全”方面。效率只是我提出使用选项1的理由之一。我的真正问题是选项1是否在数学上有效。 - Benjy Kessler
1
java.util.Random的实例是线程安全的。然而,在跨线程并发使用相同的java.util.Random实例时,可能会遇到争用和随之而来的性能下降。java.util.Random的实例不具备加密安全性。考虑改用SecureRandom获取加密安全的伪随机数生成器,以供安全敏感应用程序使用。 - ifly6
我想我的问题对于SecureRandom仍然是一样的。每次创建一个新的实例并从给定种子生成一个实例,是否仍然安全?还是它与种子的选择(函数调用的时间)如此相关,以至于随机性丢失了。 - Benjy Kessler

0
在我的经验中,好的分布和性能之间的最佳平衡是使用类似于“Messerne Twister”生成器(在Apache Commons中查看)。对于更高级的解决方案,请参见this

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接