algorithm - 从 [0 :n) 中均匀采样 k 个整数

Question

我的目标是从 0, ... n-1 中采样 k 个整数而不重复。采样整数的顺序无关紧要。在每次调用时(经常发生)，n 和 k 会略有不同但不会太大(n 约为 250,000，k 约为 2,000)。我提出了以下分期 O(k) 算法:

1. 准备一个包含项目 0, 1, 2, ..., n-1 的数组 A。这需要 O(n)，但由于 n 相对稳定，成本可以摊销为常量。
2. 从 [0:i] 中抽取一个随机数 r，其中 i = n - 1。这里的成本实际上与 n 相关，但由于 n 不是很大，因此这种依赖性并不重要。
3. 交换数组A中的第r项和第i项。
4. 将 i 减 1。
5. 重复步骤2~4 k次；现在我们在 A 的尾部有一个长度为 k 的随机排列。复制这个。
6. 我们应该将 A 回滚到其初始状态 (0, ... , n-1) 以保持第 1 步的成本不变。这可以通过在步骤 2 的每次传递时将 r 插入长度为 k 的堆栈来完成。堆栈的准备需要摊销的恒定成本。

我认为排列/组合的均匀采样应该是一个详尽研究的问题，所以 (1) 有更好的解决方案，或者至少 (2) 我的解决方案是一个众所周知的解决方案(稍作修改) .因此，

• 在情况 (1) 中，我想知道更好的解决方案。
• 在情况 (2) 中，我想找到一个引用。

请帮帮我。谢谢。

Answer 1

1. 如果 k远小于 n -- 比如说，不到 n 的一半-- 那么最有效的解决方案是将生成的数字保存在哈希表中(实际上是一个哈希集，因为没有与键关联的值)。如果随机数恰好已经在哈希表中，则拒绝它并在其位置生成另一个随机数。使用 k 的实际值和 n建议 ( k ∼ 2000; n ∼ 250,000 ) 生成 k 的预期拒绝次数unique samples 少于 10，因此很难被注意到。哈希表的大小为O(k)，可以简单地在样本生成结束时将其删除。

2. 也可以使用哈希表而不是 n 的向量来模拟 FYK 洗牌算法。值，从而避免不得不拒绝生成的随机数。如果您使用矢量 A ，您将从初始化 A[i] 开始至 i , 对于每个 0 ≤ i < k .用哈希表 H ，您从一个空的哈希表开始，并使用 H[i] 的约定被认为是 i如果键 i不在哈希表中。算法中的第 3 步——“用 A[r] 交换 A[i]”——变为“添加 H[r] 作为样本的下一个元素并将 H[r] 设置为 H[i]”。请注意，无需设置 H[i]因为该元素将永远不会再次被引用:所有后续随机数 r从不包括 i 的范围生成.

   因为本例中的哈希表同时包含键和值，所以它比上面备选方案 1 中使用的哈希集更大，并且增加的大小(以及随之而来的内存缓存未命中率的增加)可能会导致比通过消除拒绝来保存。但是，它的优点是即使k 也能正常工作。偶尔接近n .

3. 最后，在你提出的算法中，其实很容易恢复A在 O(k) 时间内。一个值 A[j]只有在以下情况下才会被算法修改:

   一个。 n − k ≤ j < n , 或者

   有一些i这样 n − k ≤ i < n和 A[i] = j .

   因此，您可以恢复向量 A通过查看每个 A[i]对于 n − k ≤ i < n : 首先，如果 A[i] < n−k , 设置 A[A[i]]至 A[i] ;然后无条件设置A[i]至 i .