c - Fisher Yates 算法在系统时间播种时在并行启动的程序中返回相同顺序的数字

Question

我并行启动几个依赖于随机数的 C/C++ 程序。对这个话题还算陌生，听说过段时间应该做seed。

此外，我使用 Fisher Yates 算法获得具有唯一随机打乱值的列表。但是，并行启动程序两次会为两个列表返回相同的结果。

我该如何解决这个问题？我可以使用不同但仍然可靠的种子吗？

我的简单测试代码如下所示:

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include <time.h>
static int rand_int(int n) {

        int limit = RAND_MAX - RAND_MAX % n;
        int rnd;

        do {
                rnd = rand();
        }
        while (rnd >= limit);
        return rnd % n;
}


void shuffle(int *array, int n) {

        int i, j, tmp;
        for (i = n - 1; i > 0; i--) {
                j = rand_int(i + 1);
                tmp = array[j];
                array[j] = array[i];
                array[i] = tmp;
        }
}


int main(int argc,char* argv[]){

        srand(time(NULL));
        int x = 100;
        int randvals[100];
        for(int i =0; i < x;i++)
                randvals[i] = i;

        shuffle(randvals,x);
        for(int i=0;i < x;i++)
                printf("%d %d \n",i,randvals[i]);

}

我从这里使用了 fisher yates 算法的实现:

http://www.sanfoundry.com/c-program-implement-fisher-yates-algorithm-array-shuffling/

我像这样并行启动程序:

./randomprogram >> a.txt & ./randomprogram >> b.txt

然后比较两个具有相同内容的文本文件。

最终应用是深度学习领域的数据增强。该机器运行带有 C++11 的 Ubuntu 16.04。

Answer 1

由于您对 RNG 进行播种的方式不同，您将获得相同的结果:

srand(time(NULL));

time 函数返回自纪元以来的秒数。如果程序的两个实例在同一秒内启动(如果快速连续启动它们，则很可能)那么两者将使用相同的种子并获得相同的随机值集。

你需要给你的种子添加更多的熵。一种简单的方法是将进程 ID 与时间按位异或:

srand(time(NULL) ^ getpid());