为何维基百科称蓄水池抽样总体大小未知，而源码却依赖已知n？

为什么定义说“不知道n”，但示例代码却用了n？ #

这是算法演示和实际场景的差异，本质上没有矛盾。

示例代码是静态数组场景下的实现，写n只是为了用循环模拟“逐个处理数据”的流程——但在真实的流式场景（n未知、内存装不下全量数据）里，你根本不需要提前知道n的值：

• 只需要维护一个计数器i，每收到一个新元素就把i加1；
• 前k个元素直接放进蓄水池；
• 从第k+1个元素开始，每次生成1到i的随机数j，如果j≤k，就用当前元素替换蓄水池的第j个位置；
• 直到数据流结束，整个过程完全不需要知道总共有多少个元素。

代码里写n只是为了方便在静态数组上演示逻辑，让读者能看懂循环范围，算法的核心逻辑和“是否知道n”无关。

已知总体大小n时，还有哪些随机抽样方法？ #

当然有，这类方法因为能拿到全量数据或知道n，实现起来更简单：

• 无放回简单随机抽样：直接生成k个不重复的随机索引（1到n），取出对应元素。比如把数组洗牌后取前k个，或者用集合生成不重复随机数直到凑够k个。优点是实现简单，但需要内存能装下全量数据。
• 系统抽样：计算抽样间隔m = n/k，随机选一个起始位置（比如1到m之间的数），然后每隔m个元素取一个。比如n=100，k=10，间隔是10，随机选起始点3，就取3、13、23…93。
• 分层抽样：如果数据集能分成不同的组（比如按类别分层），先按每组的比例抽取对应数量的样本，再合并结果。适合数据有明显分组特征的场景。

翻译后的示例代码 #

(* S 是待抽样的数据集，R 存储抽样结果 *)
ReservoirSample(S[1..n], R[1..k])
  // 初始化蓄水池数组
  循环 i 从 1 到 k
      R[i] := S[i]
  结束循环

  // 以逐渐降低的概率替换蓄水池中的元素
  循环 i 从 k+1 到 n
    (* randomInteger(a, b) 生成 [a, b] 范围内的均匀随机整数 *)
    j := randomInteger(1, i)
    如果 j <= k
        R[j] := S[i]
    结束判断
  结束循环
结束函数

内容的提问来源于stack exchange，提问作者kyopa