language-agnostic - 文件中的随机行

Question

这个问题是在面试的时候问我的。面试已经结束了，但我仍在思考 hte 问题及其困扰我：

您拥有一种包含以下工具的语言：rand()函数、while循环for、if语句和readline()方法（类似于 python 的readline()）。给定这些工具，编写一个在文件中返回随机行的算法。你不知道文件的大小，你只能循环文件的内容一次。

Answer 1

我不知道想要的答案，但我的解决方案如下：

chosen_line = ""
lines = 0

while (current_line = readline()):
    if (rand(0, lines) == 0):
        chosen_line = current_line

    lines++

return chosen_line

编辑：一个很好的解释为什么这个作品发布在这个评论中。

Answer 2

一种方法，保证均匀分布：

(1) 将文件逐行读入一个数组（或类似的，例如 python list）

(2)rand()用于选择一个介于 0 和数组中最大索引之间的数字。

另一个，不保证均匀分布：

阅读每一行。在每次读取时，还要调用 rand()。如果超过阈值，则返回该行。

Answer 3

虽然类似于 Marcin 的第三个选项，但 Luc 的实现总是返回第一行，同时解析整个文件。

它应该是这样的：

chosen_line = ""
treshold = 90 
max = 100

while chosen_line == "":
    current_line = readline()
    if (rand(0, max) > treshold):
        chosen_line = current_line

print chosen_line

如果没有选择任何行并且您阅读了整个文件，您也可以返回 current_line。