轉(zhuǎn)載自? ?這是一個驚艷了我的算法題

Reservoir Sampling( Reservoir sampling )?

這是我在今年求職過程中面試的時候被問到的，因?yàn)橹昂苌俳佑|Streaming的算法，在聽到這個題目的時候被驚呆了，根本不能理解： ?

給一個Streaming的Data，未知長度，要求在Streaming結(jié)束后返回N個Data，且是等概率的。 ?

在聽到這個問題的時候簡直驚呆了。如果Streaming長度已知為L，當(dāng)然對于每一個Data，我生成一個N/L的概率即可。但是長度未知，也即概率未知，怎么可能在Data來的時候判斷要不要保留這個Data，還能保證是等概率的……百思不得其解。 ?

事后一番研究，才發(fā)現(xiàn)了這類算法，算法之簡單令人驚嘆： ?

首先保留前N個Data，對于后面來的Data以N/i的概率選擇是否保留，i為當(dāng)前Data序號，保留的話在原來保留的N的Data中隨機(jī)剔除一個。最后返回這N的即可。 ?

證明也很容易，奇妙得地方在于在計算概率的時候，出現(xiàn)了很長的，可以前后上下不斷約掉的分式。相互約去之后剩下的概率剛好是N/L，L為總長度。簡直美妙極了！?

顯然這類算法也非常有用，因?yàn)樵趯?shí)際問題中會出現(xiàn)大量需要在Streaming的數(shù)據(jù)中進(jìn)行Sample，為下一步處理數(shù)據(jù)做準(zhǔn)備的情形。而這竟然有一個O(L)的算法，真是太驚艷了！

總結(jié)

以上是生活随笔為你收集整理的Streaming的算法Reservoir Sampling的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。