1

考虑这个问题：- 从链式哈希表中有效地挑选一个随机元素？

并认为这是第一个答案。它提出了一种以均匀随机方式选择密钥的方法。然而，这对我来说还不清楚。第一步将采用概率1/m（即从 m 个桶中随机选择一个桶）
，而第二步可以分为两个步骤：
1）如果k<=p，则返回 p。
2）如果k>p然后循环再次运行。
这样做直到返回 p。
所以一个键被选中的概率是：
(1/m)[(k1/L)+((L-k1)/L)[(1/m)[(k2/L)+((L-k2)/L)[(1/m)[(k3/L)+((L-k3)/L)[......and so on.
现在这怎么能等于1/n？

4

1 回答 1

1

这是拒绝抽样的一种形式。

评论：

  • 看起来您仅在第二步中拆分了两个步骤并以某种方式循环（我对您的计算公式的解释）
  • 每次 重做所有步骤是算法最重要的方面！
    • 这是拒绝抽样的基本思想：我们正在从一些周围密度中抽样，如果所选样本不在我们的样本范围内，则需要再次抽样（这是非常非正式的；阅读上面的链接）

为什么采用这种方法：

  • 想象一下，有2 个桶，其中b0有2 个元素，b1有4 个元素
  • 第一步是统一选择一个桶
    • 但是因为b0的元素数量与b1不同，所以步骤 2中的实际采样需要以某种方式适应有关元素数量的信息（或者我们将使用均匀性）
    • 我们没有这个完整的信息，我们只得到了所有链上的上限 L
    • 含义：我们使用拒绝思想从最大范围 L中进行采样；如果索引与存储桶兼容，则接受。因此，如果所选存储桶的元素数量是最大存储桶的一半，则需要 50% 的时间将其中止（从步骤 1 重新开始）。这就像在所有桶中插入假元素，以便元素的数量是恒定的。然后采样，检查是否选择了真元素或假元素，如果击中假元素，则再次执行此操作。
    • 很容易看出：b0 get 有 50% 的时间被选中；等于b1
    • 在b0内采样时，该过程将中止50% 的时间，因为k=2，L=4 （L 来自b2中元素的大小）
    • 在b1内采样时，该过程永远不会中止（k=L）
    • 如果没有流产的机会；我们将选择b0 的一个选定元素的频率L / size-within-b0 = L/2是从b1中选择一个元素的 2 倍（ ） ，因为桶是均匀选择的；但是要采样的元素数量不同。
于 2016-10-14T17:07:46.583 回答