需要一个快速的 C++ 随机生成器
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1640258/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Need a fast random generator for c++
提问by Martin Andersson
I'm trying to do some opt-3 swapping on my TSP generator for euclidian distances, and since I in many cases have more than ~500 nodes, I need to randomly select at least 1 of the 3 nodes that I want to try swapping.
我正在尝试在我的 TSP 生成器上对欧几里德距离进行一些 opt-3 交换，并且由于在许多情况下我有超过 500 个节点，因此我需要随机选择我想尝试交换的 3 个节点中的至少 1 个.
So basically I need a random-number function that's fast. (the normal rand() is way too slow) It doesn't have to be awesome, just good enough.
所以基本上我需要一个快速的随机数函数。（普通的 rand() 太慢了）它不必很棒，只要足够好。
EDIT: I forgot to mention, i'm sitting at an environment where I can't add any libraries except the Standard Language Library (such as STL, iostream etc). So no boost =/
编辑：我忘了提及，我所处的环境除了标准语言库（例如 STL、iostream 等）之外，我无法添加任何库。所以没有提升=/
回答by AndyV
The other thread mentioned Marsaglia's xorshf generator, but no one posted the code.
另一个线程提到了 Marsaglia 的 xorshf 生成器，但没有人发布代码。
static unsigned long x=123456789, y=362436069, z=521288629;
unsigned long xorshf96(void) { //period 2^96-1
unsigned long t;
x ^= x << 16;
x ^= x >> 5;
x ^= x << 1;
t = x;
x = y;
y = z;
z = t ^ x ^ y;
return z;
}
I've used this one all over the place. The only place it failed was when I was trying to produce random binary matrices. Past about 95x95 matrices, it starts generating too few or too many singular matrices (I forget which). It's been shown that this generator is equivalent to a linear shift feedback register. But unless you are doing cryptography or serious monte carlo work, this generator rocks.
我到处都在用这个。唯一失败的地方是我尝试生成随机二进制矩阵时。过去大约 95x95 矩阵，它开始生成太少或太多的奇异矩阵（我忘记了哪个）。已经证明该发生器等效于线性移位反馈寄存器。但是除非你在做密码学或认真的蒙特卡洛工作，否则这个生成器会摇摆不定。
回答by Sunsetquest
Two good alternatives from intel's site:
来自英特尔网站的两个不错的选择：
1) fastrand - it is 2.01 X faster than the std rand(). The routine returns one integer, similar output value range as C lib.
1) fastrand - 它比 std rand() 快 2.01 倍。该例程返回一个整数，与 C lib 类似的输出值范围。
inline int fastrand() {
g_seed = (214013*g_seed+2531011);
return (g_seed>>16)&0x7FFF;
}
2) an SSE version (see link below) is about 5.5 X as fast as std rand() however it generates 4 random values at a time, requires a processer with sse (almost all do), and is more complicated.
2) SSE 版本（见下面的链接）大约是 std rand() 的 5.5 倍，但它一次生成 4 个随机值，需要一个带有 sse 的处理器（几乎都是这样），而且更复杂。
回答by John D. Cook
See these generatorsfrom random number generator expert George Marsaglia. They're implemented as C macros, and they're lightning fast, just a few operations per number generated.
查看随机数生成器专家 George Marsaglia 的这些生成器。它们是作为 C 宏实现的，而且速度快如闪电，每个生成的数字只需几个操作。
回答by lhf
The Mersenne Twisterhas some fast implementations.
在梅森倍捻机具有一定的快速实现。
回答by Serge Rogatch
Starting with Ivy Bridgearchitecture Intel added RdRandCPU instruction and AMD added it later in June 2015. So if you are targeting a processor that is new enough and don't mind using (inline) assembly, the fastest way to generate random numbers should be in calling RdRandCPU instruction to get a 16- or 32- or 64-bit random number as described here. Scroll to approximately the middle of the page for code examples. At that link there is also a code example for checking the current CPU for support of RdRand instruction, and see also the Wikipedia for an explanation of how to do this with the CPUID instruction.
从Ivy Bridge架构开始，Intel 添加了RdRandCPU 指令，AMD 在 2015 年 6 月晚些时候添加了它。因此，如果您的目标是足够新的处理器并且不介意使用（内联）汇编，那么生成随机数的最快方法应该是在调用RdRandCPU指令描述得到一个16位或32位或64位的随机数这里。滚动到大约页面中间的代码示例。在该链接上还有一个代码示例，用于检查当前 CPU 是否支持 RdRand 指令，另请参阅维基百科以了解如何使用 CPUID 指令执行此操作。
Related question: Making use of sandy bridge's hardware true random number generator?(though according to Wikipedia, RdRandinstruction first appeared in Ivy Bridge, but not Sandy Bridge architecture as that question says)
相关问题：利用sandy bridge的硬件真随机数发生器？（虽然根据维基百科，RdRand指令首先出现在常春藤桥，但不是那个问题所说的桑迪桥架构）
Example C++ code based on _rdrand64_step():
基于_rdrand64_step() 的示例 C++ 代码：
#include <immintrin.h>
uint64_t randVal;
if(!_rdrand64_step(&randVal)) {
// Report an error here: random number generation has failed!
}
// If no error occured, randVal contains a random 64-bit number
回答by Charlie
Even tho this post is years old, it showed up when I was looking for a similar answer, and the answer I wound up using, isnt even in it. So I'm adding the one I found;
即使这篇文章已有多年历史，当我寻找类似的答案时它也出现了，而我最终使用的答案甚至不在其中。所以我添加了我找到的那个；
This approach will build a self contained random generator, and I found it to be a lot more random than rand()%x; over a few hundred thousand iterations. rand()%would never throw 16+ heads/tails in a row, when it should every other 65k attempts. This one not only does that, but it does it in a quarter of the time.
这种方法将构建一个自包含的随机生成器，我发现它比rand()%x; 超过几十万次迭代。rand()%绝不会连续抛出 16 个以上的正面/反面，而应该每隔 65k 次尝试。这不仅能做到这一点，而且还能在四分之一的时间内做到这一点。
This is how I implement #include <random>myself:
这就是我#include <random>自己实现的方式：
//create rng_gen, using mt technique, with range 0,1 (coin) and 1,6(dice);
std::random_device rd; //seed
std::mt19937 gen(rd()); //seed for rd(Mersenne twister)
std::uniform_int_distribution<> rng_coin(0, 1); //rng1 range
std::uniform_int_distribution<> rng_dice(1, 6); ///rng2 range
rng_coin(gen); //will apply rng1 range on (gen) object. Is very fast
rng_dice(gen); //will apply rng2 range, returns int.
//will output 1000 cointosses to console
for (int i=0;i<1000;++i)std::cout<<rng_coin(gen)<<"\n";
//will generate 1000 dice throws
for (int i=0;i<1000;++i)rng_dice(gen);
回答by abelenky
rand() is really darn fast, and I don't believe you'll find much faster.
rand() 真的很快，我不相信你会发现更快。
If it is in fact slowing you down (which I kinda doubt), then you need an architecture change.
如果它实际上让你慢下来（我有点怀疑），那么你需要改变架构。
I recommend pre-populating a long list with random numbers, then when you need one, simply take one from the list, rather than generating one. You may be able to re-fill the list with a background thread.
我建议用随机数预先填充一个长列表，然后当你需要一个时，只需从列表中取出一个，而不是生成一个。您可以使用后台线程重新填充列表。
回答by Mikeb
can you pregenerate a bunch of random bits ahead of time and peel them off 2 at a time (since you only need a random number between 1 and 3)?
您能否提前预生成一堆随机位并一次将它们剥离 2 个（因为您只需要 1 到 3 之间的随机数）？
回答by Kirill V. Lyadvinsky
回答by Kirill V. Lyadvinsky
I think WELL is pretty good, and WELL512a is pretty short. http://www.iro.umontreal.ca/~panneton/WELLRNG.htmlWELL44497a is complex at the time too. However, WELL generates a number between 0 and 1.
我认为 WELL 很不错，WELL512a 很短。http://www.iro.umontreal.ca/~panneton/WELLRNG.htmlWELL44497a 在当时也很复杂。但是，WELL 会生成一个介于 0 和 1 之间的数字。
