随机选择文件中的行

Question

我有一堆文件,文件有5行的标题.在文件的其余部分,一对行形成一个条目.我需要从这些文件中随机选择条目.如何选择随机文件和随机条目(一对行,不包括标题)？

Answer 1

你可能会发现perlfaq5很有用.

Answer 2

如果文件足够小,请将行对读入内存并从该数据结构中随机选择.如果文件太大,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/3
Line 2: .5 * .67     = 1/3
Line 3: .5 * .33 * 2 = 1/3

从那里,其余的是归纳.例如,假设文件有4行.我们已经说服自己,从第3行开始,到目前为止,每一行(1,2,3)都有平等的机会成为我们当前的选择.当我们前进到第4行时,它将有1/4机会被选中 - 正是它应该是什么,从而将前3行的概率减少恰当的数量(1/3 * 3/4 = 1/4).

这是Perl FAQ的答案,适合您的问题.

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;