这个问题与此有关
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.随意使用它!

希望这可以帮助!

C tr1 unordered_set随机唯一子集的最快方法的更多相关文章

  1. swift算法实践2

    字符串hash算法Time33在效率和随机性两方面上俱佳。对于一个Hash函数,评价其优劣的标准应为随机性,即对任意一组标本,进入Hash表每一个单元之概率的平均程度,因为这个概率越平均,数据在表中的分布就越平均,表的空间利用率就越高。Times33的算法很简单,就是不断的乘33,见下面算法原型。

  2. 深度学习中的五大正则化方法和七大优化策略

    utm_source=tuicool&utm_medium=referral深度学习中的正则化与优化策略一直是非常重要的部分,它们很大程度上决定了模型的泛化与收敛等性能。本文主要以深度卷积网络为例,探讨了深度学习中的五项正则化与七项优化策略,并重点解释了当前最为流行的Adam优化算法。为了解决这些问题,近年来研究者开发了多种正则化和优化策略。机器学习中最常用的正则化方法是对权重施加L2范数约束。

  3. php – 如何生成这种随机曲线?

    是否有可能产生这种随机曲线?

  4. Java(或任何语言)中的随机混乱概率

    虽然我理解算法,但我不理解他的概率计算.他说,因为Random使用32位种子,这仅限于2^32种不同的排列.他还说knuth的算法更好,因为它给你N!排列.我同意knuth的算法计算.但我认为在第一个上应该有N^N个不同的排列.塞奇威克错了还是我错过了一个事实?

  5. Java 8:IntStream到Integer []

    我正在编写简单的程序,它最终会绘制用Java编写的各种排序算法的运行时间.排序算法的一般接口是通过一种方法:publicvoidsort我试图使用Java8的流机制生成以下几行的随机测试用例:我的问题是,如何将IntStream类型的对象转换为Integer[]?解决方法您应该将IntStreambox转换为流,然后调用toArray来生成它的数组:

  6. c – random_shuffle算法 – 是否产生了没有随机生成函数的相同结果?

    如果没有为标准库中的random_shuffle算法提供随机生成器函数,如果提供相同的数据,程序的连续运行是否会生成相同的随机序列?解决方法25.2.11只是说元素是均匀分布的.它不能保证在幕后使用哪个RNG,因此您不能依赖任何此类行为.为了保证相同的洗牌结果,您需要提供自己的RNG来提供这些保证,但我怀疑即使这样,如果您更新标准库,random_shuffle算法本身也可以改变效果.

  7. delphi – 随机化StringList

    如何在StringList中随机化String,同样地,这个在线工具如何工作.如果有人熟悉它,请检查:http://textmechanic.co/Randomize-List.html解决方法执行随机播放的一个常见算法是Fisher-Yatesshuffle.这产生均匀分布的排列.要在DelphiTStrings对象上实现,可以使用:现在,理论上,这将产生均匀分布的排列,实际的性能在很大程度上取

  8. 算法 – 有效地从链接哈希表中挑选一个随机元素?

    L随机选择p均匀.如果p

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

    这个问题与此有关thisone,更确切地说是this回答它.这里是:我有一个无符号整数的C/TR1unordered_setU(粗基数100-50000,粗略值范围0到10^6).给定基数N,我希望尽可能快地迭代N随机但是U的独特成员.N没有典型值,但它应该为小N快速工作.更详细地说,这里的“随机性”的概念是两个调用应该产生一些不同的子集–越不同,越好,但这不是太关键.我会…对连续感到高兴(或缠绕

  10. Perlin / Simplex噪声算法的随机性质是什么?

    PerlinNoise算法和Simplex噪声算法的随机性质是什么?哪两种算法具有更好的随机性?与标准伪随机生成器相比,使用Perlin/Simplex作为随机数生成器是否有意义?

随机推荐

  1. 从C到C#的zlib(如何将byte []转换为流并将流转换为byte [])

    我的任务是使用zlib解压缩数据包(已接收),然后使用算法从数据中生成图片好消息是我在C中有代码,但任务是在C#中完成C我正在尝试使用zlib.NET,但所有演示都有该代码进行解压缩(C#)我的问题:我不想在解压缩后保存文件,因为我必须使用C代码中显示的算法.如何将byte[]数组转换为类似于C#zlib代码中的流来解压缩数据然后如何将流转换回字节数组?

  2. 为什么C标准使用不确定的变量未定义?

    垃圾价值存储在哪里,为什么目的?解决方法由于效率原因,C选择不将变量初始化为某些自动值.为了初始化这些数据,必须添加指令.以下是一个例子:产生:虽然这段代码:产生:你可以看到,一个完整的额外的指令用来移动1到x.这对于嵌入式系统来说至关重要.

  3. 如何使用命名管道从c调用WCF方法?

    更新:通过协议here,我无法弄清楚未知的信封记录.我在网上找不到任何例子.原版的:我有以下WCF服务我输出添加5行,所以我知道服务器是否处理了请求与否.我有一个.NET客户端,我曾经测试这一切,一切正常工作预期.现在我想为这个做一个非托管的C客户端.我想出了如何得到管道的名称,并写信给它.我从here下载了协议我可以写信给管道,但我看不懂.每当我尝试读取它,我得到一个ERROR_broKEN_P

  4. “这”是否保证指向C中的对象的开始?

    我想使用fwrite将一个对象写入顺序文件.班级就像当我将一个对象写入文件时.我正在游荡,我可以使用fwrite(this,sizeof(int),2,fo)写入前两个整数.问题是:这是否保证指向对象数据的开始,即使对象的最开始可能存在虚拟表.所以上面的操作是安全的.解决方法这提供了对象的地址,这不一定是第一个成员的地址.唯一的例外是所谓的标准布局类型.从C11标准:(9.2/20)Apointe

  5. c – 编译单元之间共享的全局const对象

    当我声明并初始化一个const对象时.两个cpp文件包含此标头.和当我构建解决方案时,没有链接错误,你会得到什么如果g_Const是一个非const基本类型!PrintInUnit1()和PrintInUnit2()表明在两个编译单元中有两个独立的“g_Const”具有不同的地址,为什么?

  6. 什么是C名称查找在这里? (&amp;GCC对吗?)

    为什么在第三个变体找到func,但是在实例化的时候,原始变体中不合格查找找不到func?解决方法一般规则是,任何不在模板定义上下文中的内容只能通过ADL来获取.换句话说,正常的不合格查找仅在模板定义上下文中执行.因为在定义中间语句时没有声明func,并且func不在与ns::type相关联的命名空间中,所以代码形式不正确.

  7. c – 在输出参数中使用auto

    有没有办法在这种情况下使用auto关键字:当然,不可能知道什么类型的.因此,解决方案应该是以某种方式将它们合并为一个句子.这可用吗?解决方法看起来您希望默认初始化给定函数期望作为参数的类型的对象.您无法使用auto执行此操作,但您可以编写一个特征来提取函数所需的类型,然后使用它来声明您的变量:然后你就像这样使用它:当然,只要你重载函数,这一切都会失败.

  8. 在C中说“推动一切浮动”的确定性方式

    鉴于我更喜欢将程序中的数字保留为int或任何内容,那么使用这些数字的浮点数等效的任意算术最方便的方法是什么?说,我有我想写通过将转换放在解析的运算符树叶中,无需将表达式转化为混乱是否可以使用C风格的宏?应该用新的类和重载操作符完成吗?解决方法这是一个非常复杂的表达.更好地给它一个名字:现在当您使用整数参数调用它时,由于参数的类型为double,因此使用常规的算术转换将参数转换为double用C11lambda……

  9. objective-c – 如何获取未知大小的NSArray的第一个X元素?

    在objectiveC中,我有一个NSArray,我们称之为NSArray*largeArray,我想要获得一个新的NSArray*smallArray,只有第一个x对象…

  10. c – Setprecision是混乱

    我只是想问一下setprecision,因为我有点困惑.这里是代码:其中x=以下:方程的左边是x的值.1.105=1.10应为1.111.115=1.11应为1.121.125=1.12应为1.131.135=1.14是正确的1.145=1.15也正确但如果x是:2.115=2.12是正确的2.125=2.12应为2.13所以为什么在一定的价值是正确的,但有时是错误的?请启发我谢谢解决方法没有理由期望使用浮点系统可以正确地表示您的帖子中的任何常量.因此,一旦将它们存储在一个双变量中,那么你所拥有的确切的一

返回
顶部