1

有人告诉我 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%

胡佛我得到了几乎相同的结果mt19937and uniform_int_distribution！这里有什么问题？不应该统一，还是测试没用？

4

3 回答 3

1

不，它不应该完全一致。因此，上述不是任何错误的证据。

它们是随机的，因此应该是相当一致的，但不完全一致。

特别是，您会期望每个数字出现大约 10000/50=200 次 - 大致标准差为 sqrt(200)，大约为 14 - 对于 50 个数字，您会期望大约 2 个标准差 - 即 +- /28。

RAND_MAX 使用模数引起的偏差小于此值；所以你需要更多的样本来检测偏差。

于 2016-11-08T08:34:22.557 回答
0

您必须使用更多样本进行此类随机数测试。我用你的代码尝试了 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%

于 2016-11-08T10:29:43.483 回答
-1

据我所知， 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)
于 2016-11-08T08:35:23.843 回答