大家好！今天讓小編來(lái)大家介紹下關(guān)于抽蓄水池（室內蓄水池）的問(wèn)題，以下是小編對此問(wèn)題的歸納整理，讓我們一起來(lái)看看吧。

文章目錄列表:

• 一、蓄水池抽水泵用多大
• 二、關(guān)于蓄水池抽水問(wèn)題
• 三、分布式/并行蓄水池抽樣 (Distributed/Parallel Reservoir Sampling)

一、蓄水池抽水泵用多大

二、關(guān)于蓄水池抽水問(wèn)題

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

        一道電面題目, 分為兩問(wèn):

        第一問(wèn)是一個(gè)標準的水塘抽樣算法(Reservoir Sampling)問(wèn)題.

        算法思路: 維護一個(gè)大小為 M 的數組. 記當前接收的是第 N 個(gè)數據(從 1 開(kāi)始).

        證明: 假設當前是第 M+1 個(gè)元素, 它被丟棄的概率是 1/(M+1) , 留下的概率就是 M/(M+1) . 對于已經(jīng)在集合中的 M 個(gè)元素, 每個(gè)以 1/(M+1) 的概率被丟棄, 留下的概率也是 M/(M+1) .

        假設當前是第 M+2 個(gè)元素, 它被丟棄的概率是 2/(M+2) , 留下的概率是 M/(M+2) . 對于前 M+1 個(gè)元素, 它們在集合中的概率是 M/(M+1) (見(jiàn)上一個(gè)分析). 這一次, 它們每個(gè)被以 1/(M+2) 的概率被丟棄, 留下的概率就是 M/(M+1) * (M+1)/(M+2) = M/(M+2)

        依次類(lèi)推, 到接受第 N 個(gè)元素時(shí), 每個(gè)元素被抽取的概率就是 M/N .

        第二問(wèn)就是分布式的蓄水池抽樣問(wèn)題了.

        算法思路是: 假設有 K 個(gè)機器, 每個(gè)機器維護大小為 M 的數組, 并記錄該機器接受的數據總數 Ni .

        假設 Ni M : 因為第 i 個(gè)機器上數據的留存概率為 M/Ni , 而采樣時(shí)又以 Ni/N 的概率抽取該機器, 又以 1/M 的概率等概率 不放回 地選取一個(gè)元素, 所以第 i 個(gè)機器上一個(gè)數據被抽中的概率為 M/Ni * Ni/N * 1/M = 1/N . 這樣重復 M 次, 每個(gè)元素被抽取到的概率就是 M/N .

        假設 Ni =M 第 i 個(gè)機器上數據的留存概率為 1 , 采樣時(shí)以 Ni/N 的概率抽取該機器, 又以 1/Ni 的概率等概率 不放回 地選取一個(gè)元素, 所以第 i 個(gè)機器上一個(gè)數據被抽中的概率為 1/N . 同樣, 重復 M 次讓每個(gè)元素被抽取到的概率為 M/N .

       以上就是小編對于抽蓄水池（室內蓄水池）問(wèn)題和相關(guān)問(wèn)題的解答了，抽蓄水池（室內蓄水池）的問(wèn)題希望對你有用！