池塘抽样法（水塘抽样）如何应用均等概率随机算法？

本文共计597个文字，预计阅读时间需要3分钟。

关联主题+链表随机节点+一般语言提供随机函数可实现数值的平均概率取值，但需考虑本主题的链表无法直接标记，若想直接使用下标，必然要花费空间存储数组。类推，如果...

关联题目 链表随机节点
一般语言提供了随机函数可以实现数的均等概率取，但是要考虑到本题目的链表无法直接标记，如果想直接使用下标,必然要花费空间存入数组。类推，如果是一个很大的文本流，无法在内存打开，那该如何是好？
于是，我们引入池塘抽样法（又称水塘抽样）

池塘抽样法

从S中抽取首k项放入「水塘」中
对于每一个S[j]项（j ≥ k）：
随机产生一个范围从0到j的整数r
若 r < k 则把水塘中的第r项换成S[j]项

用枚举数组S{1，2，3}来帮助理解：

1. 当遍历到S[1]时，概率为1，只有一个数那肯定不存在均等的概念
2. S[2]时，有两个数，那么使用随机函数(这里假定是rand，根据自己语言确定),rand(1)[表示在0-1随机取]，如果取到0则保留当前值S[2]，概率是1/2（rand（0））概率。如果取不到则保留原答案，由1.可知之前值只有S[1]，且概率为1，则此时取S[1]的概率为1 X 1/2。这是的S[1],S[2]的概率均等，都为1/2
3. S[3]时，有三个数，使用函数rand(2),取0时保留S[3]，概率为1/3。否则保持原答案，由2. 可得，S[1],S[2]原保留概率均为1/2，此时如果S[3]未选，则S[1],S[2]保留概率为1/2 X 2/3 = 1/3 ，此时三个数的取值概率均为1/3，遍历结束，得到随机值

代码：

for i, num := range S {//遍历S if rand.Intn(i + 1) == 0 {//随机数（当前是第几个数就是随机几个数）等于0 ans = i//保留答案 } }