水塘抽樣（Reservoir sampling）

貓和桃子去吃回轉壽司。桃子讓貓從轉盤上随機取下k個碟子。貓應該怎麼做？

已知：

1、貓和桃子坐在最上遊的位置，從廚房伸出來的傳送帶會在第一時間把廚師做好的壽司送到他們面前。

2、從貓眼前經過的壽司如果不被貓取下來，則會被坐在下家的兔子們吃光，而不會再轉回來。（每個壽司隻經過一次）

3、桌子上隻能容納下k個碟子。

4、如果取下的壽司沒有被吃過，可以被重新放回去。

5、雖然廚師已經停止生産新的壽司了，但是傳送帶在廚房裡的部分很長，貓不知道已經生産了多少壽司。（為了讨論友善，設一共N碟壽司，并且N≥k）

6、貓腦袋可以生成随機數。

Ok，以上表述純粹是好玩。實際上是做這樣一件事情：

從包含N個項目的集合S中随機選取k個樣本，其中N為一很大、未知的數量，以至于不能把所有N個項目都存放到主記憶體。要求隻對N周遊一次。

Jeffrey Scott Vitter在其論文[1]中提出了該問題并給出了一個精妙的算法：

1、把桌子清空，留出編号為1~k的k個位置存放壽司。

2、把前k個（第1~k個）壽司分别放在1~k号位置。

3、當第j個壽司經過面前時（k+1≤j≤N），貓腦袋生成一個1~j之間的随機整數r。

4、若r≤k，則把桌子上r号位置的壽司替換為目前（第j個）壽司；否則不操作。

5、如此（3、4步驟）直至所有壽司在貓面前經過。

這個算法的規範描述及其證明[2][3]并不複雜。我們可以計算傳送帶上第i個壽司最終被選取的機率P(i)，說明P(i)=k/N，進而證明該算法：

如果i≤k，則一開始它就被放在了桌子上，對它産生“威脅”的壽司是第k+1~N個壽司。第j（k+1≤j≤N）個壽司把它替換掉的機率為1/j，即“安全”的機率為(j-1)/j。由機率基本常識我們知道：P(i)=[k/(k+1)]×[(k+1)/(k+2)]×...×[(N-1)/N]=k/N。

對于i＞k的情形，有興趣的讀者可以自己完成這部分證明。

這個算法的精妙之處在于它的時間複雜度是O(N)，空間複雜度是O(k)。

果殼網[4]上給出了這個問題的一個沒有太大意義的答案，有興趣的讀者可以去看看。