Java教程

随机数算法---蓄水池抽样算法,拒绝采样,Fisher-Yates洗牌算法

本文主要是介绍随机数算法---蓄水池抽样算法,拒绝采样,Fisher-Yates洗牌算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

蓄水池采样算法

“给出一个数据流,这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法,使得数据流中所有数据被选中的概率相等。”

算法过程
假设数据序列的规模为 n,需要采样的数量的为 k。
首先构建一个可容纳k 个元素的数组,将序列的前 k 个元素放入数组中。
然后从第 k+1 个元素开始,以 k/n 的概率来决定该元素最后是否被留在数组中(每进来来一个新的元素,数组中的每个旧元素被替换的概率是相同的)。 当遍历完所有元素之后,数组中剩下的元素即为所需采取的样本。

for i in range(K,N): # K + 1 个元素开始进行概率采样
    r = random.randint(i + 1)
    if (r < K):// 这里其实就是k/n的体现
         result[r] = pool[i];

拒绝采样

已知rand7(),求产生rand10()
基本思路大家都知道的,就是call rand7()两次然后进行拒绝采样,因此大部分人第一下想到的算法如下:

row, col = 0, 0 
idx = 0
while idx > 40:
    row = rand7();
    col = rand7();
    idx = col + (row-1)*7;//选择第row行第col列的数字,每行7个数字
return 1 + (idx-1)%10;

没有必要idx为41~49之间的时候下一次重新调用两次rand7()

row, col = 0, 0 
idx = 0
while True:
    row = rand7();
    col = rand7();
    idx = col + (row-1)*7;//选择第row行第col列的数字,每行7个数字
	if idx <= 40:
		return 1 + (idx-1)%10;
	row = idx - 40
    col = rand7()
    idx = col + (row-1)*7;
    if idx <= 60
      return 1 + (idx-1)%10;
    row = idx - 60
    col = rand7()
    idx = col + (row-1)*7;
    if idx <= 20
      return 1 + (idx-1)%10;

推广一下,如果需要randN[1…N]生成randM[1…M]怎么做

def randM(n, m) {
   res, count = 0, 1
   tmp = n - 1
   while (tmp < m):
     tmp = tmp * n + n - 1 #首先判断出m可以由几位的n进制数组成
     count++;
   times = (tmp / m) * m
    
   while (res >= times):
     res = count > 1 ? (res % m) : 0
     offset = res? 1 : 0
     for i in range(count - offset):
         res = res * n + randN() - 1;
   return 1 + res % m;

Fisher-Yates洗牌算法

使用Fisher-Yates Shuffle算法,Fisher-Yates洗牌算法是用来打乱一个随机序列的算法,

主要步骤为:
在0到n(索引)之间生成一个数m,
交换m和n(索引对应的数),
n(索引)减掉1,
循环这三步,直到n等于0。
主要思想就是每次采样(索引)时,当前随机采样到的数(索引对应的数)交换到最后一个数(末尾索引对应的数),然后采样池数量减一(末尾索引减一),然后继续采样和交换(不断迭代),直到采样池为空。

382. 链表随机节点
(蓄水池抽样 随机 Random 细致注释~)
题目:给定一个单链表,随机选择链表的一个节点,并返回相应的节点值。保证每个节点被选的概率一样。
思路: 蓄水池抽样的套路,关键是理解:
if random.randint(1,count) == count: res = cur.val

count = 0 
cur  = self.head # cur为当前节点
while cur:
    count += 1
    # 等概率取样,每个样本被取到的概率都是1/count
    # 例如,count为1时,概率为1,即res的初值。count为2时,有1/2的几率选中2,如选中,2即为res,替换之前的res,以此类推。
    if random.randint(1,count) == count:
        res = cur.val
    cur = cur.next
return res

398. 随机数索引
题目:给定一个可能含有重复元素的整数数组,要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
思路:因为数组可能含有重复元素,为了等概率选取这个给定的数字,必须全部遍历一次。
首先,遍历数组,获得所有target的下标。
然后,随机输出,获取对应数字的index。

478. 在圆内随机生成点
题目:给定圆的半径和圆心的 x、y 坐标,写一个在圆中产生均匀随机点的函数 randPoint 。
思路1:本题的标签是“拒绝采样”,意在考察拒绝采样的方法,例如,从正方形中随机取点,然后拒绝圆外的点。
思路2:随机取得半径(radius * sqrt(random.random()))和弧度(2 * math.pi * random.random())的值,再计算出点的坐标。

  1. 用 Rand7() 实现 Rand10()
    题目:已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

思路:
方法1:直接使用random多快啊…不过,这是违规的…
方法1.1 return random.randint(1, 10) # 执行用时: 256 ms/ 内存消耗: 17.2 MB
方法1.2 return random.choice(rand7() * 7 + [8, 9, 10]) # 执行用时: 300 ms/ 内存消耗: 17.2 MB

方法2:小学奥数~~ 执行用时: 368 ms/内存消耗: 17.3 MB
使用7个符号等概率映射出十个数字,需要抛开1-7就是7个数字的想法~
取两次,m取1-5,直接作为数值1-5。n取1-6,按照奇偶性决定为m加0还是加5

方法3:套路(7进制)
方法3.1 两位 执行用时: 432 ms/ 内存消耗: 17.3 MB
使用7个数字表达出更多个数字,构造两位7进制,(rand7() - 1) * 7 + rand7() - 1,可以取得0-48之间的数字。
如得到0-39之间的数字,使用(num % 10 + 1)等概率映射出1-10.
如得到40-48之间的数字,重新选择…直到选择到0-39之间的数字。
方法3.2 三位 执行用时: 392 ms/ 内存消耗: 17.2 MB
使用7个数字表达出更多个数字,构造三位7进制,(rand7() - 1) * 49 +(rand7() - 1) * 7 + rand7() - 1,可以取得0-342之间的数字。
如得到0-339之间的数字,使用(num % 10 + 1)等概率映射出1-10.
如得到340-342之间的数字,重新选择…直到选择到0-339之间的数字。
使用两位7进制数字,需在48个数字中拒绝9个,即9/48的拒绝比例。使用三位7进制数字,仅需在342个数字中拒绝3个,即3/342(1/114)的拒绝比例,每次取数需调用rand7()三次并计算,结果显示测试时间为392 ms,优于使用两位7进制。

官网还有进一步的优化算法,思路都是最大化的利用得到的数字,尽量减少调用rand7()以及计算的次数。

528. 按权重随机选择
(随机 Random 二分查找 细致注释~)
题目: 给定一个正整数数组 w ,其中 w[i] 代表下标 i 的权重(下标从 0 开始),请写一个函数 pickIndex ,它可以随机地获取下标 i,选取下标 i 的概率与 w[i] 成正比。
思路:把概率分布函数转化为累计概率分布函数。然后通过随机数,进行二分查找。
比如,输入是[1,2,3,4],那么概率分布是[1/10, 2/10, 3/10, 4/10, 5/10],累积概率分布是[1/10, 3/10, 6/10, 10/10].总和是10。如果我们产生一个随机数,在1~10之中,然后判断这个数字在哪个区间中就能得到对应的索引。
对于输入[1,2,3,4],计算出来的preSum是[1,3,6,10],然后随机选一个s,然后查找s属于哪个区间

497. 非重叠矩形中的随机点
题目: 给定一个非重叠轴对齐矩形的列表 rects,写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。

710. 黑名单中的随机数
题目: 给定一个包含 [0,n) 中不重复整数的黑名单 blacklist ,写一个函数从 [0, n) 中返回一个不在 blacklist 中的随机整数。
思路: 共有N个数字,其中黑名单上有len(blacklist)个数字, 白名单上有N-len(blacklist)个数字. 为了可以使用random.randint(0, self.white_len - 1)随机取得white_len个白名单数字中的一个,使用映射关系处理前white_len个位置中不属于白名单中的数字.

519. 随机翻转矩阵
(随机 Random 一次v.s.多次/拒绝抽样 细致注释~)
题目:题中给出一个 n_rows 行 n_cols 列的二维矩阵,且所有值被初始化为 0。要求编写一个 flip 函数,均匀随机的将矩阵中的 0 变为 1,并返回该值的位置下标 [row_id,col_id];同样编写一个 reset 函数,将所有的值都重新置为 0。尽量最少调用随机函数 Math.random(),并且优化时间和空间复杂度。

思路1:拒绝采样/多次抽样 执行用时: 60 ms(99%)/ 内存消耗: 15.4 MB(30%)
随机选取数字作为一维数组的索引位置,使用集合记录翻转过的元素位置,如新选择的位置已经处理过,继续选数。

思路2:一次采样 执行用时: 60ms(99%)/ 内存消耗: 15.5 MB(15%)
方法同710。
比较下来,虽然方法2仅抽样一次,但为了实现仅需抽一次,增加了各种操作,时空复杂度和方法1差不多。

def flip(self):
	self.matrix_index -= 1 # 每次抽样后,样本总数减一
    # 随机选取数字作为一维数组的索引位置
    target = random.randint(0, self.matrix_index)
    # 如字target不在词典pair中,直接使用target(target_redirect=target)计算
   # 如target在词典pair中,使用其在pair中映射的值(target_redirect=pair[target])计算
   target_redirect = self.pair.get(target, target)
   # 返回结果前,把 target 映射到当前数组最后一个位置的"值/映射到的值(如有)"
   # 下一轮开始时matrix_index-1,样本数减一,没有机会选到matrix_index,。如再次抽到本轮中选中的数字target,就使用其映射在matrix_index的值
   self.pair[target] = self.pair.get(self.matrix_index, self.matrix_index)
   # 使用target_redirect计算出二维数组的坐标
   return [target_redirect // self.n_cols,  target_redirect % self.n_cols]

def reset(self):
    # 还原至init状态
    self.pair.clear()
    self.matrix_index = self.n_rows * self.n_cols

参考:https://blog.csdn.net/weixin_54955821/article/details/117715798

这篇关于随机数算法---蓄水池抽样算法,拒绝采样,Fisher-Yates洗牌算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!