抽蓄水池（室内蓄水池）

       大家好！今天让小编来大家介绍下关于抽蓄水池（室内蓄水池）的问题，以下是小编对此问题的归纳整理，让我们一起来看看吧。

文章目录列表:

• 一、蓄水池抽水泵用多大
• 二、关于蓄水池抽水问题
• 三、分布式/并行蓄水池抽样 (Distributed/Parallel Reservoir Sampling)

一、蓄水池抽水泵用多大

二、关于蓄水池抽水问题

三、分布式/并行蓄水池抽样 (Distributed/Parallel Reservoir Sampling)

        一道电面题目, 分为两问:

        第一问是一个标准的水塘抽样算法(Reservoir Sampling)问题.

        算法思路: 维护一个大小为 M 的数组. 记当前接收的是第 N 个数据(从 1 开始).

        证明: 假设当前是第 M+1 个元素, 它被丢弃的概率是 1/(M+1) , 留下的概率就是 M/(M+1) . 对于已经在集合中的 M 个元素, 每个以 1/(M+1) 的概率被丢弃, 留下的概率也是 M/(M+1) .

        假设当前是第 M+2 个元素, 它被丢弃的概率是 2/(M+2) , 留下的概率是 M/(M+2) . 对于前 M+1 个元素, 它们在集合中的概率是 M/(M+1) (见上一个分析). 这一次, 它们每个被以 1/(M+2) 的概率被丢弃, 留下的概率就是 M/(M+1) * (M+1)/(M+2) = M/(M+2)

        依次类推, 到接受第 N 个元素时, 每个元素被抽取的概率就是 M/N .

        第二问就是分布式的蓄水池抽样问题了.

        算法思路是: 假设有 K 个机器, 每个机器维护大小为 M 的数组, 并记录该机器接受的数据总数 Ni .

        假设 Ni M : 因为第 i 个机器上数据的留存概率为 M/Ni , 而采样时又以 Ni/N 的概率抽取该机器, 又以 1/M 的概率等概率 不放回 地选取一个元素, 所以第 i 个机器上一个数据被抽中的概率为 M/Ni * Ni/N * 1/M = 1/N . 这样重复 M 次, 每个元素被抽取到的概率就是 M/N .

        假设 Ni =M 第 i 个机器上数据的留存概率为 1 , 采样时以 Ni/N 的概率抽取该机器, 又以 1/Ni 的概率等概率 不放回 地选取一个元素, 所以第 i 个机器上一个数据被抽中的概率为 1/N . 同样, 重复 M 次让每个元素被抽取到的概率为 M/N .

       以上就是小编对于抽蓄水池（室内蓄水池）问题和相关问题的解答了，抽蓄水池（室内蓄水池）的问题希望对你有用！