是否有使用时间来播种随机数生成的替代方案?
我试图在计算集群中同时运行一段代码(2000个实例左右)的几个实例。 它的工作方式是我提交作业,群集将在节点每隔一段时间打开时运行它们,每个节点有几个作业。 对于使用时间种子的随机数生成中的大量实例,这似乎产生相同的值。
我可以使用一个简单的替代方案吗? 重复性和安全性并不重要,快速生成独特的种子。 什么是最简单的方法,如果可能的话,跨平台方法会很好。
rdtsc
指令是一个非常可靠(和随机)的种子。
在Windows中,可以通过__rdtsc()
内在函数访问它。
在GNU C中,可通过以下方式访问:
unsigned long long rdtsc(){ unsigned int lo,hi; __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi)); return ((unsigned long long)hi << 32) | lo; }
该指令测量自处理器通电以来的总伪周期。 鉴于当今机器的频率很高,即使它们同时启动并且以相同的速度运行,两个处理器也不太可能返回相同的值。
我假设你有一些进程启动其他进程。 让它通过种子使用。 然后,您可以让主进程只为每个进程传递一个随机数,以用作其种子。 那样的话,实际上只选择了一个任意的种子……你可以利用时间。
如果您没有主进程启动其他进程,那么如果每个进程至少有一个唯一索引,那么您可以做的是让一个进程在内存中生成一系列随机数(如果共享内存)或在文件中(如果是共享磁盘)然后让每个进程拉出索引的随机数以用作它们的种子。
没有什么能比单一种子的一系列随机数更均匀地分配种子。
PID和时间的组合应足以获得唯一的种子。 它不是100%跨平台的,但* nix平台上的getpid(3)
和Windows上的GetProcessId
将使你获得99.9%的路径。 像这样的东西应该工作:
srand((time(NULL) & 0xFFFF) | (getpid() << 16));
您还可以在* nix系统上读取/dev/urandom
数据,但是在Windows上没有相同的数据。
unsigned seed; read(open("/dev/urandom", O_RDONLY), &seed, sizeof seed); srand(seed); // IRL, check for errors, close the fd, etc...
我还建议使用更好的随机数发生器。
如果可以使用C ++ 11,那么考虑std::random_device
。 我建议你看一下综合指南的链接 。
从video链接中提取基本消息:你永远不应该使用srand
& rand
,而是使用std::random_device
和std::mt19937
– 在大多数情况下,以下是你想要的:
#include #include int main() { std::random_device rd; std::mt19937 mt(rd()); std::uniform_int_distribution dist(0,99); for (int i = 0; i < 16; i++) { std::cout << dist(mt) << " "; } std::cout << std::endl; }
而不是从C std lib time()函数以秒为单位测量的直接时间,您可以使用处理器的计数器吗? 大多数处理器都有自由运行的滴答计数,例如在x86 / x64中有时间戳计数器 :
自Pentium以来,时间戳计数器是所有x86处理器上的64位寄存器。 它计算自重置后的滴答数。
(该页面还有很多方法可以在不同平台上访问此计数器 – gcc / ms visual c / etc)
请记住,时间戳计数器并非没有缺陷,它可能不会在处理器之间同步(您可能不关心您的应用程序)。 省电function可能会使处理器上升或下降(再次您可能不关心)。
只是一个想法……生成一个GUID(16字节)并将其4字节或8字节块(取决于种子的预期宽度)求和,允许整数环绕。 将结果用作种子。
GUID通常封装生成它们的计算机的特征(例如MAC地址),这使得两个不同的机器最终生成相同的随机序列变得不太可能。
这显然不可移植,但为您的系统找到合适的API /库应该不会太难(例如Win32上的UuidCreate
,Linux上的uuid_generate
)。
视窗
提供CryptGenRandom()
和RtlGenRandom()
。 它们将为您提供一组随机字节,您可以将其用作种子。
您可以在msdn 页面上找到文档。
Linux / Unixes
您可以使用Openssl的RAND_bytes()
在linux上获取随机字节数。 它默认使用/dev/random
。
把它放在一起:
#ifdef _WIN32 #include #else #include #endif uint32_t get_seed(void) { uint32_t seed = 0; #ifdef _WIN32 RtlGenRandom(&seed, sizeof(uint32_t) ); #else RAND_bytes(&seed, sizeof(uint32_t) ); #endif return seed; }
请注意,openssl默认提供密码安全的PRNG,因此您可以直接使用它。 更多信息在这里 。
假设你是一个合理的POSIX-ish系统,你应该有clock_gettime
。 这将以纳秒为单位给出当前时间,这意味着出于所有实际目的,不可能两次获得相同的值。 (理论上,糟糕的实现可能会有更低的分辨率,例如只需将毫秒乘以100万,但即使像Linux这样的半体系也会产生真正的纳秒结果。)
如果唯一性很重要,则需要安排每个节点知道其他人声明了哪些ID。 您可以通过一个协议询问“任何人声称ID x?”来做到这一点。 或预先为每个节点安排选择尚未分配给其他节点的ID。
(GUID使用机器的MAC,因此将属于“提前安排”类别。)
如果没有某种forms的协议,您将冒两个节点使用相同ID的风险。