Что я делаю неправильно с этими случайными числами?

Question

Мне сказали, что 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! Что здесь не так? Не должно быть однородным, или тест бесполезен?

Answer 1

Нет, он не должен быть абсолютно однородным. Таким образом, вышесказанное не является доказательством каких-либо ошибок.

Они случайны и поэтому должны быть довольно однородными, но не совсем точно.

В частности, вы ожидаете, что каждое число будет происходить примерно в 10000/50 = 200 раз - примерно со стандартным отклонением sqrt (200), которое составляет около 14 - и для 50 номеров вы ожидаете примерно 2 стандартных отклонения разницы - которая равна + -/28.

Уклон, вызванный использованием модуля для RAND_MAX, меньше этого; так что вам понадобится намного больше образцов, чтобы обнаружить смещение.

Answer 2

Насколько я могу сказать от 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) 

Answer 3

Вы должны использовать большее количество образцов для испытаний таких случайных чисел. Я попробовал 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%