从文本文件中选择K个随机行

Question

这是从X行文本中选择随机行的原始问题的扩展,其中所选文本行的概率是1/X. 诀窍是如果查询范围为[0,1)的随机变量Y,则选择第J行,并返回小于1/J的值.

现在在这个问题的新版本中,我们必须选择K小于X的K随机线.我相信每条线的概率应该是K/X.

我坚持如何将原始解决方案扩展到K线.可能吗？任何解释都会很棒.

Answer 1

这可以使用原始算法的推广来解决.直觉如下:保持文件中k个候选行的列表,这些候选行最初被播种到前k行.然后,从那时起,在看到文件的第n行时:

• 选择1到n之间的随机值x(包括1和n).
• 如果x> k,则忽略此元素.
• 否则,将元素x替换为文件的第n行.

证明这是以概率k/n正确地采样每个元素,其中n是文件中的总行数,如下所示.假设n≥k.我们通过归纳证明每个元素具有被挑选的概率k/n,通过显示在看到z元素之后,这些元素中的每一个都具有被选择的概率k/z.特别地,这意味着在看到n个元素之后,每个元素具有所需的概率k/n.

作为我们的归纳基础,如果我们确切地看到k个元素,那么每个元素都被选中.因此,根据需要,被选择的概率是k/k.

对于归纳步​​骤,假设对于某些z≥k,已经以概率k/z选择了每个第一z元素并且考虑了(z + 1)st元素.我们选择[1,z + 1]范围内的随机自然数.以概率k /(z + 1),我们决定选择这个元素,然后逐出一些旧元素.这意味着以概率k /(z + 1)选择新元素.对于每个z原始元素,此时选择它的概率是我们在检查第一个z元素之后选择它的概率(概率k/z,通过我们的归纳假设),以及我们的概率保留它是z /(z + 1),因为我们用概率1 /(z + 1)代替它.因此,选择它的新概率是(k/z)(z /(z + 1))= k /(z + 1).因此,以概率k /(z + 1)选择所有第一z + 1个元素,完成归纳.

此外,该算法在O(n)时间内运行并且仅使用O(k)空间,这意味着运行时独立于k的值.要看到这一点,请注意每次迭代都执行O(1)工作,并且总共有O(n)个交互.

如果你很好奇,我可以在我的个人网站上找到这种算法的实现,作为C++ STL风格的算法.

希望这可以帮助!