蓄水池抽样算法（Reservoir Sampling） 蓄水池抽样算法用于从包含未知大小 n 的数据流中随机抽取 k 个样本，使得每个元素被选中的概率均为 k/n 。该算法特别适用于内存有限、无法存储全部数据流的场景。 问题描述 假设数据流以序列形式依次到达（如日志文件、网络数据包），且 n 可能非常大或未知。需设计一个算法，在只遍历数据流一次的情况下，保证最终抽样的 k 个样本满足均匀随机性。 算法步骤（k=1 的特殊情况） 先考虑最简单的情形：从数据流中随机选取 1 个元素，要求每个元素被选中的概率相等。 初始化结果变量 reservoir ，用于存储当前选中的样本。 遍历数据流，对第 i 个元素（ i 从 1 开始计数）： 以概率 1/i 选择当前元素，替换 reservoir 中的值； 以概率 1 - 1/i 保留原有 reservoir 的值。 遍历完成后， reservoir 即为最终样本。 正确性证明（k=1） 当 i=1 时，选中第 1 个元素的概率为 1。 当 i=2 时，第 2 个元素被选中的概率为 1/2 ；第 1 个元素被保留的概率为 1 - 1/2 = 1/2 。 推广到第 i 个元素：其被选中的概率为 1/i ，且需在后续所有步骤中不被替换。对于第 j 个元素（ j > i ），它不被第 j 个元素替换的概率为 1 - 1/j 。因此，第 i 个元素最终被保留的概率为： \[ \frac{1}{i} \times \frac{i}{i+1} \times \frac{i+1}{i+2} \times \cdots \times \frac{n-1}{n} = \frac{1}{n} \] 所有元素的概率均为 1/n ，满足均匀随机抽样。 推广到 k≥1 的一般情况 初始化一个大小为 k 的数组 reservoir[] ，存入数据流的前 k 个元素。 从第 k+1 个元素开始遍历（设当前元素索引为 i ）： 随机生成一个整数 r ，范围在 [ 0, i-1] （即 0 ≤ r ≤ i-1 ）。 若 r < k ，则用第 i 个元素替换 reservoir[r] ；否则保留 reservoir 不变。 遍历完成后， reservoir[] 中的 k 个元素即为抽样结果。 正确性分析（k≥1） 对于前 k 个元素：它们被选入初始水库的概率为 1。当处理第 i 个元素（ i > k ）时，每个元素被替换的概率为 k/i ，因此前 k 个元素最终保留的概率需计算其不被后续任何元素替换的概率： \[ \prod_ {j=k+1}^{n} \left(1 - \frac{k}{j} \cdot \frac{1}{k}\right) = \prod_ {j=k+1}^{n} \frac{j-1}{j} = \frac{k}{n} \] 对于第 i 个元素（ i > k ）：其被选入水库的概率为 k/i ，且需在后续步骤中不被替换。最终保留的概率为： \[ \frac{k}{i} \times \prod_ {j=i+1}^{n} \left(1 - \frac{k}{j} \cdot \frac{1}{k}\right) = \frac{k}{i} \times \frac{i}{n} = \frac{k}{n} \] 因此所有元素被选中的概率均为 k/n 。 应用场景与优势 数据流处理 ：如从大规模日志中随机抽样分析。 内存效率 ：仅需 O(k) 的额外空间，无需提前知道 n 。 扩展性 ：可并行化处理（如分块抽样后合并）。 此算法通过巧妙的概率设计，在单次遍历中实现了均匀抽样，是处理流式数据的经典随机化算法。