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概率被保存
|
