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

Question

这个问题关系到 这一个,并更准确地这样回答.

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

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

我到底有多远:

1. 平凡的方法:
   选择随机指标i这样(i+N-1) < |U|.获取迭代器,使用它it来U.begin()推进它,然后在子集上启动实际循环.优点:容易.缺点:浪费++.iit++

2. 桶的做法(这我有"新",从上面的链接导出):
   选择i如上,发现桶b中的i个元素是,获得local_iterator lit 到U.begin(b),提前lit通过lit++,直到我们打i的个元素U,并从此不断递增lit的N时间.如果我们到达桶的末尾,我们lit将从下一个桶的开头继续.如果我想让它更随机,我可以i完全随机选择并包裹桶.

我的开放性问题:

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

Answer 1

根据您想要的运行时间保证,有一个着名的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.
• 我们选择前两个元素中的任何一个的概率是在我们没有选择第三个元素(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. 当你看到它时,选择第一个元素作为候选元素.
2. 对于每个连续元素,用概率为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/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算法)的实现可以在这里对我的个人网站.随意使用它!

希望这可以帮助!