蓄水池抽样

定义

蓄水池抽样(Reservoir Sampling)解决这样的问题:数据以流的形式到来、总量未知或极大,要求在只扫描一遍且内存有限的条件下,等概率地随机抽取 k 个元素。经典实现称 Algorithm R,由 Jeffrey Vitter 系统分析并推广。

原理

先把前 k 个元素放入"蓄水池";此后第 i 个元素(i > k)以 k/i 的概率被选中,并随机替换池中一个元素。可用归纳法证明任意时刻每个已到达元素留在池中的概率相同,均为 k/i。时间 O(n),空间 O(k)。Vitter 的 Algorithm X/Z 通过跳跃采样减少随机数调用次数。

应用

日志与点击流的在线抽样监控、大数据集的代表性子集抽取、流式机器学习、数据库近似查询,以及面试中"从链表随机取一个节点"类问题。

变体

带权蓄水池抽样(如 Efraimidis-Spirakis 算法)支持按权重抽样。