1

rand() mod n は偏った結果になると言われたので、それを確認するためにこのコードを作成しようとしました。s1 から 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 私はmt19937and とほとんど同じ結果を得ていuniform_int_distributionます! ここで何が問題なのですか？均一であってはいけませんか、それともテストは役に立ちませんか?

4

3 に答える 3

0

このような乱数テストには、より多くのサンプルを使用する必要があります。あなたのコードで 50000 を試してみましたが、結果は次のとおりです。

生成する数はいくつですか? 50000

1 から? までの範囲の 50000 の数字を生成します。50

ランドまたは 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 に答える