需要一个快速的 C++ 随机生成器

2021-12-21 00:00:00 performance random c++

我正在尝试在我的 TSP 生成器上对欧几里德距离进行一些 opt-3 交换，并且由于在许多情况下我有超过 500 个节点，因此我需要随机选择我想要的 3 个节点中的至少 1 个尝试交换.

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.

所以基本上我需要一个快速的随机数函数.(普通的 rand() 太慢了)它不必很棒，只要 足够.

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.

我忘了说，我所处的环境除了标准语言库(例如 STL、iostream 等)之外，我无法添加任何库.所以没有提升 =/

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 =/

推荐答案

另一个帖子提到了 Marsaglia 的 xorshf 生成器，但没有人贴出代码.

The other thread mentioned Marsaglia's xorshf generator, but no one posted the code.

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;
}

我到处都在使用这个.唯一失败的地方是我尝试生成随机二进制矩阵时.超过大约 95x95 的矩阵，它开始生成太少或太多的奇异矩阵(我忘记了哪个).已经证明该发生器等效于线性移位反馈寄存器.但是除非你在做密码学或认真的蒙特卡洛工作，否则这个生成器会很厉害.

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.

相关文章