记一下那些伪随机数生成函数 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 记一下那些伪随机数生成函数

记一下那些伪随机数生成函数

浏览:7238次出处信息

今天踩了一个伪随机数生成函数的坑，与其说是个坑到不如说自己功力不够深厚，对这些随机数生成的函数族欠缺了解，先来介绍下我的问题吧。

拿了100M的数据用LDA算法来跑，单线程的时候一次迭代需要大约15s的时间，而改用两个线程跑，线程之间对不同的数据块进行迭代，一次迭代完成的时间居然需要大约50s，而且线程数越多就会越慢，因为迭代的采样函数是一个纯计算的函数，多线程的情况下每个线程的数据量要比单线程成倍地缩小，迭代速度相比单线程应该快N倍才对，现在的结果是不符合常理的，因为每个线程都是独立的训练集，线程之前没有共享数据。

其实在我用几M的小数据测试的时候就发现这个问题，当时以为是数据量小迭代速度太快，以至于在迭代完成后的线程同步占用了一些时间才导致多线程版本会慢于单线程版本，但数据量大的时候这样就不可理解了。

后来开了两个线程发现，迭代计算的时候两个CPU大部分时间居然都没有跑在用户空间，相反大量的cpu时间都耗在了系统时间，仔细看了代码，这部分就只有一个random()函数不是我的计算函数，改成定值之后测试速度马上彪上去了，那就可以断写问题就出在这里。

random()函数是不可重入的函数，不保证它是线程安全的，但我看了glibc的代码发现，其实它在glibc的实现里面是线程安全的：

long int
__random ()
{
  int32_t retval;
 
  __libc_lock_lock (lock);
 
  (void) __random_r (&unsafe_state, &retval);
 
  __libc_lock_unlock (lock);
 
  return retval;
}
 
weak_alias (__random, random)

这样就很清楚了，glibc的random()实现实际是线程安全的，但不可重入，因为在一开始就拿了一把锁，也就是因为这把锁导致了我的程序性能下降如此厉害。

那rand()函数又是怎样的呢？rand()的manual手册里面的介绍也是说，rand()不是线程安全的函数，但其实glibc的实现里面它仍然是线程安全的，再看看glibc的代码：

/* Return a random integer between 0 and RAND_MAX.  */
int
rand ()
{
  return (int) __random ();
}

这样就很清楚了，在glibc的实现里面，rand()和random()实际上是同一个函数，虽然返回值不一样，但其实random()返回的也只是个32位的值而已，二者没什么不同。只是POSIX标准说它不是线程安全的，但不同的实现有不同的做法，比如glibc就是例外。

要想使它随机生成函数线程安全，就要使用它们的可重入版本，看看rand_r()这个函数的实现(以前一直不理解这个_r后缀的意思，现在知道了它是可重入的意思。。。)：

int
rand_r (unsigned int *seed)                                             
{ 
  unsigned int next = *seed;                                           
  int result;
 
  next *= 1103515245;
  next += 12345;
  result = (unsigned int) (next / 65536) % 2048;
 
  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;
 
  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;
 
  *seed = next;
 
  return result;
}

只需要给每个线程保存各自独立的seed，那rand_r这个函数就可重入喽，但这个函数的算法显然比较弱，看它的手册里面是这样说的：

This is a very small amount of state, so this function will be a weak pseudo-random generator. Try drand48_r(3) instead.

看看drand48这一系列的函数：

YNOPSIS
       #include <stdlib.h>
 
       double drand48(void);
 
       double erand48(unsigned short xsubi[3]);
 
       long int lrand48(void);
 
       long int nrand48(unsigned short xsubi[3]);
 
       long int mrand48(void);
 
       long int jrand48(unsigned short xsubi[3]);
 
       void srand48(long int seedval);
 
       unsigned short *seed48(unsigned short seed16v[3]);
 
       void lcong48(unsigned short param[7]);

应该来说，像erand48，nrand48这些应该都可以设计成线程安全的，我没有仔细去读这些函数的源码，因为实现都比较复杂，但有一点可以确定，他们在生成随机数的时候不仅仅只需要个种子，一方面它们需要一个类型为struct drand48_data的种子，另一方面也需要一个unsigned short xsubi[3]这样的状态数组，通过这两组变量来生成随机数，struct drand48_data我理解的是它是只读的，只要在多线程的过程中不修改它，那么就可以把erand48(),nrand48()这些函数作为线程安全的来用，但如果在运行过程中调用lcong48()改变了drand48_data的值，那恐怕就不能保证线程安全了。

drand48系统也有对应的可重入版本：

       #include <stdlib.h>
 
       int drand48_r(struct drand48_data *buffer, double *result);
 
       int erand48_r(unsigned short xsubi[3],
                     struct drand48_data *buffer, double *result);
 
       int lrand48_r(struct drand48_data *buffer, long int *result);
 
       int nrand48_r(unsigned short int xsubi[3],
                     struct drand48_data *buffer, long int *result);
 
       int mrand48_r(struct drand48_data *buffer,long int *result);
 
       int jrand48_r(unsigned short int xsubi[3],
                     struct drand48_data *buffer, long int *result);
 
       int srand48_r(long int seedval, struct drand48_data *buffer);
 
       int seed48_r(unsigned short int seed16v[3],
                    struct drand48_data *buffer);
 
       int lcong48_r(unsigned short int param[7],
                     struct drand48_data *buffer);

这样子问题就简单了，只要每个线程都维护自己的drand48_data变量和xsubi数组，那erand48_r(), nrand48_r就可以保证线程安全又可重入了。哦，再补充一点，这些函数不应该算是严格的可重入，应该叫隐式可重入？如果这些传递进来的指针都指向一块共享地址的话，那这些函数同样是不可重入的喽。

建议继续学习：

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：为什么Fibonacci数列相邻两项之比会趋于0.618？

后一篇：信用卡校验位算法THE LUHN MOD-10 >>

文章信息

作者：levin 来源： basic coder
标签：随机数
发布时间：2013-04-06 23:16:11

建议继续学习

近3天十大热文