水塘抽样算法

从大量数据中随机选择样本的高效算法，适用于数据量巨大且未知的场景

30
3

1. 总体数据 (N)

就绪状态：请点击"开始演示"按钮

2. 水塘(样本) (k)

3. 随机选择判定

0
0 i = 1
水塘大小 (k)
3
当前位置 (i)
1
当前随机值 (r)
-
判定结果
-

算法原理

  1. 先将前k个元素放入"水塘"(样本集合)中
  2. 对于第i个元素(i > k)：
    • 生成一个0到i之间的随机整数r
    • 如果r < k（即r在0到k-1范围内），则用第i个元素替换水塘中第r个元素
    • 否则，该元素被忽略
  3. 处理完所有元素后，水塘中保留的就是随机选择的k个样本

处理步骤

演示尚未开始...

概率说明

每个元素被选中的概率均为 k/N，保证了抽样的公平性。

准备开始演示...