最近做数据库作业,需要对几个 G 的数据进行抽样,比如抽 100 万行,需要边扫边抽样,不能存储所有的行之后再抽样。

那如何进行抽样才能让每行抽到的概率相等呢?

做法很简单,假设一共需要抽样 s 行,当前扫描到了第 n 行(n 从 1 开始),那么

1、若 n \le s,则直接加入到抽样数组中
2、否则以 s / n 的概率,随机替换掉抽样数组中的某个元素

为什么这是正确的呢?

我们直接来分析每个元素被抽到的概率(不妨假设总行数 t 大于等于 s

n \ (n < s) 行最终抽到的概率为

\begin{aligned}
& \prod_{m = s +1}^{t} \left[ (1 - \frac{s}{m}) + \frac{s}{m}  \left(1 - \frac{1}{s} \right) \right]
\\ = & \prod_{m = s +1}^{t} \frac{m - 1}{m}
\\ = & \frac{s}{s+1} \frac{s+1}{s+2} \cdots \frac{t-1}{t}
\\ = & \frac{s}{t}
\end{aligned}

n \ (n \ge s) 行最终抽到的概率为

\begin{aligned}
& \frac{s}{n} \prod_{m = n +1}^{t} \left[ (1 - \frac{s}{m}) + \frac{s}{m}  \left(1 - \frac{1}{s} \right) \right]
\\ = & \frac{s}{n} \prod_{m = n +1}^{t} \frac{m - 1}{m}
\\ = & \frac{s}{n} \frac{n}{n+1} \frac{n+1}{n+2} \cdots \frac{t-1}{t}
\\ = & \frac{s}{t}
\end{aligned}

1 条评论

欢迎留言>_<

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据