C++ tr1无序集合中获取随机唯一子集的最快方法

Question

C++ tr1无序集合中获取随机唯一子集的最快方法

6

这个问题与这个有关，更确切地说是与这个答案有关。

我有一个C++/TR1无序集合U，其中包含无符号整数（大约100-50000个，值范围大约为0到10^6）。给定一个基数N，我想尽快迭代U中的N个随机但唯一的成员。对于N，没有典型的值，但它应该对小的N快速工作。

更详细地说，这里的“随机性”概念是，两个调用应该产生略微不同的子集——差异越大越好，但这并不是太关键。例如，我会满意于N个连续的（或环绕的连续）U成员块，只要该块的起始索引是随机的。非连续的代价相同，但主要问题是速度。U在调用之间轻微变化，但不断变化（大约0-10个元素在调用之间插入/擦除）。

我目前的进展：

1.平凡方法：选择随机索引i，使得(i+N-1) < |U|，获取到一个迭代器it，使用it++将其向前推进i次，然后开始子集的实际循环。优点：容易。缺点：浪费了许多++。

2.桶法（我从上面的链接中“新”获得的）：像上面一样选择i，找到i所在的bucket b，获取到一个局部迭代器lit，通过lit++推进lit，直到我们命中U的第i个元素，然后继续增加lit，直到N次。如果我们遇到了bucket的末尾，我们从下一个bucket的开头继续使用lit。如果我想让它更随机，我可以完全随机地选择i并围绕buckets进行包装。

我的问题如下：

关于上述的第二点，如果我已经找到了第i个元素，是否真的无法以某种方式获得一个指向U中迭代器呢？这将减少我对于bucket边界控制等的需求。对于我这样的初学者来说，标准的前向迭代器似乎应该知道如何在遍历到U中的第i个元素时继续遍历整个U，但是当我自己找到第i个元素时，除了通过上述的方法2之外，不应该有其他的遍历U的方式。
还能做什么呢？您是否知道更聪明/更随机的方法？如果可能的话，我不想涉及到手动控制bucket大小、哈希函数等，因为我觉得这些内容有点超出我的理解范围。

- daspostloch

你所描述的两个线性时间算法似乎是用于选择集合中的随机元素，而不是选择随机子集？另外，为什么不将可能的迭代器值复制到数组中呢？这样你就可以在常数时间内选择随机元素了。 - Cheers and hth. - Alf

嗯，我认为随机选择N个元素与选择大小为N的子集是相同的。如果有一个解决方案取决于它是哪一个，我仍然想听听它。您能否在复制方面进行澄清，即在什么成本下进行复制，如何处理无序集合的更改？ - daspostloch

如果你自己编写一个哈希集（或以其他方式访问底层桶），那么你可以显著提高性能，前提是你不关心是否有真正的均匀分布... - bdonlan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

根据您想要的运行时保证，有一个著名的O(n)算法可以在一次遍历中从数字流中选择k个随机元素。为了理解这个算法，让我们先看看当我们只想从集合中选出一个元素时如何操作，然后我们将把它推广到选择k个元素的情况。这种方法的优点是不需要任何关于输入集大小的预先知识，并且保证元素的均匀采样，这总是非常好的。

假设我们想从集合中选择一个元素。为此，我们将遍历集合中的所有元素，并在每个点上维护一个候选元素，我们计划返回该元素。当我们遍历元素列表时，我们将使用一些概率更新我们的猜测，直到最后我们选择了一个具有均匀概率的单个元素。在每个点上，我们将保持以下不变量：

在看完k个元素之后，第一个k个元素中任何一个当前被选为候选元素的概率为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) 个元素的概率（k/(k+1)），这使得这些元素每个都有 1/(k+1) 的被选中概率。由于每个步骤都保持不变量，因此我们得到了一个很好的算法：

第一次看到元素时，选择第一个元素作为候选元素。
对于每个后续元素，以 1/k 的概率替换候选元素，其中 k 是到目前为止看到的元素数量。

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

现在，让我们看看如何扩展这个算法，以便我们可以从集合中选择 k 个元素，而不仅仅是一个。这个想法与先前的算法非常相似（实际上是更通用的特殊情况）。我们不再维护一个候选元素，而是维护 k 个不同的候选元素，存储在数组中，编号为 1、2、…k。在每个点上，我们保持这个不变量：

看到 m > k 个元素后，选择前 m 个元素中任意一个的概率是 k/m。

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

算法与之前类似。首先，以概率 1 选择集合中的前 k 个元素。这意味着当我们看到 k 个元素时，任何一个元素被选中的概率都是 1=k，并且不变量成立。现在，归纳地假设在 m 次迭代后不变量成立，并考虑第 (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算法编写）的版本，在我的个人网站（点击此处）上可以找到。请随意使用！

希望这可以帮助您！