随机算法--水塘抽样和洗牌算法

1 水塘抽样

如果数组以文件形式存储（读者可假设构造函数传入的是个文件路径），且文件大小远超内存大小，我们是无法通过读文件的方式，将所有下标保存在内存中的，因此需要找到一种空间复杂度更低的算法；当内存无法加载全部数据时，如何从包含未知大小的数据流n中随机选取k个数据，并且要保证每个数据被抽取到的概率相等。
该抽样方法能通过时间换空间解决上述的困难。
考虑情况：

1.1 k = 1

我们知道如果要保证所有的数被抽到的概率相等，那么每个数抽到的概率应该为1/k 。
那我们可以这样做：
遇到第1个数 n1的时候，我们保留它，概率为1.
遇到第2个数n2的时候，我们以 1/2的概率保留它
遇到第3个数n3的时候，我们以1/3的概率保留它:
$P(n_1) = P(n_2) = \frac12 * (1 - \frac13) = \frac13$
……
遇到第i个数ni的时候，我们以 $\frac1n$ 的概率保留它，那么
$P(n_1) = P(n_2) = ...= P(n_{i-1}) = \frac1{i-1} * (1 - \frac1i) = \frac1i$
这样就可以看出，对于k=1的情况，我们可以制定这样简单的抽样策略：
数据流中第i个数被保留的概率为 1/i 。只要采取这种策略，只需要遍历一遍数据流就可以得到采样值，并且保证所有数被选取的概率均为 1/i 。

1.2 k > 1

对于k>1的情况，我们可以采用类似的思考策略：
仍然假设数据流中含有n个数，那么要保证所有的数被抽到的概率相等，每个数被选取的概率必然为 $\frac{k}n$ 。
对于前k个数，我们全部保留下来，则 $P(n_1) = P(n_2) = P(n_k) = 1$
对于第k+1个数 $n_{k+1}$ ，我们以 $\frac{k}{k+1}$ 的概率保留它（这里只是指本次被保留下来），那么前k个数中的被保留的概率可以这样表示：
$P(n_1) = P(n_2) = ... = P(n_k) = 1 * (\frac1{k+1} + \frac{k}{k+1} * \frac{k-1}{k}) = \frac{k}{k+1}$ ，
对于第k+2个数，我们以 $\frac{k}{k+2}$ 的概率保留它（这里只是指本次被保留下来），那么前k个被保留下来的数中的
被保留的概率为
$P(n_1) = P(n_2) = ... = P(n_k) = \frac{k}{k+1}* (\frac2{k+2} + \frac{k}{k+2} * \frac{k-1}{k}) = \frac{k}{k+2}$
……
对于第i（i>k）个数，我们以的概率保留它，前i-1个数中的被保留的概率为
$P(n_1) = P(n_2) = ... = P(n_k) = \frac{k}{i-1}* (\frac{i-k}{i} + \frac{k}{i} * \frac{k-1}{k}) = \frac{k}{i}$
这样，我们可以制订策略：
对于前k个数，我们全部保留，对于第i（i>k）个数，我们以 k/i的概率保留第i个数，并以 1/k的概率与前面已选择的k个数中的任意一个替换。

2 Fisher-Yates 洗牌算法

对于1个含n个无重复元素的数组或列表，对于 [0, n -1] 范围内的每个下标为i 的元素，从下标范围 [i, n-1] 中，随机选出1个下标为k 的元素，与下标为i 的元素交换。遍历数组或列表，对数组或列表中的每个元素执行步骤1。数组遍历完成，即完成 “洗牌”。

具体来说，我们先在0 ~ n-1中随机选一个坐标，将它作为第一个，和第一个交换位置；（每个数被选到的概率是1/n）
剩下的n-1个数里，继续随机一个1 ~ n-1的坐标，将它作为第二个，和第二个交换位置；(每个数被选到的概率为第一次没被选到且第二次被选到
(n/n−1)∗ (1/n−1)= 1/n )

nums = [1, 2, 3, 4, 5]
for i in range(len(nums)):
    # 随机选出第i个位置的数
    idx = randint(i, len(nums) - 1)
    # 交换 i和idx，即随机选出了第i个数
    nums[i], nums[idx] = nums[idx], nums[i]
print(nums)

最后编辑于：2024.11.19 23:57:10