金沙澳门官网手机版每当产生了6或者7都要抛弃

当前位置:金沙手机版58588 > 金沙澳门官网手机版 > 金沙澳门官网手机版每当产生了6或者7都要抛弃
作者: 金沙手机版58588|来源: http://www.aidenlayout.com|栏目:金沙澳门官网手机版

文章关键词:金沙手机版58588,随机取样

  这是在编程工作最常见的随机函数的应用,在这里做一个起点再合适不过。把随机数区间的起点从

  如果b-a和RAND_MAX很接近会发生什么情况?读者不妨先做思考,问题2的分析会做出解答。这个rand(),其实相当于《编程珠玑》提到的bigrand()。

  给定一个随机数函数rand7(),它能以等概率生成1~7这7个整数。请根据rand7()写出类似的rand5()。

  如果直接像问题1中一样,把1+rand7()%5作为rand5()会有什么情况发生?这时确实能产生1~5的随机数没错,可是各个数的概率相等吗?

  对于随机数2,既有可能来自于1+1%5,也有可能来自于1+6%5,显然其概率是2/7,而不是1/5,不满足rand5()等概率产生各随机数这一隐含要求。不同于问题1,问题1中一个很大的区间收缩成较小区间时,各个元素映射后的新元素概率虽然概率可能不完全一样,但却是近似相同的。

  虽然保证了1~5的概率都变成了1/5,但是有一个无法避免的缺点是,每当产生了6或者7都要抛弃,相当于这一次运行是“空转”,浪费了时间。如果对1/5这个概率不明白,可以有两种理解:每次产生6或7就被抛弃,剩下数的概率相等,必然为1/5;或者用更严密的推理:产生1~5的随机数,最终得到某一个的概率为:1/7+(1/7)*(2/7)+(1/7)*(2/7)2+...,无限项求和,结果是1/5。

  给定一个随机数函数rand7(),金沙澳门官网手机版它能以等概率生成1~7这7个整数。请根据rand7()写出类似的rand10()。

  有了问题2的概率基础,把rand7()变成rand10()仅仅需要一点点思考了。

  问题2和问题3是对《编程珠玑》上使用范围不大的randint(i,j)生成其他范围随机数方法的解答。在掌握了问题2和问题3的解法后,你已经学会随机数区间的收缩和扩张,类似的问题迎刃而解。

  C库函数rand()常返回15个随机位,写出bigrand(),能够返回30个随机位。

  其实问题4和问题3有点像,但是不同之处在于,这次我们的视角是从位出发的,把rand()看做了将15个位每一个位以1/2概率设为0或1,从而生成0~RAND_MAX。从某种意义上来说,按这种理解方式来解这个问题更轻松一些,但是仅局限于2的幂减1这样的数值的区间,比如从0到11...11。在此基础之上把两部分的位拼接起来即可。

  这是一个简单粗暴有效的方法,使用这个方法你可以不用考虑复杂的区间扩展和收缩的问题。以rand7()产生rand10()为例,构造一个二维数组并把它填成:

  然后使用两次rand7()分别生成行号和列号,金沙澳门官网手机版如果对应元素是0,抛弃重来;否则即是结果。其实这种方法依然用到了区间扩展:把7扩展成7*7,并把不符合的部分抛弃。这样横向生成一个1~7的随机数,纵坐标生成1~7的随机数,这样两次随机数便能定位一个数组元素,若该元素为1~10之间的数,则被选中,否则重新选择。这能保证1~10之间的每个数被选中的概率都是1/10。从这里可以看出这种方法其实还是有缺陷的:如果用rand7()生成rand50(),那这50个数可是填满这个表格后还有填不下的。金沙澳门官网手机版

  用随机事件表示随机事件?这个问题具体化为:使用rand()表示以M/N的概率发生的随机事件,其中M=N,并可用作:if(事件A发生),其中P(A) = M/N,那么表示为:

  通过这种方式,我们就可以做出让程序“以M/N的概率执行某个命令”这样的设计了。

  考虑整数0,1,2,...,n-1,可以用上节的方法以概率m/n选取0(推导方式略)。但是对于1,必须考虑之前0是否被选取而以(m-1)/(n-1)或m/(n-1)的概率选取1,后续就更加麻烦。好在迭代是计算机的长项,只需要把这个是否选择当前数的随机事件稍作修改即可,使之变成从r个其余的数中选择s个:

  《编程珠玑》提示,这种算法是“所有n的所有m元子集被选中的概率相等”,这个条件强于“所有元素被选中的概率相同”。下面是习题12.2中提到的“以等概率选择所有元素,但是有些m元子集被选中的概率比其他子集大”的算法:直接选择1个数,则这个m元集合为它本身即后续的一共m个数,可能包括回绕。

  对于这种方法,总要产生n次随机数。进一步可以写为for(i=0;in&&m0;i++),但程序的平均运行时间是否变得更快需要权衡。对应地,习题12.7提供了一种稍微减少随机数产生次数的递归函数:

  由于集合元素不重复,如果按等概率选择一个随机数,不在集合中就把它插入,反之直接抛弃,直到集合元素个数达到m个,同样可以满足要求,并且用C++的STL很容易实现:

  这个算法的主要问题是,如果抛弃已存在的元素的次数过多,相当于多次产生随机数并进行集合操作,性能将明显下降。比如当n=100而m=99,取第99个元素时,算法“闭着眼睛乱猜整数,直到偶然碰上正确的那个为止”(《编程珠玑(续)》,13.1节)。虽然这种情况会在“从一般到特殊”提供解决方案,但下面的Floyd算法明显规避了产生随机数超过m次的问题。

  习题12.9提供了一种基于STL集合的随机数取样方法,可以在最坏情况下也只产生m个随机数:限定当前从中取值的区间的大小,每当产生重复的随机数,就把这一次迭代时不会产生的第一个随机数拿来替换。

  不必基于集合而实现,我自己写了一个原理类似的算法,思想是把“用过”的元素“扔”到下一次迭代的随机数取样区间之外:

  这是个来源于实际的想法:将所有n个元素打乱,取出前m个。更快的做法是,打乱前m个即可。对应的C++代码如下:

  把sort注释掉的这段代码,可以作为随机不重复序列产生器。类似的还有Floyd的算法P。(《编程珠玑(续)》,13.3节)

  以上讨论的几种方式都不限定m和n的取值,只需m=n即可。对于特殊的取值,有特殊的解决方案,以下是编程珠玑上的两例:

  1.n = 106而m=n-10,这时m很大较为接近n,可以先生成10个元素,然后输出其余的元素。进行这种处理的额外代码可以提高算法的平均速度。

  2.n=231而m = 107,mn,这时可以先生成1.1*107个元素,排序后去掉重复的(由于n很大,m中出现重复元素的概率很低),得到107个元素的样本。

  (《编程珠玑(续)》习题13.5)Doug McIlory的求N个元素中取M种的第G种情况的组合的算法,原书这个算法我没有理解,也没有看到比较满意的解释,可能用到了某些我不熟悉的组合数性质。原书中没有对其进行进一步解释,并且似乎只是作者的题外话而已。如果看着有困难,这部分代码完全可以跳过。介绍这个算法的原因是用它能在获得随机数G后,直接获得第G种N个元素取M个的取法,相当于只产生了一次随机数。

  1.读取一个未知行数的文件,随机输出其中的的一行,同时最多只能缓冲一行的内容(《编程珠玑(续)》习题15.3利用了这种形式);

  2.对链表进行一趟遍历,随机输出其中的一个结点的元素,只能使用一个临时指针。

  解法是,以概率1选择第一个元素存入缓存,以概率1/2用第二个元素替换掉缓存,...,直至遍历完所有元素,最后输出缓存的内容。可以分析出此时所有元素留在缓存的概率均为1/n,比如1,是1*(1/2)*(2/3)*...*((n-1)/n)。

  对于这个问题的常见应用:马尔科夫文本生成器里选择哈希表中某项对应链表的任意一个结点。

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!