儲水池抽樣演算法原理與實現
記得在實習那會，涉及到抽獎的解決方案，即一天以k/n的概率中獎，要求給出簡單高效的演算法，其中n只有在結束時才知道。換言之，題意即為如何從未知或者很大樣本n空間中隨機地取k個數，保證每個被取到的概率為n/k。解決此題的很好方法就是儲水池演算法Reservoir Sampling Algorithm。
儲水池演算法應用的前提條件是樣本空間總數未知或很大。若當前的樣本數為m，則以k/m的概率保留每一個樣本……直到最終樣本數為n時是的每一個被選中的概率為k/n，缺陷是不到最後不知道哪些樣本要被選中。這樣問題就來了，為何不在最終結果n出來時再來隨機抽取k個樣本，保證概率為k/n呢？其實這種想法有些時候是不可行的，數據是動態增長的，可能緩存系統存儲不了所有的樣本信息，但卻足夠存儲k個樣本的信息，即空間複雜度可以從O(n)降到O(k)，k相對n來說是非常小的。所以儲水池演算法還是很有應用價值的。
Advertisements
下面說說儲水池演算法的原理及實現。先把前k個數放入蓄水池；對第k+1個樣本，以k/(k+1)概率決定換入蓄水池，換入時又隨機選取池裡的一個樣本作為替換項……，對應第i個樣本（i>k）,以k/i的概率留下，然後隨機從池裡選中一個替換掉……這樣一直做下去，對於任意的樣本空間n，對單個樣本的選取概率為k/n。證明過程如下：
此演算法時間複雜度為O(n)，空間複雜度為O(k)，能夠處理樣本空間總數未知或很大的情況，不失為一種比較好的方法。關於儲水池演算法，在分散式系統上有著應用，在此提供一下豐富眼界的鏈接，儲水池演算法的拓展。
由於工作原因，Java對於我來說似乎比C/C++更重要一點，所有以後的代碼盡量用Java給出，直接上源代碼的。
Advertisements
import java.util.Random;
publicclass ReservoirSampling {
privateint m_nChoice;
privateint [] m_arrayChoice;
privateint m_nNowNumber;
private Random m_Rand =new Random(System.currentTimeMillis());
public ReservoirSampling(int k)
{
m_nNowNumber = 0;
m_nChoice = k;
m_arrayChoice = newint [k];
}
publicvoid AdjustChoice()
{
if(m_nNowNumber < m_nChoice)
{
m_arrayChoice [m_nNowNumber] = m_nNowNumber;
}
else
{
int id = m_Rand.nextInt(m_nNowNumber + 1);
if(id < m_nChoice)
{
m_arrayChoice [id] = m_nNowNumber;
}
}
++ m_nNowNumber;
}
publicvoid ShowChoice()
{
for( int i = 0; i <m_arrayChoice.length ; ++ i)
{
if(i != 0 && i % 10 == 0)
System.out.println();
System.out.print(1 + m_arrayChoice [i] + " ");
}
}
publicstaticvoid main(String agr[])
{
System.out.println("My Java program!");
ReservoirSampling test = new ReservoirSampling(20);
for( int i =0 ;i < 200 ; ++ i)
{
test.AdjustChoice();
}
test.ShowChoice();
}
}
由於時間和水平的原因，難免有不足的地方，歡迎斧正！
原創作品，出自 「曉風殘月xj」 博客，歡迎轉載，轉載時請務必註明出處（http://blog.csdn.net/xiaofengcanyuexj）。
由於各種原因，可能存在諸多不足，歡迎斧正！