如何在不将文件存储在内存中的情况下从文件中读取N个随机行？

Question

我熟悉从文件读取单个随机行而不将整个文件读入内存的算法.我想知道这种技术是否可以扩展到N个随机线？

用例是一个密码生成器,它连接从字典文件中拉出的N个随机字,每行一个字(如/usr/share/dict/words).你可能想出来angela.ham.lewis.pathos.现在它将整个字典文件读入一个数组,并从该数组中选择N个随机元素.我想消除该文件的数组或任何其他内存存储,并只读取该文件一次.

(不,这不是一个实际的优化练习.我对算法感兴趣.)

更新:谢谢大家的答案.

答案分为三类:完整读取算法的修改,随机搜索或索引线并随机搜索它们.

随机搜索要快得多,并且相对于文件大小是恒定的,但是基于文件大小而不是字数来分发.它还允许重复(可以避免,但它使算法O(inf)).这是我使用该算法重新实现我的密码生成器.我意识到,通过从搜索点向前读取,而不是向后读取,如果搜索落在最后一行,它会有一个一个一个错误.校正留作编辑的练习.

#!/usr/bin/perl -lw

my $Words       = "/usr/share/dict/words";
my $Max_Length  = 8;
my $Num_Words   = 4;

my $size = -s $Words;

my @words;
open my $fh, "<", $Words or die $!;

for(1..$Num_Words) {
    seek $fh, int rand $size, 0 or die $!;
    <$fh>;
    my $word = <$fh>;
    chomp $word;
    redo if length $word > $Max_Length;
    push @words, $word;
}
print join ".", @words;

然后就是Guffa的答案,这正是我所寻找的; 原始算法的扩展.更慢,它必须读取整个文件,但是按字分发,允许过滤而不改变算法的效率,并且(我认为)没有重复.

#!/usr/bin/perl -lw

my $Words       = "/usr/share/dict/words";
my $Max_Length  = 8;
my $Num_Words   = 4;

my @words;
open my $fh, "<", $Words or die $!;
my $count = 0;
while(my $line = <$fh>) {
    chomp $line;
    $count++;
    if( $count <= $Num_Words ) {
        $words[$count-1] = $line;
    }
    elsif( rand($count) <= $Num_Words ) {
        $words[rand($Num_Words)] = $line;
    }
}

print join ".", @words;

最后,索引和搜索算法具有按字而不是文件大小分布的优点.缺点是它读取整个文件和内存使用量与文件中的单词数量呈线性关系.不妨使用Guffa的算法.

Answer 1

在该示例中,该算法未以非常好的方式实现...一些更好地解释它的伪代码将是:

cnt = 0
while not end of file {
   read line
   cnt = cnt + 1
   if random(1 to cnt) = 1 {
      result = line
   }
}

如您所见,我们的想法是您读取文件中的每一行并计算该行应该是所选行的概率.读完第一行后概率为100%,读完第二行后概率为50%,依此类推.

这可以扩展为通过保持大小为N而不是单个变量的数组来挑选N个项目,并计算一行替换数组中当前一个的概率:

var result[1..N]
cnt = 0
while not end of file {
   read line
   cnt = cnt + 1
   if cnt <= N {
      result[cnt] = line
   } else if random(1 to cnt) <= N {
      result[random(1 to N)] = line
   }
}

编辑:
这是用C#实现的代码:

public static List<string> GetRandomLines(string path, int count) {
    List<string> result = new List<string>();
    Random rnd = new Random();
    int cnt = 0;
    string line;
    using (StreamReader reader = new StreamReader(path)) {
        while ((line = reader.ReadLine()) != null) {
            cnt++;
            int pos = rnd.Next(cnt);
            if (cnt <= count) {
                result.Insert(pos, line);
            } else {
                if (pos < count) {
                    result[pos] = line;
                }
            }
        }
    }
    return result;
}

我通过运行方法100000次,从20个中挑选5行进行测试,并计算出线的出现次数.这是结果:

25105
24966
24808
24966
25279
24824
25068
24901
25145
24895
25087
25272
24971
24775
25024
25180
25027
25000
24900
24807

如您所见,分布与您想要的一样好.:)

(我Random在运行测试时将对象的创建移出方法,以避免种子问题,因为种子是从系统时钟中取出的.)

注意:
如果您希望随机排序,可能需要对结果数组中的顺序进行加扰.由于前N行在数组中按顺序放置,如果它们保留在末尾,则不会随机放置它们.例如,如果N为3或更大并且拾取第3行,则它将始终位于数组中的第3个位置.

编辑2:
我改变了代码使用List<string>而不是a string[].这使得以随机顺序插入前N个项目变得容易.我从新的测试运行中更新了测试数据,这样您就可以看到分布仍然很好.