今天呢在OIwiki上看到了1个诡异的生成随机数函数：mt19937，看到之后我直接就一脸懵了，这啥玩意？？？
最开始我以为这是1个叫M.T.的人在19937/1937年发明的函数，但是再往后看，发现这个mt好像意思是梅森缠绕器（好像还有人说叫梅森旋转算法），而19937是一个质数，19937的意思是2^19937-1，随后我就随便在网上复制了一段代码，粘到DEV里面，然后我就震惊的发现，代码CE了
然后我抱着试一下的想法，又复制到了最新版VS2022上面，然后我又震惊的发现，这玩意竟然就真过了编译，生成了一个数，看完之后，我决定测试一下这个的随机性怎么样，于是就有了下面这段代码
#include#include #include #include using namespace std; int cnt[30050]; struct val { int x;//下标 int y;//数量 }all; int main() { srand(time(0)); std :: mt19937 rng(time(0)); //1-5000,5001-10000,10001-15000,15001-20000,20001-25000,25001-30000; for (int i = 0; i < 1000000; i++) { unsigned int x = rng() % 30000 + 1; //unsigned int x = rand() % 30000 + 1; if (1 <= x && x <= 5000) cnt[1]++; else if (5001 <= x && x <= 10000) cnt[2]++; else if (10001 <= x && x <= 15000) cnt[3]++; else if (15001 <= x && x <= 20000) cnt[4]++; else if (20001 <= x && x <= 25000) cnt[5]++; else cnt[6]++; } cout << "第一个数：1-5000 第二个数：5001-10000 第三个数：10001-15000 第四个数：15001-20000 第五个数：20001-25000 第六个数：25001-30000" << endl; cout << cnt[1] << " " << cnt[2] << " " << cnt[3] << " " << cnt[4] << " " << cnt[5] << " " << cnt[6] << endl; memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < 1000000; i++) { unsigned int x = rng() % 30000 + 1; //unsigned int x = rand() % 30000 + 1; cnt[x]++; } int maxn = -1, minn = 1000050; for (int i = 1; i <= 30000; i++) { if (cnt[i] > maxn) maxn = cnt[i]; if (cnt[i] < minn) minn = cnt[i]; } cout << "maxn：在1-30000中出现最多的数，minn：在1-30000中出现最少的数" << endl; cout << "maxn - minn = " << maxn - minn << endl; long long sum1 = 0, middle, sum2 = 0; for (int i = 1; i <= 30000; i++) { sum1 += i * cnt[i]; if (sum2 < 500000 && sum2 + cnt[i] >= 500000) middle = i + 1; sum2 += cnt[i]; } double average = (double)sum1 / 1000000.0; cout << "平均数：" << average << endl; cout << "中位数：" << middle << endl; maxn = -1; for (int i = 1; i <= 30000; i++) if (cnt[i] > maxn) maxn = cnt[i]; for (int i = 1; i <= 30000; i++) if (cnt[i] == maxn) all.x = i, all.y = maxn; cout << "众数：" << all.x; return 0; }
经过n多次测试，下面就是差距最大的几组：
可以看到，mt19937的随机性还是很不错的，分布均匀，众数很随机，平均数、中位数很接近，maxn-minn比较小，测试完随机性，我决定再测一测速度，代码就加上几行就行了
#include#include #include #include using namespace std; int cnt[30050]; struct val { int x;//下标 int y;//数量 }all; int main() { srand(time(0)); std :: mt19937 rng(time(0)); //1-5000,5001-10000,10001-15000,15001-20000,20001-25000,25001-30000; for (int i = 0; i < 1000000; i++) { unsigned int x = rng() % 30000 + 1; //unsigned int x = rand() % 30000 + 1; if (1 <= x && x <= 5000) cnt[1]++; else if (5001 <= x && x <= 10000) cnt[2]++; else if (10001 <= x && x <= 15000) cnt[3]++; else if (15001 <= x && x <= 20000) cnt[4]++; else if (20001 <= x && x <= 25000) cnt[5]++; else cnt[6]++; } cout << "第一个数：1-5000 第二个数：5001-10000 第三个数：10001-15000 第四个数：15001-20000 第五个数：20001-25000 第六个数：25001-30000" << endl; cout << cnt[1] << " " << cnt[2] << " " << cnt[3] << " " << cnt[4] << " " << cnt[5] << " " << cnt[6] << endl; memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < 1000000; i++) { unsigned int x = rng() % 30000 + 1; //unsigned int x = rand() % 30000 + 1; cnt[x]++; } int maxn = -1, minn = 1000050; for (int i = 1; i <= 30000; i++) { if (cnt[i] > maxn) maxn = cnt[i]; if (cnt[i] < minn) minn = cnt[i]; } cout << "maxn：在1-30000中出现最多的数，minn：在1-30000中出现最少的数" << endl; cout << "maxn - minn = " << maxn - minn << endl; long long sum1 = 0, middle, sum2 = 0; for (int i = 1; i <= 30000; i++) { sum1 += i * cnt[i]; if (sum2 < 500000 && sum2 + cnt[i] >= 500000) middle = i + 1; sum2 += cnt[i]; } double average = (double)sum1 / 1000000.0; cout << "平均数：" << average << endl; cout << "中位数：" << middle << endl; maxn = -1; for (int i = 1; i <= 30000; i++) if (cnt[i] > maxn) maxn = cnt[i]; for (int i = 1; i <= 30000; i++) if (cnt[i] == maxn) all.x = i, all.y = maxn; cout << "众数：" << all.x; clock_t start = clock(); for (int i = 0; i < 10000000; i++) { unsigned int x = rng() % 30000 + 1; //unsigned int x = rand() % 30000 + 1; } cout << endl << "生成10000000个随机数的速度（ms）：" << clock() - start; return 0; }
这个时候我发现这个mt19937几乎是个O(1)的算法，我准备再测一下rand函数的性能
首先是随机性
代码：
#include#include #include #include using namespace std; int cnt[30050]; struct val { int x;//下标 int y;//数量 }all; int main() { srand(time(0)); std :: mt19937 rng(time(0)); //1-5000,5001-10000,10001-15000,15001-20000,20001-25000,25001-30000; for (int i = 0; i < 1000000; i++) { unsigned int x = rng() % 30000 + 1; //unsigned int x = rand() % 30000 + 1; if (1 <= x && x <= 5000) cnt[1]++; else if (5001 <= x && x <= 10000) cnt[2]++; else if (10001 <= x && x <= 15000) cnt[3]++; else if (15001 <= x && x <= 20000) cnt[4]++; else if (20001 <= x && x <= 25000) cnt[5]++; else cnt[6]++; } cout << "第一个数：1-5000 第二个数：5001-10000 第三个数：10001-15000 第四个数：15001-20000 第五个数：20001-25000 第六个数：25001-30000" << endl; cout << cnt[1] << " " << cnt[2] << " " << cnt[3] << " " << cnt[4] << " " << cnt[5] << " " << cnt[6] << endl; memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < 1000000; i++) { unsigned int x = rng() % 30000 + 1; //unsigned int x = rand() % 30000 + 1; cnt[x]++; } int maxn = -1, minn = 1000050; for (int i = 1; i <= 30000; i++) { if (cnt[i] > maxn) maxn = cnt[i]; if (cnt[i] < minn) minn = cnt[i]; } cout << "maxn：在1-30000中出现最多的数，minn：在1-30000中出现最少的数" << endl; cout << "maxn - minn = " << maxn - minn << endl; long long sum1 = 0, middle, sum2 = 0; for (int i = 1; i <= 30000; i++) { sum1 += i * cnt[i]; if (sum2 < 500000 && sum2 + cnt[i] >= 500000) middle = i + 1; sum2 += cnt[i]; } double average = (double)sum1 / 1000000.0; cout << "平均数：" << average << endl; cout << "中位数：" << middle << endl; maxn = -1; for (int i = 1; i <= 30000; i++) if (cnt[i] > maxn) maxn = cnt[i]; for (int i = 1; i <= 30000; i++) if (cnt[i] == maxn) all.x = i, all.y = maxn; cout << "众数：" << all.x; //clock_t start = clock(); //for (int i = 0; i < 10000000; i++) { //unsigned int x = rng() % 30000 + 1; //unsigned int x = rand() % 30000 + 1; //} //cout << endl << "生成10000000个随机数的速度（ms）：" << clock() - start; return 0; }
对比一下和mt19937函数，发现不论是均匀分布还是最大值-最小值，rand都要比mt19937差一大截
最后是rand的时间
代码：
#include#include #include #include using namespace std; int cnt[30050]; struct val { int x;//下标 int y;//数量 }all; int main() { srand(time(0)); std :: mt19937 rng(time(0)); //1-5000,5001-10000,10001-15000,15001-20000,20001-25000,25001-30000; for (int i = 0; i < 1000000; i++) { //unsigned int x = rng() % 30000 + 1; unsigned int x = rand() % 30000 + 1; if (1 <= x && x <= 5000) cnt[1]++; else if (5001 <= x && x <= 10000) cnt[2]++; else if (10001 <= x && x <= 15000) cnt[3]++; else if (15001 <= x && x <= 20000) cnt[4]++; else if (20001 <= x && x <= 25000) cnt[5]++; else cnt[6]++; } cout << "第一个数：1-5000 第二个数：5001-10000 第三个数：10001-15000 第四个数：15001-20000 第五个数：20001-25000 第六个数：25001-30000" << endl; cout << cnt[1] << " " << cnt[2] << " " << cnt[3] << " " << cnt[4] << " " << cnt[5] << " " << cnt[6] << endl; memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < 1000000; i++) { //unsigned int x = rng() % 30000 + 1; unsigned int x = rand() % 30000 + 1; cnt[x]++; } int maxn = -1, minn = 1000050; for (int i = 1; i <= 30000; i++) { if (cnt[i] > maxn) maxn = cnt[i]; if (cnt[i] < minn) minn = cnt[i]; } cout << "maxn：在1-30000中出现最多的数，minn：在1-30000中出现最少的数" << endl; cout << "maxn - minn = " << maxn - minn << endl; long long sum1 = 0, middle, sum2 = 0; for (int i = 1; i <= 30000; i++) { sum1 += i * cnt[i]; if (sum2 < 500000 && sum2 + cnt[i] >= 500000) middle = i + 1; sum2 += cnt[i]; } double average = (double)sum1 / 1000000.0; cout << "平均数：" << average << endl; cout << "中位数：" << middle << endl; maxn = -1; for (int i = 1; i <= 30000; i++) if (cnt[i] > maxn) maxn = cnt[i]; for (int i = 1; i <= 30000; i++) if (cnt[i] == maxn) all.x = i, all.y = maxn; cout << "众数：" << all.x; clock_t start = clock(); for (int i = 0; i < 10000000; i++) { //unsigned int x = rng() % 30000 + 1; unsigned int x = rand() % 30000 + 1; } cout << endl << "生成10000000个随机数的速度（ms）：" << clock() - start; return 0; }
然后后我们可以得出1个结论，rand比mt19937除了适用性外都差很多
最后介绍一下用法，就是再代码前面加上这样一行代码初始化
std :: mt19937 rng(time(0));
然后再调用rng()就行了，生成的是unsigned int的范围的随机数，如果用int会有负数
具体的就看OIWIKI吧
最后的最后，大家留个赞再走吧
