蓄水池算法（单机版）

1、我是第一行

P=1/2*(1-1/3) = 1/3

P=1/N

……

蓄水池

用数学归纳法得出该方法可行

读第二行

读第三行

场景2：有一个文本文件有N行（N未知），要求从里边随机抽取K行由于N未知，所以一样无法把所有的数据都读到内存中，所以用蓄水池算法，确保每一行被取到的概率为k/i（i为当前读到的行数）

P=1/4

读第N行

P=1/2

P=1/3

P=1*(1/2)=1/2

P = 被抽取的概率

5、我是第N行

3、我是第三行

读第四行

确保文本文件中每行文本被选取的概率为k/N，而从蓄水池中随机选取一个位置来作替换

上一次没有被替换的概率*这一次没有被替换的概率

2、我是第二行

P=1

场景1：有一个文本文件有N行（N未知），要求从里边随机抽取一行因为行数未知，所以未知文件的大小，所以不能一次性读到内存中，只能一行一行地读取，并且要保证每行取到的几率为1/N。

读第一行

4、我是第四行

文本文件