从文件中随机选择行

从文件中随机选择行,第1张

文件中随机选择

如果文件足够小,则将成对的行读取到内存中,然后从该数据结构中随机选择。如果文件太大,则Eugene
Y提供正确的答案:使用储层采样。

这是该算法的直观解释。

Process the file line by line.pick = line, with probability 1/N, where N = line number

换句话说,在第1行,我们将以

1/1
概率选择第1行。在第2行,我们将选择权 更改
为第2行
1/2
。在第3行,我们将按
1/3
概率将选择权更改为第3行。等等。

为了直观地证明,想象一下一个包含3行的文件:

        1 Pick line 1.       /      .5  .5     /         2       1        Switch to line 2?   /      /  .67 .33 .33 .67 /      /     2       3       1    Switch to line 3?

每个结果的概率:

Line 1: .5 * .67     = 1/3Line 2: .5 * .67     = 1/3Line 3: .5 * .33 * 2 = 1/3

从那里开始,剩下的就是归纳法。例如,假设文件有4行。我们已经说服自己,从第3行开始,到目前为止的每一行(1、2、3)都有相等的机会成为我们 当前的
选择。当我们前进到第4行时,将有

1/4
机会被选中-正好是应该的位置,从而将前3行的概率降低为正确的数量(
1/3 * 3/4 = 1/4
)。

这是Perl常见问题解答,适用于您的问题。

use strict;use warnings;# Ignore 5 lines.<> for 1 .. 5;# Use reservoir sampling to select pairs from remaining lines.my (@picks, $n);until (eof){    my @lines;    $lines[$_] = <> for 0 .. 1;    $n ++;    @picks = @lines if rand($n) < 1;}print @picks;


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5663688.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存