c++ - C++ tr1 unordered_set 的随机唯一子集的最快方法

Question

这个问题与
this one ，更准确地说是 this回答它。

这是:我有一个 C++/TR1 unordered_set U无符号整数(粗略基数 100-50000，粗略值范围 0 到 10^6)。
给定一个基数 N ，我想尽快迭代 N随机但U唯一成员(member). N 没有典型值，但它应该
为小人快速工作 N .

更详细地说，这里的“随机性”的概念是
两个调用应该产生一些不同的子集——越不同，
越好，但这不是太重要。我会例如乐于持续
(或环绕连续)N块U成员(member)，只要块的起始索引是随机的。
在相同成本下非连续更好，但主要关注的是速度。 U变化
温和，但在通话之间不断(在通话之间插入/删除大约 0-10 个元素)。

我走了多远:

简单的方法:选择随机索引 i使得 (i+N-1) < |U| .
获取迭代器 it至 U.begin() , 推进它 i使用次数 it++ ，然后开始
子集上的实际循环。优点:容易。缺点:浪费++。

桶方法(这是我从上面的链接"new"派生的):
接 i如上，找到桶b其中i -th 元素在，获取 local_iterator lit至 U.begin(b) , 提前 lit通过 lit++直到我们点击 i U 的第 - 个元素，然后继续递增 lit为 N次。如果我们撞到桶的尽头，
我们继续 lit从下一个桶的开始。如果我想做
更多随机我可以选择i完全随机并包裹在桶周围。

我的开放问题:

对于上面的第 2 点，我真的无法以某种方式获得
迭代器进入 U一旦我找到了 i -th 元素？这会饶了我
桶边界控制等。 对我来说相当
初学者，标准前向迭代器应该知道如何
继续遍历U当在 i -th 项，但是当我找到 i 时-我自己的第一个项目，
应该不可能遍历 U除了通过上述第 2 点。

我还可以做些什么？你知道什么更聪明/更随机吗？如果可能，我不想参与手册
控制桶大小、散列函数等，因为这有点超出我的想象。

Answer 1

根据您想要的运行时保证，有一个著名的 O(n) 算法，用于在一次传递中从数字流中挑选 k 个随机元素。为了理解算法，让我们先看看我们只想从集合中挑选一个元素的情况，然后我们将它概括为用于挑选 k 个元素。这种方法的优点是它不需要任何关于输入集大小的预先知识，并保证元素的可证明统一采样，这总是非常好的。

假设我们想从集合中挑选一个元素。为此，我们将遍历集合中的所有元素，并在每个点维护一个我们计划返回的候选元素。当我们遍历元素列表时，我们会以一定的概率更新我们的猜测，直到最后我们以统一的概率选择了一个元素。在每个点，我们将保持以下不变式:

After seeing k elements, the probability that any of the first k elements is currently chosen as the candidate element is 1 / k.

如果我们在整个数组中保持这个不变性，那么在看到所有 n 个元素之后，它们中的每一个都有 1/n 的机会成为候选元素。因此，候选元素已经以均匀随机概率采样。

为了了解算法是如何工作的，让我们考虑一下它必须做什么来保持不变量。假设我们刚刚看到了第一个元素。为了保持上述不变性，我们必须以概率 1 选择它，因此我们将候选元素的初始猜测设置为第一个元素。

现在，当我们处理第二个元素时，我们需要保持每个元素以 1/2 的概率被选中的不变量，因为我们已经看到了两个元素。所以让我们假设我们以 1/2 的概率选择第二个元素。然后我们知道以下几点:

我们选择第二个元素的概率是 1/2。

我们选择第一个元素的概率是我们第一次选择它的概率大约 (1) 乘以我们没有选择第二个元素的概率 (1/2)。这也达到了 1/2。

所以在这一点上，不变量仍然保持不变!让我们看看当我们来到第三个元素时会发生什么。此时，我们需要确保每个元素以 1/3 的概率被选中。好吧，假设我们以 1/3 的概率选择最后一个元素。然后我们知道

我们选择了第三个元素的概率是 1/3。

我们选择前两个元素中的任何一个的概率是在前两个步骤之后它被选择的概率 (1/2) 乘以我们没有选择第三个元素的概率 (2/3)。这可以达到 1/3。

所以再次，不变量成立!

这里的一般模式如下所示:在我们看到 k 个元素之后，每个元素都有 1/k 的机会被选中。当我们看到第 (k + 1) 个元素时，我们以 1/(k + 1) 的概率选择它。这意味着它以 1/(k + 1) 的概率被选择，并且它之前的所有元素被选择的概率等于我们之前选择它的概率 (1/k) 而没有选择 (k + 1) )st 个元素这次 (k/(k + 1))，这使这些元素每个都有 1/(k + 1) 被选中的概率。由于这在每一步都保持不变，我们得到了一个很棒的算法:

当您看到它时，选择第一个元素作为候选。

对于每个连续的元素，用概率 1/k 的那个元素替换候选元素，其中 k 是到目前为止看到的元素的数量。

这在 O(n) 时间内运行，需要 O(1) 空间，并从数据流中返回一个均匀随机的元素。

现在，让我们看看如果我们想从集合中挑选 k 个元素，而不仅仅是一个，如何扩大它的工作范围。这个想法与之前的算法非常相似(实际上它最终成为更通用算法的一个特例)。我们不维护一个候选，而是维护 k 个不同的候选，存储在我们编号为 1, 2, ..., k 的数组中。在每一点，我们都保持这个不变式:

After seeing m > k elements, the probability that any of the first m elements is chosen is k / m.

如果我们扫描整个数组，这意味着当我们完成时，每个元素都有被选中的概率 k/n。由于我们选择了 k 个不同的元素，这意味着我们随机从数组中均匀地采样元素。

算法与之前类似。首先，以概率 1 从集合中选择前 k 个元素。这意味着当我们看到 k 个元素时，其中任何一个被选中的概率是 1 = k/k 并且不变量成立。现在，归纳假设不变量在 m 次迭代后成立，并考虑第 (m + 1) 次迭代。选择一个介于 1 和 (m + 1) 之间的随机数，包括 1 和 (m + 1)。如果我们选择 1 到 k(含)之间的数字，则用下一个元素替换该候选元素。否则，不要选择下一个元素。这意味着我们根据需要以概率 k/(m + 1) 选择下一个元素。选择前 m 个元素中的任何一个的概率是它们之前被选择的概率 (k/m) 乘以我们没有选择包含该元素的槽的概率 (m/(m + 1))，即根据需要给出 k/(m + 1) 被选中的总概率。通过归纳，这证明了该算法完全一致地从集合中随机抽取了 k 个元素!

而且，运行时间是O(n)，与集合的大小成正比，完全独立于你要选择的元素数量。它还仅使用 O(k) 内存，并且对所存储元素的类型不做任何假设。

由于您试图为 C++ 执行此操作，作为无耻的自我推销，我有此算法的实现(编写为 STL 算法) available here 在我的个人网站上。随意使用它!

希望这可以帮助!