[Algorithm]Reservoir Sampling

假设存在一个数据流，长度为N。但我们事先不知道其长度，我们想从数据流中选出k(k <= N)个数据，如何保证选到的k个数据是随机的？换句话说，如何保证每个元素被选到被选择的改路是k / N？Reservoir sampling就是用来解决这类问题的算法，具体步骤如下：

1. 将数据流前k个数据([0, k - 1])加入结果集
2. 对于[k, N - 1]中的数据i，我们随机生成一个[0, i]的数字r，如果0 <= r <= k - 1，我们把数据i加入结果集，把数据r移出结果集

这样对于数据流中的数据，我们有如下结论：

• 对于前k个数，其最终留在结果集中的概率为(k / (k + 1)) * ((k + 1) / (k + 2)) * ... * ((N - 1) / N) = k / N
• 对于[k, N - 1]的数据i，其被换入结果集的概率为k / i，留在结果集不被换出的概率为(i / (i + 1)) * ((i + 1) / (i + 2)) * ... * ((N - 1) / N)，两者相乘结果为k / N

我们用Linkedlist来代表数据流，代码如下：