Мне сказали, что rand () mod n дает необъективные результаты, поэтому я попытался сделать этот код, чтобы проверить это. Генерирует s
цифры от 1 до l
и чем сортирует по вхождению.
#include <iostream>
#include <random>
using namespace std;
struct vec_struct{
int num;
int count;
double ratio;
};
void num_sort(vec_struct v[], int n){
for (int i = 0; i < n-1; i++){
for (int k = 0; k < n-1-i; k++){
if (v[k].num > v[k+1].num) swap(v[k], v[k+1]);
}
}
}
void count_sort(vec_struct v[], int n){
for (int i = 0; i < n-1; i++){
for (int k = 0; k < n-1-i; k++){
if (v[k].count < v[k+1].count) swap(v[k], v[k+1]);
}
}
}
int main(){
srand(time(0));
random_device rnd;
int s, l, b, c = 1;
cout << "How many numbers to generate? ";
cin >> s;
cout << "Generate " << s << " numbers ranging from 1 to? ";
cin >> l;
cout << "Use rand or mt19937? [1/2] ";
cin >> b;
vec_struct * vec = new vec_struct[s];
mt19937 engine(rnd());
uniform_int_distribution <int> dist(1, l);
if (b == 1){
for (int i = 0; i < s; i++){
vec[i].num = (rand() % l) + 1;
}
} else if (b == 2){
for (int i = 0; i < s; i++){
vec[i].num = dist(engine);
}
}
num_sort(vec, s);
for (int i = 0, j = 0; i < s; i++){
if (vec[i].num == vec[i+1].num){
c++;
} else {
vec[j].num = vec[i].num;
vec[j].count = c;
vec[j].ratio = ((double)c/s)*100;
j++;
c = 1;
}
}
count_sort(vec, l);
if (l >= 20){
cout << endl << "Showing the 10 most common numbers" << endl;
for (int i = 0; i < 10; i++){
cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl;
}
cout << endl << "Showing the 10 least common numbers" << endl;
for (int i = l-10; i < l; i++){
cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl;
}
} else {
for (int i = 0; i < l; i++){
cout << vec[i].num << "\t" << vec[i].count << "\t" << vec[i].ratio << "%" << endl;
}
}
}
После запуска этого кода я могу определить ожидаемое отклонение от rand ():
$ ./rnd_test
How many numbers to generate? 10000
Generate 10000 numbers ranging from 1 to? 50
Use rand or mt19937? [1/2] 1
Showing the 10 most common numbers
17 230 2.3%
32 227 2.27%
26 225 2.25%
25 222 2.22%
3 221 2.21%
10 220 2.2%
35 218 2.18%
5 217 2.17%
13 215 2.15%
12 213 2.13%
Showing the 10 least common numbers
40 187 1.87%
7 186 1.86%
39 185 1.85%
42 184 1.84%
43 184 1.84%
34 182 1.82%
21 175 1.75%
22 175 1.75%
18 173 1.73%
44 164 1.64%
Hoover я получаю почти тот же результат с mt19937
а также uniform_int_distribution
! Что здесь не так? Не должно быть равномерным, или тест бесполезен?
Нет, оно не должно быть идеально однородным. Таким образом, вышеизложенное не является доказательством какой-либо ошибки.
Они случайны и поэтому должны быть достаточно равномерными, но не совсем.
В частности, вы ожидаете, что каждое число будет встречаться примерно 10000/50 = 200 раз — примерно со стандартным отклонением sqrt (200), которое составляет около 14 — и для 50 чисел вы ожидаете около 2 стандартных отклонений разности — что + — / 28.
Смещение, вызванное использованием модуля для RAND_MAX, меньше, чем это; так что вам понадобится намного больше образцов, чтобы обнаружить смещение.
Вы должны использовать больше образцов для таких тестов случайных чисел. Я попробовал 50000 с вашим кодом, и результат:
Сколько чисел сгенерировать? 50000
Генерация 50000 номеров в диапазоне от 1 до? 50
Использовать rand или mt19937? [1/2] 2
Показаны 10 самых распространенных номеров
36 1054 2,108%
14 1051 2,102%
11 1048 2,096%
27 1045 2,09%
2 1044 2,088%
33 1035 2,07%
21 1034 2,068%
48 1034 2,068%
34 1030 2,06%
39 1030 2,06%
Показаны 10 наименее распространенных чисел
47 966 1,932%
16 961 1,922%
38 960 1,92%
28 959 1,918%
8 958 1,916%
10 958 1,916%
30 958 1,916%
32 958 1,916%
18 953 1,906%
23 953 1,906%
Насколько я могу судить по
http://www.cplusplus.com/reference/random/mersenne_twister_engine/ mt19937 будет страдать от того же смещения, что и rand ()
Смещение происходит из-за того, что rand () генерирует целое число без знака в некотором диапазоне [0-MAX_RAND], когда вы берете модуль, это делает меньшие числа немного более вероятными (если ваш делитель не является целочисленным делителем MAX_RAND)
Рассматривать:
Range [0-74]:
0 % 50 = 0
40 % 50 = 40
50 % 50 = 0
74 % 50 = 24
(numbers less than 25 occur twice)