水库抽样

水库抽样算法是一个典型的空间亚线性算法。

在很多时候我们要在海量数据中进行均匀的抽样，由于我们要取样的是海量数据，以至于只能让这些数据从我们面前流过一次。

水库抽样的要求是，每一时刻取到的样本都是前面已经流过的全部数据的均匀抽样。

例如：连续输入一组未知大小的数据，输出这组数据的k个均匀抽样。要求：输入到前n(n>k)个数据时，保存已经输入的数据的k个均匀抽样。

1.申请长度为k的数组A保存抽样(此处下标用1~k表示)；

2.首先保存接收到的前k个数据；

3.当接收到第i个数据t时，生成[1,i]间的随机数j,若j<=k,则以t替换A[j]。

算法的关键在第三步，每当新来元素t时，生成随机数，一旦随机数落在数组范围之内，就替换掉。

算法原理：

对于每个新到来的元素i，它是以k/i的概率被收入集合的，因为生成的随机数范围是[1,i]，而当数字小于等于k时，才会被替换进数组A。

当第i+1个元素到来时，第i+1个元素被替换进数组的概率是Pi=k/(i+1)，而此时，前一个元素i被从中替换出来的概率为Po=1/k。则当第i+1个元素到来时第i个元素被替换出去的概率为Pi*Po，那么没有被替换出来的概率为p=1-Pi*Po=1-1/(i+1)。

那么当第i+2,i+3...个元素到来时，第i个元素没有被替换出来的概率为1-1/(i+2)，1-1/(1+3)...

那么当元素i被选入集合中，并且在后面的所有的替换中都没有被替换出来的概率：

这样便得到，对于任意一个元素i，其被选入样本的概率均为k/n，也就是说它符合随机抽样。