蓄水池算法（单机版）
2021-04-25 23:15:13 0 举报
蓄水池算法（单机版）
作者其他创作
大纲/内容
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、我是第四行
文本文件
0 条评论
回复 删除
下一页
