蓄水池抽樣算法（Reservoir Sampling）
應(yīng)用場景: 蓄水池抽樣一般用于海量數(shù)據(jù)不知道總數(shù)只能遍歷一次隨機(jī)抽樣問題熙含。
主要強(qiáng)調(diào)：
- 數(shù)據(jù)流長度N很大且不可知罚缕，所以不能一次性存入內(nèi)存。
- 時(shí)間復(fù)雜度為O(N)怎静。
- 隨機(jī)選取m個(gè)數(shù)邮弹，每個(gè)數(shù)被選中的概率為m/N。
分布式蓄水池抽樣（Distributed/Parallel Reservoir Sampling）
應(yīng)用場景：一塊CPU的計(jì)算能力再強(qiáng)蚓聘，也總有內(nèi)存和磁盤IO拖他的后腿腌乡。因此為提高數(shù)據(jù)吞吐量，分布式的硬件搭配軟件是現(xiàn)在的主流或粮。如果遇到超大的數(shù)據(jù)量导饲，即使是O(N)的時(shí)間復(fù)雜度，蓄水池抽樣程序完成抽樣任務(wù)也將耗時(shí)很久。因此分布式的蓄水池抽樣算法應(yīng)運(yùn)而生渣锦。
作者：邱simple
鏈接：http://www.reibang.com/p/7a9ea6ece2af
來源：簡書
著作權(quán)歸作者所有硝岗。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處袋毙。
參考資料：
