如何从文件中返回随机行？面试问题

Question

我正准备接受电话采访.我在互联网上遇到了这些问题.谁能告诉我一些这些好的答案？

1. 假设我给你一个文本文件并要求你编写一个程序,它将从文件中返回一个随机行(所有行必须具有相同的返回概率)

2. 与第1部分相同,除了这次整个文本文件不能适合主存储器

3. 与第2部分相同,除了现在您有一个流而不是一个文件.

请帮忙.

好的...... @每个人,在我问到这个问题之前,我真的有一些想法......看到我的同伴们的无情攻击,我发布了我的答案.请随意攻击他们......

1:计算文件中'\n'的数量.生成1和数字之间的随机数,并返回数字-1'\n'之后的行.

2:将文件逐个部分地存入主存储器,并按照上述步骤进行操作.

3:我对此并不太了解,并希望得到任何意见.

很棒,你们真的给予灵感推进.....

Answer 1

1. 将所有行读入数组,返回1范围内的随机行和行数.

2. 最简单:计算线条,随机选择一个行号,再次浏览文件并返回.

3. 你只需要记住一行.每个新行的概率为1/N(N为行读取).

   伪代码:

   i = 1
   chosen_line = ""
   for line in lines:
       if random() < 1/i:    # random returns a uniform random number in [0,1)
           chosen_line = line
       i += 1
   return chosen_line
   

算法编号3也可以用于1和2.

Answer 2

你可以这样做而无需读取内存中的所有行,因此适用于大文件.伪代码:

linenum := 0
ret := ''
while more lines to read:
    line := readline()
    linenum := linenum + 1
    r := uniform_random(0, linenum)
    if r < 1:
        ret := line

return ret

证明:我们首先注意到我们总是保存第一行ret.如果文件有一行,您将选择它,然后就完成了.

对于双行文件,ret将在100%的时间内保存第一行,并且ret在循环的第二次迭代期间将在50%的时间内保存第二行.因此,每条线的选择概率为0.5.

现在,我们假设此方法适用于≤ N行的文件.为了证明这意味着它适用于N+1在(N+1)循环的第二次迭代中,有1/(N+1)可能选择最后一行(random(0, N+1) < 1具有该概率).因此,最后一行有1/(N+1)被选中的概率.选择所有其他线路的概率仍然相互相等,让我们称之为x.然后,N*x + 1/(N+1) == 1这意味着x = 1/(N+1).

感应证明已完成.

编辑:哎呀,在回复之前没有看到第一个答案的第三个方法.不过,如果只是为了证明,我会在这里保留这篇文章,如果有任何错误,其他人有机会纠正它.

Answer 3

回复 1：使用 2 的解决方案

回复 2：您可能希望使用 RandomAccessFile 访问来扫描整个文件以计算行数并（可能）缓存每个行开头的文件指针。然后你可以随机选择一个（我假设这个问题不是关于如何生成随机数）并移回该起点，读取该行并将其返回。如果你想要它快，那么请确保你正在缓冲读取（否则 raf 会很慢）。

回复3：如果流不适合内存（即您无法缓存整个内容）并且您不知道流中有多少行而无需读取整个流（假设您只能读取一次），那么我看不到解决方案。我也等答案...