3

特定の範囲（0〜5,000,000）が与えられており、この範囲から2,500,000個の一意の乱数を生成する必要があるとします。これを行うための効率的な方法は何ですか？真の乱数を取得するのは難しいことを理解しています。

新しい乱数を生成できるように、番号が存在するかどうかを確認してみました。ただし、計算には数時間かかります。これを行うためのより良い方法はありますか？

この背後にある理由は、私がサイズ5,000,000のベクトルを持っているからです。ベクトルを正確に半分に縮小したいと思います。つまり、ベクトルから要素のランダムな50％を削除します。

    #include <iostream>
    #include <vector>
    #include <stdlib.h>
    #include <algorithm>
    using namespace std;

    #define NUMBER 2500000
    #define RAND_START 0
    #define RAND_END 5000000

    unsigned int generate_random_number(int min, int max)
    {
        return min + (rand() % (unsigned int)(max - min + 1));
    }

    int main(int argc, char* argv[])
    {
        unsigned int count = 0, random_number;
        vector<unsigned int> rand_vector;
        do 
        {   
            count++;
            random_number = generate_random_number(RAND_START,RAND_END);
// Tried to manually add a different number each time. But still not a considerable improvement in performance. 
            if (std::find(rand_vector.begin(), rand_vector.end(), random_number) != rand_vector.end())
            {
                if(random_number > count)
                    random_number = random_number - count;
                else
                    random_number = random_number + count;          
            }
            rand_vector.push_back(random_number);
            sort(rand_vector.begin(), rand_vector.end());
            rand_vector.erase(unique (rand_vector.begin(), rand_vector.end()), rand_vector.end());
        }while (rand_vector.size() != NUMBER);


        for (unsigned int i =0; i < rand_vector.size(); i++)
        {
            cout<<rand_vector.at(i)<<", ";
        }
        cout<<endl;
        return 0;
    }

私がこれを行うことができるより良いアプローチはありますか？

4

4 に答える 4

5

どういうわけか乱数を事前に生成する必要があるという考えに固執しているようです。なんで？究極のタスクは、ベクトルからいくつかのランダムな要素を削除することだとあなたは言いました。その特定の問題については、事前にすべてのランダムインデックスを事前に生成する必要はありません。これらのインデックスは「オンザフライ」で簡単に生成できます。

この特定のタスク（つまり、ベクター内の要素の50％を削除する）では、Knuthアルゴリズムが非常にうまく機能します（https://stackoverflow.com/a/1608585/187690を参照）。

0から元のベクトルのすべての要素を繰り返し処理し、確率で5番目の要素N-1を削除するランダムな決定を行います。ここで、はまだ削除する必要のある要素の数であり、はベクトルの残りの部分の長さです。 。このアプローチは、1回のパスでそれを実行し（スマートに実装されている場合）、追加のメモリや試行錯誤の反復を必要としません。それは単にあなたがしたいことを正確に実行します：等しい確率でベクトル要素の50％を破壊します。iN_to_delete / N_to_iterateN_to_deleteN_to_iterate

MKnuthアルゴリズムは、ランダム値の数（ ）が範囲の長さ（）に比べてかなり大きい場合に最適に機能します。Nこれは、その複雑さがに関連付けられているためNです。Mの50％であるあなたの場合、NKnuthアルゴリズムを使用することはかなり良い考えです。

ランダム値の数が範囲（）よりもはるかに少ない場合、その複雑さはによってではなくによってM << N定義されるため、Bob Floydアルゴリズム（上記のリンクを参照）の方が理にかなっています。追加のメモリ（セット）が必要ですが、乱数を生成するときに試行錯誤を繰り返すことはありません。MN

ただし、あなたの場合、ベクトルから要素を削除しようとしています。ベクトル要素の削除は、によって支配されNます。これは、とにかくボブフロイドアルゴリズムの利点を打ち負かします。

于 2012-08-23T18:15:56.920 に答える
2

一意の番号があるかどうかを手動でチェックする代わりに、たとえばstd::unordered_setを使用して、セットのサイズが必要な番号になるまで番号を生成し続けることができます。

于 2012-08-23T17:48:34.740 に答える
2

それをコーディングする最も簡単な方法：

std::random_shuffle(vectoshrink.begin(), vectoshrink.end());
vectoshrink.resize(vectoshrink.size() / 2);

使用中の要素の順序を維持したい場合は、vectoshrinkAndreyTの回答。

本当に事前にインデックスを選択したい場合：

std::vector<size_t> vec(vectoshrink.size());
// iota is C++11, but easy to do yourself
std::iota(vec.begin(), vec.end(), size_t(0));
std::random_shuffle(vec.begin(), vec.end());
vec.resize(vec.size() / 2);
// optionally
std::sort(vec.begin(), vec.end());

これで、これらのインデックスを使用して、インデックスの要素をvec新しいベクトルにコピーすることで元のベクトルを縮小し、結果を元のベクトルと交換できます。

どちらの場合も、random_shuffleベクトル全体をシャッフルするため、厳密に必要な以上のことを行いますが、実際には、その半分だけを「シャッフル」する必要があります。ただし、Fisher-Yatesシャッフルがどのように機能するかを読むと、自分でコーディングした場合に必要な変更は、完全なシャッフルの半分の手順を実行するだけであることが簡単にわかります。ただし、C++には標準がありませんpartial_random_shuffle。

最後に、デフォルトのランダムソースはあまり良くない可能性があることに注意してください。そのため、の3つの引数バージョンを使用することをお勧めしますrandom_shuffle。関数はとgenerate_random_numberの特定の値に対してかなり偏っているので、乱数生成の一般的な理論についてもう少し調べたいと思うかもしれません。minmax

于 2012-08-23T18:15:21.313 に答える
0

1番目の数値<5M、2番目の数値<（5M-1）などを生成します。要素を削除するたびに、要素が1つ少なくなり、同じ数値であるかどうかは関係ありません。;-)これは、一意の数についての質問には答えませんが、ベクトルを半分にすることについての質問には答えません。

また、必要以上の数を生成する必要はありません。

于 2012-08-23T17:44:30.127 に答える