一、問題由來

????? 這個題目的由來是在《編程珠璣》里遇到的故記錄一下。還可以這么說”如何從二進制文件中等概率取整數”或者”在不知道文件總行數的情況下如何從文件中隨機的抽取一行?”這個題目說的有點不清楚實際上是一個二進制文件中有好多好多整數你要隨機取出一個。

????? 這個問題的難點就在于你開始不知道有多少的整數也就是說這個1/n你不知道n是多少。???

????? 綜上隨機抽樣問題表示如下要求從N個元素中隨機的抽取k個元素其中N無法確定。

????? 這種應用的場景一般是數據流的情況下由于數據只能被讀取一次而且數據量很大并不能全部保存因此數據量N是無法在抽樣開始時確定的但又要保持隨機性于是有了這個問題。所以搜索網站有時候會問這樣的問題。

????? 這里的核心問題就是“隨機”怎么才能是隨機的抽取元素呢我們設想買彩票的時候由于所有彩票的中獎概率都是一樣的所以我們才是“隨機的”買彩票。那么要使抽取數據也隨機必須使每一個數據被抽樣出來的概率都一樣。

二、算法實現

?

array R[k]; // resultinteger i, j;for each i in 1 to k doR[i] := S[i]done;for each i in k+1 to length(S) doj := random(1, i); // important: inclusive rangeif j <= k thenR[j] := S[i]fidone

?

總結

以上是生活随笔為你收集整理的海量数据处理之蓄水池抽样算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。