0

我的目标是从 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. 重复k次步骤2~4；现在我们在 A 的尾部有一个长度为 k 的随机排列。复制这个。
  6. 我们应该将 A 回滚到其初始状态 (0, ... , n-1) 以保持步骤 1 的成本不变。这可以通过在步骤 2 的每次通过时将 r 推入长度为 k 的堆栈来完成。堆栈的准备需要摊销的恒定成本。

我认为排列/组合的统一采样应该是一个详尽研究的问题，所以要么（1）有一个更好的解决方案，要么至少（2）我的解决方案是一个（小的修改）一个众所周知的解决方案。因此，

  • 在情况（1）中，我想知道更好的解决方案。
  • 在情况（2）中，我想找到一个参考。

请帮我。谢谢。

4

1 回答 1

1

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

  2. 也可以使用哈希表而不是n值向量来模拟 FYK shuffle 算法，从而避免不得不拒绝生成的随机数。如果您使用的是 vector A，您将首先初始化A[i]为i, for each 0 ≤ i < k。使用 hash table H，你从一个空的 hash table 开始，并使用H[i]被认为是ikeyi不在 hash table 中的约定。A[r]算法中的第 3 步——“与”交换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]for来恢复向量n − k ≤ i < n：首先，如果A[i] < n−k，设置A[A[i]]为A[i]; 然后，无条件设置A[i]为i。

于 2017-08-19T23:14:17.933 回答