【学习笔记】随机化

发表于

cf上用random_shuffle挂了
看来随机化还是要好好了解一下

头文件从c++11起

time相关：
std::time
定义于头文件
std::time_t time( std::time_t* arg );

CLOCKS_PER_SEC
定义于头文件

#define CLOCKS_PER_SEC /implementation defined/
展开成 std::clock_t 类型表达式，值等于每秒 std::clock() 所返回的时钟计次数（不必是编译时常量）。

std::clock
定义于头文件
std::clock_t clock();
返回进程从关联到程序执行的实现定义时期开始，所用的粗略处理器时间。为转换结果为秒，可将它除以 CLOCKS_PER_SEC 。

ftime()
定义于头文件
函数定义：void ftime(struct timeb *tp);
函数说明：ftime()将目前日期由tp所指的结构体返回。

1
2
3
4
5
6
struct timeb{
    time_t time;   /* 为1970-01-01至今的秒数*/
    unsigned short millitm; /* 千分之一秒即毫秒 */
    short timezone;  /* 为目前时区和Greenwich相差的时间，单位为分钟 */
    short dstflag;   /* 为日光节约时间的修正状态，如果为非0代表启用日光节约时间修正 */
};

c&c++03的随机化：
std::srand
定义于头文件
void srand( unsigned seed );
注意：
通常来说，应该只播种一次随机数生成器，在程序开始出，任何到 rand() 的调用前。不应重复播种，或每次冀愿生成新一批随机数时重播种。
标准实践是使用以 time(0) 为种子调用的结果。然而 time() 返回 time_t 值，而不保证 time_t 是整数类型。尽管实践中，主流实现都定义 time_t 为整数类型，且此亦为 POSIX 所要求。
1.srand(time(0)); //time();
2.srand(tim.time*1000+tim.millitm); //ftime();

RAND_MAX（保证此值至少为 32767）
win下32767，linux下2147483647

std::rand
定义于头文件
int rand();
返回 0 与 RAND_MAX （包含 0 与 RAND_MAX ）的随机数。
推荐用 C++11 的随机数生成设施替换 rand() 。 (C++11 起)

random_shuffle
定义于头文件
基于rand()
类似的实现：

1
2
3
4
5
6
7
template<typename T> IL void random_shuffl(T first,T last)
{
	int n=last-first;
	for(int i=1;i<n;++i){
		swap(*(first+i),*(first+rand()%(i+1)));	
	}
}

由于rand()有可能太小，移动的偏差可能很小（cf上的测试，3e6的数列，每个值平均移动2%，期望移动是1/3）
自己手写random_shuffle:

1
2
3
4
5
6
7
8
9
10
11
IL int ra()
{
	return (rand()<<15)+rand();	
}
template<typename T> IL void random_shuffl(T first,T last)
{
	int n=last-first;
	for(int i=1;i<n;++i){
		swap(*(first+i),*(first+ra()%(i+1)));	
	}
}

c++11起可以使用mt19937作为更优质的随机数生成器替代rand()
定义于头文件
mt19937:32位梅森缠绕器
mt19937_64:64位梅森缠绕器
成员函数：

构造与播种：

  • (构造函数)：构造引擎 (公开成员函数)
  • seed：设置引擎的当前状态 (公开成员函数)

生成：

  • operator()：令引擎状态向前并返回生成值 (公开成员函数)

特征：

  • min[静态]：获取输出范围中的最小可能值 (公开静态成员函数)
  • max[静态]：获取输出范围中的最大可能值 (公开静态成员函数)

例：

1
2
3
4
5
mt19937 mt;
mt.seed(/*随机数种子*/); // 或者在定义时mt19937 mt(/*随机数种子*/);
mt.min();mt.max();      // 0 2^32-1
mt();                   // 返回[min(),max()]中的随机数
//mt19937_64就是[0,2^64-1]的随机数生成器