常用的Random生成方法在极限条件下的对比实验.doc

真随机和伪随机随机数是计算机编程中一个非常重要的工具。利用它，我们可以完成很多很多很多的事，而且有很多很多很多的事也必须用随机数来完成。所以随机数够不够随机，对我们来说，是非常之关键的。在软件编程中，比如C#（其他任何语言均与此类似），我们用System.Random这个类来获得随机数。由于是使用特定算法获取的随机数，所以，从本质上来讲，Random生成的（甚至是任何软件生成的）随机数并非真随机数，而仅是具有一定随机程度的伪随机数。在Wikipedia上对伪随机数的解释是这样的。伪随机数，或称伪乱数，是使用一个确定性的算法计算出来的似乎是随机的数序，因此伪随机数实际上并不随机。在计算伪随机数时假如使用的开始值不变的话，那么伪随机数的数序也不变。伪随机数的随机性可以用它的统计特性来衡量， 其主要特征是每个数出现的可能性和它出现时与数序中其它数的关系。伪随机数的优点是它的计算比较简单，而且只使用少数数值很难推算出计算它的算法。一般人们使用一个假的随机数，比如电脑上的时间作为计算伪随机数的开始值。目前几乎所有的真随机数发生器（从理论上来说，真随机数只有可能在自然界中由物理现象产生，即由硬件实现）都具有其各自的专利，不是一般人可以接触的。下图列举了部分公司的真随机数发生器专利。作者：野比（）23 May 2012 保留所有权利 野比 2012System.Random的实现原理我们使用的System.Random类是基于Donald E. Knuth的减随机数生成器算法实现的，从实用角度而言， 其随机程度已经足够。在加上Random可以利用int型的种子进行随机化，所以我们在日常使用中并没有感觉到任何问题。关于测试其实今天我并不是要研究真随机数，只是在使用过程中，我想到一个情况：如果计算机飞速发展，而计算机又只能生成伪随机数，那么我们现在的一般应用情况1 Random rand;2 while(true)3 4 / 用种子初始化随机数5 rand = new Random(seed);6 int value = rand.Next();7 8 / （费时的操作）9 在未来超高速计算下，现在的费时的操作也许 未来就一晃而过，用时几乎可以忽略。在这样的极限情况下，上面的语句就变成了单纯的循环生成随机数了。那么这种情况下，Random生成的数值，还能不能够保证一定程度的随机呢？来做个实验看看。实验条件CPU：i3 380m 2.56GHz 2核4线程内存：DDR3 1066 2GB x2硬盘：TOSHIBA MK3265GSX (320 GB) 5400 RPMruntime：.NET Framework版本：v2.0.50727（C#2.0）开发：Visual Studio 2005 Team SuiteOS：Windows XP SP3实验方法模拟最严酷的环境，使用类似下面这样的代码，通过改变不同的rand生成方式和count数，对多种Random生成方式及相应的随机数生成结果进行对比。1 / 示例代码，不可用2 for(int i = 0; i count; i+)3 4 rand.Next();5 作者：野比（）23 May 2012 保留所有权利 野比 2012实验用例这次实验测试以下8种常见的随机数生成方式（找找看你一般用的第几种）：1. 默认构造函数使用Random rand=new Random()。这是最为简单的生成方法，单次生成，不重复。这也是MSDN建议的生成方式。2. 默认构造函数（重复创建）仍然使用默认构造函数，但是在每次循环中都重新创建Random变量，即不停的rand=new Random()，下同。3. 用常数作为种子使用rand=new Random(10)。用常数作为种子创建rand变量。单次，类似用例#1。4. 用常数作为种子（重复创建）类似用例#2。5. 用时间刻度作为种子（重复创建）这是比较普遍的一种用法，每次利用系统当前时间作为种子创建rand变量。使用DateTime.Now.Ticks（此属性的值表示自 0001 年 1 月 1 日午夜 12:00:00 以来已经过的时间的以 100 毫微秒为间隔的间隔数）。注意该方法只能重复创建，否则将成为用例#3。6. 用随机数作为种子（重复创建）这是一种看起来很随机的方法，使用另一个Random变量，在每次循环时用Next()作为种子创建新的rand变量。因为具体结果如何我也没有用过，所以需等实验后看数据才知道。注意该方法只能重复创建，否则将成为用例#3。7. 三角函数种子（重复创建）使用Math.Sin()三角函数作为种子创建新的rand变量。（纯实验）8. 复杂种子这是种子随机性比较大的一种方法，是众多高手常用的。我摘录了xiahouwen在CSDN的这篇帖子里介绍的方法，利用GUID哈希值、当前时间Ticks和计数器相乘来计算种子，生成rand变量。算法如下。 1 private static int randomCount = 0; 2 private static string CreateRandomText() 3 4 randomCount+; 5 6 Guid guid = Guid.NewGuid( ); 7 8 int key1 = guid.GetHashCode( ); 9 int key2 = unchecked( (int)DateTime.Now.Ticks );10 11 int seed = unchecked( key1 * key2 * randomCount );12 Random rand = new Random( seed );13 14 int n = rand.Next( 100000, 999999 );15 / （业务代码，略）16 实验原理实验原理较为简单，只是统计在生成范围内，生成的多个随机数的分布情况。利用数组进行统计，然后在PictureBox中绘制出统计直方图。同时，程序将统计最大重复出现次数和随机数跳变次数，以检验Random的生成结果变化情况。跳变数越多，表示生成的数字变化得越多，反之则生成数字变化较少。最理想的情况是跳变次数等于生成次数，即每次生成的数值都和前一次不同。实验程序的实现和代码这里不做解释，和本文无关。样图说明下面是两张测试样图，分别标记为A和B。Sample ASample B这是测试生成100个随机数的样图结果。生成的随机数范围是沿x轴从左到右，整个样图的Width范围。Random每生成一个随机数r，即在x=r处的直方图上+1，因此直方图每条线高度代表该线所在坐标数值出现次数。图中文字说明含义为： 最大重复：同样的数值出现的最大次数，例如生成100个随机数（0,1,2.），其中1出现了60次，则最大重复为60 跳变：当某次生成的随机数和前次不同，则跳变数+1 用时：生成全部（100个）随机数所用时间，该时间不含显示时间 需要注意的是直方图的高度是自适应的，因此两张不同的直方图对比时需要参考每张图上标注的最大重复。如何阅读样图测试程序运行后得到的样图参见前一节的Sample A和Sample B。样图记录的是Random生成的随机数的重复次数统计，因此越是不重复的样图，表示该测试用例的随机性越高。在图上看，就是直方图线条越多越好，最大重复数值越小越好，跳变越大越好。作者：野比（）23 May 2012 保留所有权利 野比 2012实验结果注意观察结果图中的数据。1. 100次生成2. 1,000次生成3. 10,000次生成4. 100,000次生成5. 1,000,000次生成作者：野比（）23 May 2012 保留所有权利 野比 2012结果分析从实验结果看，和我们平时的印象有所出入。下面逐一进行分析。#1：默认构造函数单次创建的Random变量忠实的完成了近乎白噪声的随机数输出分布。#2：很差的随机性。也展示出一个问题，即同样种子创建的Random，其输出具有极高的相似性。这和伪随机序列有关，参见#4。#3：使用常数完成初始化的Random，和#1类似，实现了相当程度的随机性输出。#4：每次采用同样的种子创建Random，并取Random生成的第一个随机数，得到的数值完全一样。这充分说明了计算机生成的伪随机序列，如果种子一样，序列index一样，那么得到的值也是（几乎）一样的。证明了Random获取的并非真实随机数。#5：对于高强度的生成，以时间为种子的#5却出现了随机不起来的问题。仔细分析，以100万次重复为例。共消耗时间3757.835毫秒，平均每次消耗即3757纳秒。DateTime.Ticks的最小时间刻度为100纳秒，照理说不应该出现种子来不及变化的情况。但事实上，把每次创建Random时的时间种子dump出来观察，会发现平均每2050次循环后，DateTime.Now.Ticks才会发生变化。这也就导致了输出的值域收缩了2050倍。#6：用#1的方式生成的随机数，以此作为新Random的种子，随机性上得到了保证，自然可以达到白噪声分布的效果。#7：使用Math.Sin()作为种子。由于Math.Sin()得到的是-11之间的实数，所以需要将其乘以某常数进行放大。放大带来的问题就是值域的收缩，再加上Sin()的周期性，出现了种子取值固定的问题。#8：让人寄予厚望