水塘抽样（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]上给出了这个问题的一个没有太大意义的答案，有兴趣的读者可以去看看。