Vik*_*tor 3 random c++-cli shuffle srand
我有一张带有52卡的Deck矢量,我想把它洗牌.
vector<Card^> cards;
所以我用过这个:
random_shuffle(cards.begin(), cards.end());
问题是它每次都给我相同的结果,所以我曾经srand随机化它:
srand(unsigned(time(NULL)));
random_shuffle(cards.begin(),cards.end());
这仍然不是真正随意的.当我开始交易卡时,它与上次运行时相同.例如:"1.交易:A,6,3,2,K; 2.交易:Q,8,4,J,2",当我重新启动程序时,我得到完全相同的交易顺序.
然后我用srand(),并random_shuffle与它的第3个参数:
int myrandom (int i) {
return std::rand()%i;
}
srand(unsigned(time(NULL)));
random_shuffle(cards.begin(),cards.end(), myrandom);
现在它正在工作并且总是在重新运行时给我不同的结果,但我不知道为什么它以这种方式工作.这些功能如何运作,我在这做了什么？
这个答案需要一些调查,查看VC++中的C++标准库头文件并查看C++标准本身.我知道标准说了什么,但我很好奇VC++(包括C++ CLI)的实现.
首先是标准所说的内容std::random_shuffle.我们可以在这里找到.特别是它说:
重新排列给定范围[第一个,最后一个]中的元素,使得这些元素的每个可能的排列具有相同的出现概率.
1)随机数发生器是实现定义的,但功能的std ::兰特被经常使用.
粗体部分是关键.该标准表明RNG可以是特定于实现的(因此不同编译器的结果会有所不同).标准的建议是std::rand被经常使用.但这不是必需的.因此,如果某个实现没有使用,std::rand那么它可能不会std::srand用于起始种子.一个有趣的脚注是,从std::random_shuffleC++ 14开始,这些函数已被弃用.但std::shuffle仍然存在.我的猜测是,因为std::shuffle要求你提供一个函数对象,你在生成随机数时明确定义了你想要的行为,这比旧的更有优势std::random_shuffle.
我拿了我的VS2013并查看了C++标准库头文件并发现它<algorithm>使用的模板类使用完全不同的伪rng(PRNG)而不是std::rand索引(种子)设置为零.虽然VC++的不同版本(包括C++/CLI)之间的细节可能有所不同,但我认为VC++/CLI的大多数版本可能会做类似的事情.这可以解释为什么每次运行应用程序时都会获得相同的洗牌.
如果我正在寻找伪RNG并且我没有进行加密,那么我会选择的选项是使用像Mersenne Twister那样成熟的东西:
优点 Mersenne Twister的常用版本MT19937产生一系列32位整数,具有以下理想特性:
它具有非常长的周期2 ^ 19937-1.虽然长周期不是随机数发生器的质量保证,但短周期(例如许多较旧的软件包中常见的2 ^ 32)可能是有问题的.
对于每1≤k≤623,它被k分布为32位精度(参见下面的定义).
它通过了许多统计随机性测试,包括Diehard测试.
幸运的是,C++ 11标准库(我相信它应该适用于VS2010及更高版本的C++/CLI)包含一个可以与之配合使用的Mersenne Twister函数对象.有关更多详细信息,std::shuffle请参阅此C++文档.前面提供的C++标准库参考实际上包含执行此操作的代码:
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(v.begin(), v.end(), g);
需要注意的是std::random_device产生非确定性(不可重复)的无符号整数.如果我们想要使用Mersenne Twister(std::mt19937)PRNG 种子,我们需要非确定性数据.这类似于在概念在接种rand与srand(time(NULL))(后者不是过于良好的随机源).
这看起来很好,但在处理卡洗牌时有一个缺点.Windows平台上的无符号整数是4个字节(32位),可以存储2 ^ 32个值.这意味着只有4,294,967,296个可能的起点(种子),因此只有很多方法可以改变平台.问题是有52个!(52个阶乘)方式来改变标准的52卡牌组.这恰好是80658175170943878571660636856403766975289505440883277824000000000000方式,这远远大于我们从设置32位种子获得的唯一方式的数量.
值得庆幸的是,Mersenne Twister可以接受0到2 ^ 19937-1之间的种子.52!是一个很大的数字,但所有组合可以用226位(或~29字节)的种子表示.std::mt19937如果我们愿意,标准库允许接受最多2 ^ 19937-1(~624字节数据)的种子.但由于我们只需要226位,因此以下代码将允许我们创建29个字节的非确定性数据,以用作适合的种子std::mt19937:
// rd is an array to hold 29 bytes of seed data which covers the 226 bits we need */
std::array<unsigned char, 29> seed_data;
std::random_device rd;
std::generate_n(seed_data.data(), seed_data.size(), std::ref(rd));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
// Set the seed for Mersenne *using the 29 byte sequence*
std::mt19937 g(seq);
然后你需要做的就是用以下代码调用shuffle:
std::shuffle(cards.begin(),cards.end(), g);
在Windows VC++/CLI上,您将收到一条警告,要求您使用上述代码进行抑制.所以在文件的顶部(在其他包括之前)你可以添加:
#define _SCL_SECURE_NO_WARNINGS 1