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

发布时间：2020-12-16 03:43:23 所属栏目：百科来源：网络整理

导读：这个问题与此有关 this one,更确切地说是 this回答它. 这里是：我有一个无符号整数的C / TR1 unordered_set U(粗基数100-50000,粗略值范围0到10 ^ 6). 给定基数N,我希望尽可能快地迭代N随机但是 U的独特成员.N没有典型值,但它应该为小N快速工作. 更详细地说

这个问题与此有关
this one,更确切地说是 this回答它.

这里是：我有一个无符号整数的C / TR1 unordered_set U(粗基数100-50000,粗略值范围0到10 ^ 6).
给定基数N,我希望尽可能快地迭代N随机但是
U的独特成员.N没有典型值,但它应该
为小N快速工作.

更详细地说,这里的“随机性”的概念是
两个调用应该产生一些不同的子集 – 越不同,
越好,但这不是太关键.我会…对连续感到高兴
(或缠绕连续)
U的N个成员的块,只要该块的起始索引是随机的.
以相同的成本不连续更好,但主要关注的是速度.你改变了
温和地,但不断地在呼叫之间(在呼叫之间插入/删除大约0-10个元素).

我到底有多远：

>平凡方法：选择随机索引i,使得(i N-1)< | U |.
获取一个迭代器到U.begin(),使用它推进它,然后启动
子集上的实际循环.优点：容易.缺点：浪费’es.
>存储桶方法(以及我从上面链接派生的“新”)：
选择上面的i,找到第i个元素所在的桶b,点亮local_iterator
到了U.begin(b),通过点亮前进直到我们击中U的第i个元素,然后继续点亮N次.如果我们到达桶的末端,
我们继续从下一个桶的开头点燃.如果我想成功的话
更随机我可以完全随机选择我并将其包裹起来.

我的开放性问题：

>对于上面的第2点,我真的无法以某种方式得到一个
一旦我找到第i个元素,迭代器进入U？这样可以省去我
铲斗边界控制等对我而言相当
初学者,标准的前向迭代器应该知道如何,这似乎是不可思议的
在第i个项目时继续遍历U,但是当我自己找到第i个项目时,
除了通过上面的第2点之外,不应该遍历U.
>我还能做什么？你知道更聪明/更随意的事吗？如果可能的话,我不想参与手册
控制铲斗尺寸,散列函数等,因为这有点过头了.

解决方法

根据您想要的运行时间保证,有一个着名的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.
>我们选择前两个元素中的任何一个的概率是在我们没有选择第三个元素(2/3)的前两个步骤(1/2)之后选择它的概率.这可以达到1/3.

再一次,不变量持有！

这里的一般模式如下所示：在我们看到k个元素之后,每个元素都有1 / k的机会被选中.当我们看到(k 1)st元素时,我们选择它的概率为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)st迭代.选择介于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.随意使用它！

希望这可以帮助！

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!