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

Question

我熟悉 the algorithm for reading a single random line from a file without reading the whole file into memory .我想知道是否可以将此技术扩展到 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，并且选择了第三行，它将始终位于数组中的第三个位置。

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