蓄水池算法(单机版)
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 条评论
下一页