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

Question

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

现在在这个新版本的问题中，我们必须选择 K 小于 X 的随机行。我相信每行的概率应该是 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，前 z 个元素中的每一个都以概率 k / z 被选择，并考虑第 (z + 1) 个元素。我们在 [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)。

此外，该算法在 O(n) 时间内运行并且仅使用 O(k) 空间，这意味着运行时间与 k 的值无关。要看到这一点，请注意每次迭代都做了 O(1) 次工作，并且总共有 O(n) 次迭代。

如果您好奇，我在我的个人网站上提供了这个算法作为 C++ STL 风格算法的实现。

希望这可以帮助！

Answer 2

首先使用第一种算法从 X 行中随机选择第一个元素。然后从剩余的 X-1 行中选择第二个。运行这个过程 K 次。

任何给定的 K 条线集合的概率是(X choose K)。我将由您来验证该算法是否提供了所需的均匀分布。