I**********s 发帖数: 441 | 1 一个文件的内容行数未知, 要一次扫描, 任意输出一行.
要求输出每一行的概率相等. 内存很小, 最多只能放下一行的内容.
如果可以扫描两次, 第一次得到行数, 很简单.
如果只扫描一次呢? |
b****r 发帖数: 1272 | 2 print nth line with prob 1/n |
H*M 发帖数: 1268 | 3 check resourvor sampling
【在 I**********s 的大作中提到】 : 一个文件的内容行数未知, 要一次扫描, 任意输出一行. : 要求输出每一行的概率相等. 内存很小, 最多只能放下一行的内容. : 如果可以扫描两次, 第一次得到行数, 很简单. : 如果只扫描一次呢?
|
a******2 发帖数: 393 | 4 programming pearl上有
不过忘记怎么说的了
【在 I**********s 的大作中提到】 : 一个文件的内容行数未知, 要一次扫描, 任意输出一行. : 要求输出每一行的概率相等. 内存很小, 最多只能放下一行的内容. : 如果可以扫描两次, 第一次得到行数, 很简单. : 如果只扫描一次呢?
|
h**k 发帖数: 3368 | 5 那第一行的概率不是1?总是打印第一行?
【在 b****r 的大作中提到】 : print nth line with prob 1/n
|
h*********e 发帖数: 56 | 6 同意,有1/n的概率换原来选的。
【在 b****r 的大作中提到】 : print nth line with prob 1/n
|
l********n 发帖数: 86 | 7 int k=2;
while((line=readline())!=null){
if(random()<1/k)
return line;
k++;
}
|
s*****i 发帖数: 355 | 8 你这每行被选中的概率是 1/2^n
【在 l********n 的大作中提到】 : int k=2; : while((line=readline())!=null){ : if(random()<1/k) : return line; : k++; : } : :
|
m******2 发帖数: 252 | 9 同意,
具体点就是:
先保存第一行,
读到第二行时,1/2概率此行被保存,1/2保留原来的不变
。。
在读第n行,有1/n的概率此行被保存, (n-1)/n概率不变
这样算下来,每行都有1/n概率被保存
【在 h*********e 的大作中提到】 : 同意,有1/n的概率换原来选的。
|
f*****r 发帖数: 754 | 10 没错!
写得更数学一点是这样:
读第一行,保存的概率是 1
读第二行,保存的概率是 1/2, 则第一行被保存的概率是(1-1/2)
读第三行,保存的概率是 1/3, 则第一行被保存的概率是(1-1/2)*(1-1/3), 第二行被
保存的概
率是(1/2)*(1-1/3)
以此类推,假设一共有N行(N未知),则第k行被保存的概率为
1/k*(1-1/(k+1)*...*(1-1/N)=1/N
【在 m******2 的大作中提到】 : 同意, : 具体点就是: : 先保存第一行, : 读到第二行时,1/2概率此行被保存,1/2保留原来的不变 : 。。 : 在读第n行,有1/n的概率此行被保存, (n-1)/n概率不变 : 这样算下来,每行都有1/n概率被保存
|