常用算法

一、常用算法

Reservoir Sampling，蓄水池算法，用来解决大量数据的采样问题，算法过程如下：

1、假设数据规模为n，需要采样的数量为k；
2、首先构建一个可容纳k个元素的数组，并将数据的前k个元素放入数组；
3、从第k+1个元素开始，假设是第m个元素，它会以k/m的概率进入数组，数组中每个元素被替换的概率是1/k；
4、当遍历完所有元素之后，数组中剩下的元素即为所需采取的样本；
5、对于其中每个元素，被保留的概率都为k/n；