免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 11020 | 回复: 33

浅谈Perl的随机数 [复制链接]

论坛徽章:
0
发表于 2013-10-17 12:28 |显示全部楼层
本帖最后由 iamlimeng 于 2013-10-17 13:26 编辑

随机性不是您所想象的那样呆板:一些数字流要比其它一些更随机。计算机一直是具有完全确定性的机器,所以,特别在行为随机性方面表现不尽人意,因为确定性的机器很难实现随机。事实上,(部分)随机数真正的唯一来源涉及到测量物理现象,譬如,基于测量诸如原子的放射性衰变或热辐射中的波动之类,它可以用某些数学方面的技巧来提取纯的随机序列(或至少是伪随机数发生器的种子)。但多数情况下,我们并不具备这样的条件。

无须利用实际的设备,计算机程序需要随机数时,会自己来生成这些数字。但这种计算机的决定机制使得生成随机数的算法很困难。正是由于这样,而使大多数程序员转向伪随机数。我们建立了真正调用伪随机数生成器(PRNG)的 random() 。什么是伪随机数生成器?假定需要生成介于 1 和 10 之间的随机数,每一个数出现的几率都是一样的。理想情况下,应生成 0 到 1 之间的一个值,不考虑以前值,这个范围中的每一个值出现的几率都是一样的,然后再将该值乘以 10。请注意,在 0 和 1 之间有无穷多个值,而计算机不能提供这样的精度。

为了编写代码来实现类似于前面提到的算法,常见情况下,伪随机数生成器生成 0 到 N 之间的一个整数,返回的整数再除以 N。得出的数字总是处于 0 和 1 之间。对生成器随后的调用采用第一次运行产生的整数,并将它传给一个函数,以生成 0 到 N 之间的一个新整数,然后再将新整数除以 N 返回。这意味着,由任何伪随机数生成器返回的数目会受到 0 到 N 之间整数数目的限制。

在大多数的常见随机数发生器中,N 是 2的32次方 (大约等于 40 亿),对于 32 位数字来说,这是最大的值。换句话说,我们经常碰到的这类生成器能够至多生成 40 亿个可能值。而这 40 亿个数根本不算大,只是指尖这么大。

伪随机数生成器将作为“种子”的数当作初始整数传给函数。这粒种子会使这个球(生成伪随机数)一直滚下去。伪随机数生成器的结果仅仅是不可预测。由伪随机数生成器返回的每一个值完全由它返回的前一个值所决定(最终,该种子决定了一切)。如果知道用于计算任何一个值的那个整数,那么就可以算出从这个生成器返回的下一个值。

结果,伪随机数生成器是一个生成完全可预料的数列(称为流)的确定性程序。一个编写得很好的的 PRNG 可以创建一个序列,而这个序列的属性与许多真正随机数的序列的属性是一样的。一方面,伪随机数生成器有许多有用的应用方面用途。另一方面,在那种需要不可预料性(如洗虚拟牌或加密数据)的应用中,伪随机数生成器很难以一种安全的方式来使用。如果知道种子和算法,就可以很容易地推算出这个序列。

基于历史先例,PRNG 的种子通常是参照系统时钟生成的。这个想法是使用系统时间的某一点来作为种子。这意味着如果能算出生成器什么时间发生,那么就可以知道由生成器生成的每一个值(包括数字出现的次序)。这样的结果说明,用时钟播种的伪随机数,所有结果不是不可预测的。正如我们所见,这个事实对于洗牌算法和密钥有着深远的影响。

所以,不正确地使用伪随机数生成器会导致惊人的安全性问题。希望您不会发生这类问题。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

以上内容摘录自Gary McGraw & John Viega撰写的《使您的软件运行起来: 摆弄数字,真正安全的软件需要精确的随机数生成器》,网址:
http://www.ibm.com/developerworks/cn/security/playing/index.html

Perl提供了内置的随机数生成函数rand(),调用非常方便和简单。前几天,需要模拟一批实验数据,用到Perl的随机数,发现了一些很有趣的现象。我要模拟的数据是这样的:从10000个有编号的元素中,每次随机抽取200个元素,允许重复,抽取1000万次,统计每个元素被抽取到的次数。

代码如下:
  1. #!/usr/bin/perl

  2. use strict;
  3. use warnings;

  4. my $rand = 10000;
  5. my %count = ();
  6. for (1..10000000) {
  7.         $count{int rand($rand)}++;
  8. }
  9. open(FH,">rand.xls");
  10. for (0..$rand-1) {
  11.         $count{$_} = 0 if (!$count{$_});
  12.         print FH "$count{$_}\n";
  13. }
  14. close FH;
复制代码
当我在不同的时间,不同的计算机上模拟出N份数据后,发现一个很难解释的现象,这些数据惊人地一致,分别都围绕两个相对集中的区间分布,在1000-1100之间断档。如图:
10000-1000W.png
修改一下参数,抽取次数改为100万次,其他参数不变,数据分布如图:
10000-100W.png
修改一下参数,抽取次数改为1亿次,其他参数不变,数据分布如图:
10000-1亿.png
将元素库改为1000个,抽取次数改为100万次,其他参数不变,数据分布如图:
1000-100W.png
将元素库改为1000个,抽取次数改为1000万次,其他参数不变,数据分布如图:
1000-1000W.png
将元素库改为1000个,抽取次数改为1亿次,其他参数不变,数据分布如图:
1000-1亿.png
理论上正常的随机数,应该表现为正态分布。从以上分布图我们能很明显地发现Perl内置随机数生成函数的缺陷,当数据量达到一定规模时,它的缺陷就会表现得很明显,而且是非常不安全的。但数据规模不是很大时,用内置随机函数是可以接受的。由此,我们可以得出结论,Perl内置的rand()函数是经过阉割的伪随机数生成器。

那么Perl能不能生成相对严谨可用的随机数呢?有,CPAN上有几个现成的模块可用:
1、Math::Random: Math::Random is a Perl port of the C version of randlib, which is a suite of routines for generating random deviates.
2、Math::Random::MT: The Mersenne Twister PRNG.
3、Math::Random::MT:erl: Pure Perl Mersenne Twister Random Number Generator.
4、Math::TrulyRandom:Perl interface to a truly random number generator function. The random numbers take a long time (in computer terms) to generate, so are only really useful for seeding pseudo random sequence generators.
以上模块都能生成相对可用的随机数。我们简单用Math::Random测试一下上述问题。代码如下:
  1. #!/usr/bin/perl

  2. use strict;
  3. use warnings;
  4. use Math::Random qw(random_uniform_integer);

  5. my $rand = 10000;
  6. my %count = ();
  7. for (1..10000000) {
  8.         my $no = random_uniform_integer(1, 0, $rand);
  9.         $count{$no}++;
  10. }
  11. open(FH,">rand.xls");
  12. for (0..$rand-1) {
  13.         $count{$_} = 0 if (!$count{$_});
  14.         print FH "$count{$_}\n";
  15. }
  16. close FH;
复制代码
元素库为10000个,抽取次数改为100万次,其他参数不变,数据分布如图:
10000-100WMR.png
元素库为10000个,抽取次数改为1000万次,其他参数不变,数据分布如图:
10000-1000WMR.png
元素库为10000个,抽取次数改为1亿次,其他参数不变,数据分布如图:
10000-1亿MR.png
元素库为1000个,抽取次数改为100万次,其他参数不变,数据分布如图:
1000-100WMR.png
元素库为1000个,抽取次数改为1000万次,其他参数不变,数据分布如图:
1000-1000WMR.png
元素库为1000个,抽取次数改为1亿次,其他参数不变,数据分布如图:
1000-1亿MR.png
从数据的分布图来看,基本符合正态分布,在不是特别高安全要求的情况下,这就是可用的随机数生成器,尽管它还是伪随机数生成器。

前三个模块,生成的数据非常接近,效果相当,第4个未测试。

我们简单测试一下它们的运行效率。设元素库为10000个,抽取次数为1亿次,其他参数如上,生成两组这样的数据。在我的计算机上运行(Intel Core i3-2130 CPU 3.40Ghz, 2GB内存,32位 Windows 7 SP1 旗舰版, ActivePerl 5.14.2),使用内置函数用时55秒;使用Math::Random用时262秒;Math::Random::MT用时271秒;Math::Random::MT:erl与前者相当;Math::TrulyRandom文档明确说明了很慢,未测试,肯定是龟速。

以上测试,是在32位OS上的表现,在64位OS上肯定会有差异,但那只是精度问题,若数据规模大到一定程度,最终的表现也会显现同样的规律,不过,我没有条件来测试。

水平有限,以上测试仅供参考,不严谨之处,请大牛们指正。

论坛徽章:
46
15-16赛季CBA联赛之四川
日期:2018-03-27 11:59:132015年亚洲杯之沙特阿拉伯
日期:2015-04-11 17:31:45天蝎座
日期:2015-03-25 16:56:49双鱼座
日期:2015-03-25 16:56:30摩羯座
日期:2015-03-25 16:56:09巳蛇
日期:2015-03-25 16:55:30卯兔
日期:2015-03-25 16:54:29子鼠
日期:2015-03-25 16:53:59申猴
日期:2015-03-25 16:53:29寅虎
日期:2015-03-25 16:52:29羊年新春福章
日期:2015-03-25 16:51:212015亚冠之布里斯班狮吼
日期:2015-07-13 10:44:56
发表于 2013-10-17 12:59 |显示全部楼层
默认的 rand 只能产生 32768(0x7FFF) 个不同数字

论坛徽章:
46
15-16赛季CBA联赛之四川
日期:2018-03-27 11:59:132015年亚洲杯之沙特阿拉伯
日期:2015-04-11 17:31:45天蝎座
日期:2015-03-25 16:56:49双鱼座
日期:2015-03-25 16:56:30摩羯座
日期:2015-03-25 16:56:09巳蛇
日期:2015-03-25 16:55:30卯兔
日期:2015-03-25 16:54:29子鼠
日期:2015-03-25 16:53:59申猴
日期:2015-03-25 16:53:29寅虎
日期:2015-03-25 16:52:29羊年新春福章
日期:2015-03-25 16:51:212015亚冠之布里斯班狮吼
日期:2015-07-13 10:44:56
发表于 2013-10-17 13:00 |显示全部楼层
相对你10000个数据集来说不可能算平均分布

论坛徽章:
46
15-16赛季CBA联赛之四川
日期:2018-03-27 11:59:132015年亚洲杯之沙特阿拉伯
日期:2015-04-11 17:31:45天蝎座
日期:2015-03-25 16:56:49双鱼座
日期:2015-03-25 16:56:30摩羯座
日期:2015-03-25 16:56:09巳蛇
日期:2015-03-25 16:55:30卯兔
日期:2015-03-25 16:54:29子鼠
日期:2015-03-25 16:53:59申猴
日期:2015-03-25 16:53:29寅虎
日期:2015-03-25 16:52:29羊年新春福章
日期:2015-03-25 16:51:212015亚冠之布里斯班狮吼
日期:2015-07-13 10:44:56
发表于 2013-10-17 13:06 |显示全部楼层
本帖最后由 zhlong8 于 2013-10-17 13:08 编辑

0-0x7fff 个数字分布到 10000 个区间里面需要每个除以 3.2768

for (0 .. 0x7fff) { my $n = int ($_ / 3.2768); $hash{$n} ++ }

得到的 %hash 表明每两个相临数字分布比为 3:4 也就是你图上显示的 900 1200 两条线的比例

论坛徽章:
46
15-16赛季CBA联赛之四川
日期:2018-03-27 11:59:132015年亚洲杯之沙特阿拉伯
日期:2015-04-11 17:31:45天蝎座
日期:2015-03-25 16:56:49双鱼座
日期:2015-03-25 16:56:30摩羯座
日期:2015-03-25 16:56:09巳蛇
日期:2015-03-25 16:55:30卯兔
日期:2015-03-25 16:54:29子鼠
日期:2015-03-25 16:53:59申猴
日期:2015-03-25 16:53:29寅虎
日期:2015-03-25 16:52:29羊年新春福章
日期:2015-03-25 16:51:212015亚冠之布里斯班狮吼
日期:2015-07-13 10:44:56
发表于 2013-10-17 13:13 |显示全部楼层
啊不对,是4个数字一组, 4:3:3:3 的比例

论坛徽章:
0
发表于 2013-10-17 13:22 |显示全部楼层
本帖最后由 iamlimeng 于 2013-10-17 13:24 编辑

回复 5# zhlong8


10000个元素,每次抽200个,抽取1000万次,在64位计算机上表现正常,内置rand()受硬件限制,如果数据规模超过这个限制,就会有问题。rand()可能是为了保持运算速度而实现的简化版随机,这在数据规模较小的情况下是没问题的,超过上限,就有问题了。

论坛徽章:
46
15-16赛季CBA联赛之四川
日期:2018-03-27 11:59:132015年亚洲杯之沙特阿拉伯
日期:2015-04-11 17:31:45天蝎座
日期:2015-03-25 16:56:49双鱼座
日期:2015-03-25 16:56:30摩羯座
日期:2015-03-25 16:56:09巳蛇
日期:2015-03-25 16:55:30卯兔
日期:2015-03-25 16:54:29子鼠
日期:2015-03-25 16:53:59申猴
日期:2015-03-25 16:53:29寅虎
日期:2015-03-25 16:52:29羊年新春福章
日期:2015-03-25 16:51:212015亚冠之布里斯班狮吼
日期:2015-07-13 10:44:56
发表于 2013-10-17 13:30 |显示全部楼层
回复 6# iamlimeng


    样本空间过小导致平均分布在 int 取整后不再是平均分布了,只有15bit的随机数显然无法满足10000个可能的值。

论坛徽章:
0
发表于 2013-10-17 13:34 |显示全部楼层
回复 7# zhlong8

应该是rand()底层实现的限制导致的,因为同样的条件,用模块生成随机数,表现正常。

论坛徽章:
5
丑牛
日期:2014-01-21 08:26:26卯兔
日期:2014-03-11 06:37:43天秤座
日期:2014-03-25 08:52:52寅虎
日期:2014-04-19 11:39:48午马
日期:2014-08-06 03:56:58
发表于 2013-10-17 14:24 |显示全部楼层
回复 5# zhlong8
是4个数字一组, 4:3:3:3 的比例


怎么两条线不是4条线, 这说明什么呢?

论坛徽章:
46
15-16赛季CBA联赛之四川
日期:2018-03-27 11:59:132015年亚洲杯之沙特阿拉伯
日期:2015-04-11 17:31:45天蝎座
日期:2015-03-25 16:56:49双鱼座
日期:2015-03-25 16:56:30摩羯座
日期:2015-03-25 16:56:09巳蛇
日期:2015-03-25 16:55:30卯兔
日期:2015-03-25 16:54:29子鼠
日期:2015-03-25 16:53:59申猴
日期:2015-03-25 16:53:29寅虎
日期:2015-03-25 16:52:29羊年新春福章
日期:2015-03-25 16:51:212015亚冠之布里斯班狮吼
日期:2015-07-13 10:44:56
发表于 2013-10-17 15:23 |显示全部楼层
pitonas 发表于 2013-10-17 14:24
回复 5# zhlong8
是4个数字一组, 4:3:3:3 的比例


那3个3都是900左右重合了啊,也就是上下两个线值的比是4:3 密度比是 1:3,第6个图也一样是两条线的比例是 33:32 点的密度是 4:1。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

基于案例的 SQL 优化实战训练营

讲师:中电福富特级专家梁敬彬,参与本次课程培训,你将收获:
1. 能编写出较为高效的 SQL;
2. 能解决70%以上的数据库常见优化问题;
3. 能得到老师提供的高效的相关工具和解决方案;
4. 能举一反三,收获不仅仅是 SQL 优化。
现在购票享受8.8折优惠!
----------------------------------------
优惠时间:2019年3月20日前

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP