蓄水池抽样算法（Reservoir Sampling） 蓄水池抽样算法是一种用于从数据流中随机抽取k个样本的算法，特别适用于数据总量未知或无法一次性加载到内存的情况。该算法保证每个元素被选中的概率相等。 问题描述 假设有一个数据流（数据只能顺序访问一次，且总数量n未知），需要从中均匀随机抽取k个元素（k≤n）。即每个元素被选中的概率均为k/n。 算法思路 初始化一个大小为k的"蓄水池"（数组），保存当前已选中的样本。 依次处理数据流中的每个元素： 对于前k个元素，直接放入蓄水池。 对于第i个元素（i>k），以概率k/i决定是否将其替换蓄水池中的某个元素。 替换时，从蓄水池中均匀随机选择一个位置进行替换。 详细步骤 初始化蓄水池 ：读取数据流的前k个元素，直接存入蓄水池数组 reservoir[0..k-1] 。 处理后续元素 ： 从第k+1个元素开始（索引为k），遍历到第n个元素（索引为n-1）。 对于第i个元素（i从k到n-1），生成一个随机整数j，范围在[ 0, i-1 ]内。 若j < k，则用第i个元素替换 reservoir[j] ；否则忽略该元素。 结束 ：遍历完成后，蓄水池中的k个元素即为均匀随机抽样的结果。 概率分析 对于前k个元素 ：每个元素在初始时被选中的概率为1。处理第k+1个元素时，每个前k元素被替换的概率为 k/(k+1) * 1/k = 1/(k+1) ，因此保留概率为 1 - 1/(k+1) = k/(k+1) 。依此类推，到处理第n个元素时，前k个元素的保留概率为： k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n = k/n 。 对于第i个元素（i>k） ：该元素被选入蓄水池的概率为 k/i 。之后不被后续元素替换的概率为： i/(i+1) * (i+1)/(i+2) * ... * (n-1)/n = i/n 。 因此第i个元素最终留在蓄水池的概率为 (k/i) * (i/n) = k/n 。 示例 假设k=2，数据流为[ 1,2,3,4,5 ]： 初始化蓄水池为[ 1,2 ]。 处理第3个元素（3）： 生成随机数j∈[ 0,2]，若j<2（概率2/3），则替换 reservoir[j] 。 假设j=0，蓄水池变为[ 3,2 ]。 处理第4个元素（4）： 生成j∈[ 0,3]，若j<2（概率2/4），替换 reservoir[j] 。 假设j=1，蓄水池变为[ 3,4 ]。 处理第5个元素（5）： 生成j∈[ 0,4]，若j<2（概率2/5），替换 reservoir[j] 。 假设j=1，蓄水池变为[ 3,5 ]。 最终每个元素被选中的概率均为2/5。 应用场景 从大规模日志中随机抽样分析。 在无法预知数据总量的情况下进行随机采样（如网络数据流）。