不知道数据总量也能均匀抽样：蓄水池算法辟谣

流式日志长度未知时先统计总量再随机下标并不是唯一办法。本文用反直觉概率推导蓄水池抽样第 i 个元素以 k/i 的概率进入容量 k 的样本并随机替换旧元素Python 完整代码使用可注入随机源验证确定性输出、样本大小和输入不足时的行为。“要均匀抽样必须先知道总记录数”听起来合理却不适用于无法回放的日志流。容量为 k 的蓄水池先保留前 k 个元素看到第 i 个元素时以 k/i 的概率让它进入样本并随机替换池中一个位置。新元素会获得机会旧元素也不是永久安全。正是这种看似残酷的持续替换让流结束时每个元素概率完全相同。辟谣一未知总量不妨碍均匀对从一开始计数的第 i 个元素随机生成[0,i-1]的整数 j。若 jk就用当前元素替换 reservoir[j]否则忽略。因为 j 落在前 k 个位置的概率是 k/i新元素入选概率正确。它若入选每个槽位被选作替换位置的概率相同因此池中没有位置偏好。前 k 个元素直接装入相当于当 ik 时入选概率为一。第 i 个元素凭什么有 k/i 机会考虑任意早期元素 x。在处理到第 i 步前归纳假设它留在池中的概率为 k/(i-1)。第 i 个新元素替换 x 的概率是新元素入池 k/i再在 k 个槽位中选中 x即 1/i。因此 x 本轮存活概率为(k/(i-1))*(1-1/i)k/i。新元素本身入池概率也是 k/i。于是处理完 i 个元素后前 i 个元素的保留概率完全一致。被选中后为何还会被换掉容量三流为 0 到 9。前三个元素先占满样本从第四个元素开始每个新元素可能替换一个旧槽位也可能被忽略。示例使用固定随机种子所以输出可复现但固定种子只为测试不代表生产抽样必须得到某个具体集合。断言重点检查样本大小、元素来自原流、同一输入与同一种子结果相同以及输入少于 k 时完整返回。用归纳算清每个元素的命运归纳证明给出了边际均匀性处理 n 个元素后每个元素进入容量 k 样本的概率为 k/n。算法始终只保存至多 k 个元素因此适合未知长度单遍流。若要求带权概率、分层配额或时间衰减普通蓄水池不再满足需求需要使用带权蓄水池、分层抽样或滑动时间窗口不能通过修改替换概率凭感觉扩展。在线日志抽样的工程边界随机源应通过参数注入测试使用固定种子生产使用合适的系统随机源或统一伪随机策略。并行分片各自抽样后直接拼接并不均匀合并时要考虑每个分片的总量与权重。日志隐私同样重要均匀抽样可能把低频敏感记录保留下来进入样本前仍需脱敏和字段白名单。监控应记录已见元素数、样本容量和算法版本。完整可运行代码importrandomdefreservoir_sample(iterable,k,rngNone):ifk0:raiseValueError(k must be non-negative)rngrngorrandom.Random()reservoir[]fori,iteminenumerate(iterable):ifik:reservoir.append(item)elifk0:jrng.randrange(i1)ifjk:reservoir[j]itemreturnreservoirif__name____main__:areservoir_sample(range(10),3,random.Random(7))breservoir_sample(range(10),3,random.Random(7))assertabassertlen(a)3andset(a)set(range(10))assertreservoir_sample([4,5],5,random.Random(1))[4,5]assertreservoir_sample(range(5),0,random.Random(1))[]print(a)print(reservoir tests passed)随机下标与替换位置enumerate的 i 从零开始所以当前是第 i1 个元素随机范围必须是range(i1)。只有 jk 才替换对应 k/(i1) 的入选概率。k 为零时仍可单遍消费输入但不调用随机源。函数接受任意可迭代对象不读取长度也不回放符合流式约束。从边际均匀到联合分布证明每个元素进入样本的概率相同只说明边际均匀标准蓄水池还保证最终样本是所有大小 k 子集中的均匀选择。可以用归纳理解处理第 i 个元素时它以 k/i 进入并等概率替换一个旧位置任何包含新元素的 k 子集都由上一步对应的 k-1 个旧元素加上新元素产生概率一致不含新元素的子集则在本轮不替换时保留概率也与前者相等。统计测试只能发现明显偏差不能替代理论证明。可以在 n5、k2 时重复运行统计十个可能子集的频率并做卡方检查样本次数有限时频率必然波动阈值应依据显著性水平而不是肉眼要求完全一致。单元测试更适合验证边界和确定性分布测试应单独标记为较慢测试避免在普通持续集成中偶发失败。如果每条记录有权重目标可能是权重越大入选概率越高。此时可为元素生成与权重相关的随机键并维护前 k 个键不能简单重复元素若干次因为权重可能是小数且流量巨大。时间窗口抽样又要求过期旧元素普通蓄水池无法删除不知道是否仍代表总体的历史记录。先写清总体是“从启动至今”“最近一小时”还是“每个租户各自”再选择相应算法均匀二字才有可验证含义。概率实验应该怎样设容差取 n5、k1 重复抽样十万次五个位置理论频率均为二成。可以使用卡方统计或给每个频率设置基于标准差的宽松区间测试种子固定以便复现不要要求每个位置出现次数完全相同。k2 时统计十种二元素子集能发现只保证单元素边际却破坏联合均匀的错误实现。统计测试属于算法审计而非普通单元测试日常持续集成保留边界断言慢速分布实验定期运行并记录随机种子与样本次数。进一步推导练习令容量为一流长度从一逐步增长到四画出第一个元素每轮的存活概率一、二分之一、三分之一、四分之一。再令容量为二对任意一个旧元素计算第三个元素到来时被替换的概率。最后考虑两个长度不同的分片各自抽一条后直接二选一证明这种合并会偏向短分片从而理解为什么并行合并必须携带已见总量。复杂度分析处理 n 个元素时间 O(n)样本空间 O(min(k,n))每个元素只访问一次。随机数生成视为常数成本。若最终还要按某字段排序样本会增加 O(k log k)但不影响抽样均匀性。对无限流算法不会自然结束需要由时间、记录数或外部取消信号决定何时读取当前样本。边界条件k 不能为负k 为零返回空输入少于 k 时返回全部输入输入可为空重复值按记录位置而非值去重每个出现位置拥有相同机会。随机源对象不能在并发线程中无保护共享。若需要密码学不可预测抽样应更换随机源。常见错误随机范围写成randrange(i)会漏掉当前计数端点用jk造成越界和概率偏差每次从完整历史重选失去 O(k) 空间优势只测试一个固定输出而不验证性质并行分片样本直接等权拼接把相同值去重后再抽样改变了记录级概率。可复制的测试用例运行会先打印固定种子得到的三元素列表再打印reservoir tests passed。断言验证可复现、样本合法、短输入和零容量。统计性质测试可重复十万次容量一的抽样观察各位置频率接近但只能设置容差不能要求完全相等或把一次实验频率当成理论证明。上线前复核清单**计数**第 i 个元素的公式要与代码的零基 enumerate 对齐。**随机**测试固定种子生产不要依赖固定输出。**重复**算法对记录位置均匀不自动对值去重。**并行**分片合并必须按已见数量加权。**隐私**进入样本前执行与全量日志相同的脱敏规则。总结蓄水池抽样反直觉的地方是旧元素随时可能被换走但每一步恰好把所有已见元素的保留概率重新拉平。一次单遍、固定容量、未知总量仍能均匀抽样靠的不是运气而是一条可以逐步验证的概率不变量。