シャッフルアルゴリズムの2つの実装の比較

方法1: ランダム生成

まず、非常に一般的な方法であるランダム生成法（私が名付けました）を紹介します。私はこの方法を使用して、マインスイーパゲームで地雷の位置をランダムに分散させました（考え方は同じです）。この方法の重要なポイントは、最初から指定された領域に 1 つずつ数字をランダムに生成することです。新しく生成された乱数が以前に生成された場合、その数字は保存されません。新しく生成された乱数が以前に生成されていない場合、その数字は保存されます。生成された数字の数が必要な数に達するまで保存されます。

実装コードは次のとおりです。

 size_tシャッフル( char s[], int n)
 {
 size_t t=0; //ループ回数を計算する 
整数c = 0;
 (c<n)の場合
    {
        t++;
 int num = rand()%n;
 (memchr(s,num,c) == NULL)の場合
        {
            s[c++] = static_cast < char >(num);
        }
    }
 tを返します。
 } 
 
 
 void printCards( char s[], int n)
 {
 ( int i=0; i<n; i++)の場合
    {
        cout << static_cast < int >(s[i]) << " " ;
    }
    cout << 終了;
 }

コードでは、memchr 関数を使用しています (時間計算量は O(n) かもしれませんが、証拠は見つかりませんでした)。たとえ O(1) であっても、乱数を生成するためにループする回数は固定ではありません (生成する必要がある数以上)。

方法2: ポジション交換法

この方法は、昨日テンセントの筆記試験を受けているときに思いつきました。今日学校に戻って寮で試してみました。基本的な考え方は、まず分散した数字の列を初期化し、次にランダムな位置を生成して、各位置と順番に交換します。生成されたランダムな位置がそれ自身でない場合は、交換操作を実行します。

実装コード:

 void swap( int & a, int & b)
 {
    ;
    ;
    ;
 } 
 
 size_t shuffle2( int s[], int n)
 {
 size_t t=0; //ループ回数を計算する 
 ( int i=0; i<n; i++)の場合
    {
        t++;
        s[i] = i;
    }
 ( int i=0; i<n; i++)の場合
    {
        t++;
 int num = rand()%n;
 （数値!= i）の場合
        {
            swap(s[num],s[i]);
        }
    }
 tを返します。
 } 
 
 void printCards2( int s[], int n)
 {
 ( int i=0; i<n; i++)の場合
    {
        cout << s[i] << " " ;
    }
    cout << 終了;
 }

比較: 方法 2 は、スワップ位置の最大数が制限されている (生成される乱数の数が固定されている) ため、新しく生成された数が生成された数の中にあるかどうかを調べる時間が節約されるため、時間の点で方法 1 よりもはるかに高速です。方法 1 では、新たに生成された数字が既に生成された数字の中にある場合、新しい乱数を生成する必要があるため、乱数として生成される数字の数は固定ではありません (最小値があります)。

テストコード:

結果：

2 番目の方法が優れているかどうかはまだわかりません。これは私自身のアイデアであり、検証が完全ではないためです。他の欠点 (弱いランダム性など) がある可能性があります。他の本では見たことがありません。ネットユーザーがどこかで見たことがある場合は、教えてください。方法 1 は、中国語版の「The Essentials of C and C++ Code」P97 で見つかりました。

後続の補足:

chncwang さんの返信ありがとうございます。方法 2 は完全にランダムではありません。完全にランダムな変更は次のとおりです。

 size_t shuffle22( int s[], int n)
 {
 size_t t=0; //ループ回数を計算する 
 ( int i=0; i<n; i++)の場合
    {
        t++;
        s[i] = i;
    }
 ( int i=n-1; i>0; --i)の場合
    {
        t++;
整数= rand()%(i+1);
 （数値!= i）の場合
        {
            swap(s[num],s[i]);
        }
    }
 tを返します。
 }

なぜなら、「最初の移動後、最初の数字がまだ最初の位置にある確率は 1/n であり、その後の移動ではこの確率が下がるだけです。したがって、このアルゴリズムは完全にランダムではありません。」変更されたアルゴリズムは、実際には C++ の STL<algorithm> ライブラリの random_shuffle() 関数の実装方法です。 i が変化するたびに乱数の範囲が変更されるため、前の位置の数字が元の数字のままである確率は低下しません (つまり、後続のスワップ操作は、すでにスワップされた位置に影響を与えません)。

実装は標準ライブラリ <algorithm> の random_shuffle() 関数を使用すると簡単です。コードは次のとおりです。

 intメイン()
 {
    ベクトル< int > s_stl;
 ( int i=0; i<CARDS_COUNT; ++i)の場合、 s_stl.push_back(i);
    ランダムシャッフル(s_stl.begin(),s_stl.end());
    cout << "C++ アルゴリズム ライブラリの使用:" ;
 (ベクトル< int >::iterator it=s_stl.begin(); it!=s_stl.end(); ++it)
        cout << " " << *it;
 0を返します。
 }