首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >伪随机数生成器提供相同的第一个输出,但随后的行为与预期相同。

伪随机数生成器提供相同的第一个输出,但随后的行为与预期相同。
EN

Stack Overflow用户
提问于 2014-10-20 21:57:11
回答 3查看 4.1K关注 0票数 11

使用随机类和时间种子(NULL),均匀分布总是给出相同的第一个输出,即使有不同的编译,但是在第一个输出之后的行为就像您期望的伪随机数生成器的行为一样。

这是建筑造成的,还是我用错了?

MWE:

代码语言:javascript
复制
#include <ctime>
#include <iostream>
#include <random>

using namespace std;

default_random_engine gen(time(NULL));
uniform_int_distribution<int> dist(10,200);

int main()
{
    for(int i = 0; i < 5; i++)
        cout<<dist(gen)<<endl;

    return 0;
}

在我运行这个程序的前三次中,我得到了以下输出:

代码语言:javascript
复制
57
134
125
136
112

在第二次尝试之前,我决定删除uniform_int_distributionint main()之间的空行,以查看种子是否基于编译时,正如您所看到的,这并不重要。

代码语言:javascript
复制
57
84
163
42
146

再跑一次:

代码语言:javascript
复制
57
73
181
160
46

所以在我的运行中,我总是先得到57,这当然不是世界末日,如果我想要不同的输出,我可以丢弃第一个输出。但它让人怀疑这是否是故意的(如果是的话,为什么?)或者如果我以某种方式滥用了生成器(如果是的话,如何使用?)

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2014-10-20 22:08:45

我不知道哪里出了问题(还不知道!),但您仍然可以按如下方式按时间进行初始化,而不会碰到问题(从这里借来的)。

代码语言:javascript
复制
#include <ctime>
#include <iostream>
#include <random>
#include <chrono>

using namespace std;

unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();

default_random_engine gen(seed1); //gen(time(NULL));
uniform_int_distribution<int> dist(10,200);

int main()
{
    for(int i = 0; i < 5; i++)
        cout<<dist(gen)<<endl;

    return 0;
}

您也可以使用随机设备,这是不确定的(它从您的键笔画,鼠标移动和其他来源的时间信息,以产生不可预测的数字)。这是你可以选择的最强大的种子,但如果你不需要强有力的保证,计算机时钟是更好的选择,因为如果你经常使用它,计算机就会没有“随机性”(生成一个真正的随机数需要很多键击和鼠标移动)。

代码语言:javascript
复制
std::random_device rd;
default_random_engine gen(rd());

正在运行

代码语言:javascript
复制
cout<<time(NULL)<<endl;
cout<<std::chrono::system_clock::now().time_since_epoch().count()<<endl;
cout<<rd()<<endl;

在我的机器上生成

代码语言:javascript
复制
1413844318
1413844318131372773
3523898368

因此,chrono库提供了比ctime库更大的数量和更快的变化数(以纳秒为单位)。random_device正在产生不确定的数字,在地图上到处都是.因此,似乎ctime正在生产的种子可能在某种程度上过于接近,从而部分映射到相同的内部状态?

我做了另一个程序,看起来是这样的:

代码语言:javascript
复制
#include <iostream>
#include <random>
using namespace std;

int main(){
  int oldval           = -1;
  unsigned int oldseed = -1;

  cout<<"Seed\tValue\tSeed Difference"<<endl;
  for(unsigned int seed=0;seed<time(NULL);seed++){
    default_random_engine gen(seed);
    uniform_int_distribution<int> dist(10,200);
    int val = dist(gen);
    if(val!=oldval){
      cout<<seed<<"\t"<<val<<"\t"<<(seed-oldseed)<<endl;
      oldval  = val;
      oldseed = seed;
    }
  }
}

正如您所看到的,这只是输出到当前时间为止的每个可能的随机种子的第一个输出值,以及具有相同值的种子和先前种子的数量。输出的摘录如下:

代码语言:javascript
复制
Seed  Value Seed Difference
0 10  1
669 11  669
1338  12  669
2007  13  669
2676  14  669
3345  15  669
4014  16  669
4683  17  669
5352  18  669
6021  19  669
6690  20  669
7359  21  669
8028  22  669
8697  23  669
9366  24  669
10035 25  669
10704 26  669
11373 27  669
12042 28  669
12711 29  669
13380 30  669
14049 31  669

因此,对于每一个新的第一个数,就有669个种子给出了第一个数。因为第二数和第三数是不同的,所以我们仍然产生唯一的内部状态。我认为我们必须对default_random_engine有更多的了解,才能理解669的特殊之处(这可以被考虑到3和223中)。

考虑到这一点,chronorandom_device库为什么运行得更好是很清楚的:它们生成的种子之间的距离总是超过669。请记住,即使第一个数字是相同的,在许多程序中,重要的是由不同的数字生成的序列。

票数 9
EN

Stack Overflow用户

发布于 2014-10-21 09:58:16

使用std::default_random_engine就像说“给我一个惊喜!”在一家糟糕的餐馆里。唯一可以肯定的是,结果会很差--因为<random>提供的生成器都有缺陷--但是您甚至不知道必须处理哪些特定的缺陷。

梅森曲棍球可以是一个不错的选择,如果-只有当-它是适当的种子,其中就有摩擦。理想情况下,种子的每一点都应该以相同的概率影响生成器状态的每一点;正如您所发现的,在std::mersenne_twister_engine的常见实现中,情况并非如此。

Mersenne通常是通过一个简单的PRNG的输出初始化的,而PRNG又被任何可用的熵所播种。这实际上将简单PRNG的种子熵扩展到了龙卷风的巨大状态上。标准的制造者为此目的深思熟虑地提供了seed_seq接口;然而,库似乎不包含任何适配器,用于将生成器用作种子序列。

两个不同的播种概念之间也存在着差异。在生成器方面,种子函数应该接受传入的熵,并将其忠实地映射到生成器状态,确保在过程中不会丢失熵。在用户端,它是“获取这些数字并给出非常不同的序列”,其中‘这些数字’是{ 1,2,3,.}或clock()输出。

换句话说,种子熵是以一种不适合直接初始化生成器状态的形式提供的;小的种子差异给出了小的状态差异。这对于像Mersenne这样的大型滞后发电机或为std::ranluxXX生成器提供动力的滞后斐波纳契( Fibonacci )来说尤其有问题。

一个位混合函数--一种双射函数,其中输出的每一位都以相同的概率依赖于输入的每一位--可以帮助使种子(如1、2、3或clock() )的输出对于播种更有用。杂音散列混频器接近这个理想,实现了几乎完美的扩散(32位版本显示):

代码语言:javascript
复制
uint32_t murmur_mix32 (uint32_t x)
{
   x ^= x >> 16;
   x *= 0x85EBCA6B;
   x ^= x >> 13;
   x *= 0xC2B2AE35;
   x ^= x >> 16;

   return x;
}

这个函数是双射的,因此它根本不失去任何熵。这意味着你可以用它来改良任何种子,而不会使事情变得更糟。

另一个快速修复--不需要做一个seed_seq --是用依赖于(杂音混合的)种子的参数调用生成器上的discard()。然而,对像Mersenne这样的巨型发电机的影响是有限的,因为它们的状态演化非常缓慢,它们需要几十万次迭代才能从缺陷状态中完全恢复。

票数 2
EN

Stack Overflow用户

发布于 2014-10-20 22:08:48

您使用的种子可能会引入偏差,如果使用不同的种子产生相同的结果,那么生成器本身就不会被正确地写入。

我建议用不同的种子进行测试,得出一个结论。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/26475595

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档