水庫(kù)抽樣算法是一個(gè)典型的空間亞線性算法。

在很多時(shí)候我們要在海量數(shù)據(jù)中進(jìn)行均勻的抽樣，由于我們要取樣的是海量數(shù)據(jù)，以至于只能讓這些數(shù)據(jù)從我們面前流過(guò)一次。

水庫(kù)抽樣的要求是，每一時(shí)刻取到的樣本都是前面已經(jīng)流過(guò)的全部數(shù)據(jù)的均勻抽樣。

例如：連續(xù)輸入一組未知大小的數(shù)據(jù)，輸出這組數(shù)據(jù)的k個(gè)均勻抽樣。要求：輸入到前n(n>k)個(gè)數(shù)據(jù)時(shí)，保存已經(jīng)輸入的數(shù)據(jù)的k個(gè)均勻抽樣。

1.申請(qǐng)長(zhǎng)度為k的數(shù)組A保存抽樣(此處下標(biāo)用1~k表示)；

2.首先保存接收到的前k個(gè)數(shù)據(jù)；

3.當(dāng)接收到第i個(gè)數(shù)據(jù)t時(shí)，生成[1,i]間的隨機(jī)數(shù)j,若j<=k,則以t替換A[j]。

算法的關(guān)鍵在第三步，每當(dāng)新來(lái)元素t時(shí)，生成隨機(jī)數(shù)，一旦隨機(jī)數(shù)落在數(shù)組范圍之內(nèi)，就替換掉。

算法原理：

對(duì)于每個(gè)新到來(lái)的元素i，它是以k/i的概率被收入集合的，因?yàn)樯傻碾S機(jī)數(shù)范圍是[1,i]，而當(dāng)數(shù)字小于等于k時(shí)，才會(huì)被替換進(jìn)數(shù)組A。

當(dāng)?shù)趇+1個(gè)元素到來(lái)時(shí)，第i+1個(gè)元素被替換進(jìn)數(shù)組的概率是Pi=k/(i+1)，而此時(shí)，前一個(gè)元素i被從中替換出來(lái)的概率為Po=1/k。則當(dāng)?shù)趇+1個(gè)元素到來(lái)時(shí)第i個(gè)元素被替換出去的概率為Pi*Po，那么沒(méi)有被替換出來(lái)的概率為p=1-Pi*Po=1-1/(i+1)。

那么當(dāng)?shù)趇+2,i+3...個(gè)元素到來(lái)時(shí)，第i個(gè)元素沒(méi)有被替換出來(lái)的概率為1-1/(i+2)，1-1/(1+3)...

那么當(dāng)元素i被選入集合中，并且在后面的所有的替換中都沒(méi)有被替換出來(lái)的概率：

這樣便得到，對(duì)于任意一個(gè)元素i，其被選入樣本的概率均為k/n，也就是說(shuō)它符合隨機(jī)抽樣。