配列の要素をシャッフルする：スタックベースのバッファオーバーランエラー

Question

私の与えられたコードは、元のプログラムの問題部分です。 myArrayの2つの要素をランダムにN回とT回のループで交換します。プログラムは想定していることをしますが、 "return 0"を押すと "program.exeが動作を停止しました"というエラーメッセージが表示されます。デバッグ出力には、

Stack cookie instrumentation code detected a stack-based buffer overrun 

が表示されます。なぜジョブが完了した後にプログラムがエラーを表示していますか？ これを修正するにはどうすればよいですか？

#include <iostream> 
#include <ctime>  
#include <cstdlib> 

using namespace std; 

int main() 
{ 
    const int N = 10000; 
    const int T = 100; 

    srand((unsigned)time(0)); 

    bool myArray[N] ; 
    bool temp = true; 
    int save1 = 0; 
    int save2 = 0; 

    //initializing myArray 
    for (int index = 0; index < N/2; index++) { 
     myArray[index] = false; 
    } 
    for (int index = N/2; index < N; index++) { 
     myArray[index] = true; 
    } 

    for (int index = 0; index < T; index++) { 

     for (int index1 = 0; index1 < N; index1++) {  
      save1 = int(N*rand()/RAND_MAX); 
      save2 = int(N*rand()/RAND_MAX); 


      temp = myArray[save1]; 
      myArray[save1] = myArray[save2] ; 
      myArray[save2] = temp; 
     } 
    } 

    cout<<" Press any key to exit..."; 
    cin.get(); 

    return 0; 
} 

EDIT： Iは0から（N-1）へのランダムな整数を生成しなければなりませんでした。 myArrayのN番目の場所を呼び出すと問題が発生していました。

しかし、以下のいずれの方法も、ランダムな整数を均一に生成しません。

save1 = int((N-1)*rand()/RAND_MAX); 

も

save1 = int(N*rand()/(RAND_MAX+1)); 

素敵videoは、この方法の問題です。 MicとBob__が指摘しているように、(N-1)*rand()によって引き起こされたオーバーランの問題もあります。

このモジュロ方法は、広範囲のランダム整数に対しても非常に非効率的です（詳細はarticleを参照）。だから、均一な乱数を生成する私の最高のチャンスは、次の方法です（記事から借りています）。

while(true) 
{ 
    int value = rand(); 
    if (value < RAND_MAX - RAND_MAX % range) 
    return value % range; 
} 

また、配列の要素をシャッフルするために、最適なパフォーマンスのためrandom_shuffle機能やFisher–Yates shuffleを使用するのが最適です。修正する

Answer 1

のは、（編集後qustionの）この行を考えてみましょう：

save1は、タイプ intの変数です Nは、同じタイプのconstのであると rand()は、範囲[0に intを返し

save1 = int((N-1)*rand()/RAND_MAX); 

RAND_MAX]。

C++では、この式は左から右に評価されるため、最初に乗算、次に除算が行われます。 rand()がINT_MAX /（N - 1）より大きい値を戻す場合、この操作はオーバーフローし、未定義動作が発生します。ほとんどの実装では、積分値の2の補数表現のため、結果は負の値になります。その後

RAND_MAXは結果が0

ある任意の値についてのx、このような-RAND_MAX < X <ことをあなたはhereそのあなたのプログラム（私だけを見ることができるように、RAND_MAXによって整数分割が行われ、私のポイントを証明するための行を追加しました）コンパイルして実行します。 indecesがゼロでない回数を確認してください。 0とN（除外）の間の乱数を生成するために、rand()を使用して

Cでの一般的な方法は、次のとおりです。

int number = rand() % N; 

は、あなたができると、Fisher Yatesのように、また、配列をシャッフルするためのより良いアルゴリズムを考えてみましょう

#include <iostream> 
#include <random> 
#include <array> 
#include <algorithm> 

int main() 
{ 
    std::random_device rd; 
    std::mt19937 g(rd()); 

    std::array<bool, 10000> my_array; 
    auto middle = my_array.begin() + my_array.size()/2; 
    std::fill(my_array.begin(), middle, false); 
    std::fill(middle, my_array.end(), true); 

    std::shuffle(my_array.begin(), my_array.end(), g); 
} 

0：あなたはこれらのアルゴリズムを書き換えるの標準ライブラリを代わりに使うべき++ Cで

void my_c_shuffle(bool *arr, size_t n) 
{ 
    while (n > 1) 
    { 
     size_t choice = rand() % n; 
     --n; 
     bool temp = arr[n]; 
     arr[n] = arr[choice]; 
     arr[choice] = temp; 
    } 
} 

：としてCで実装

Answer 2

少なくとも一つのこと：

ランドは（）ので、あなたはあなたが交換する必要があります

N*rand()/(1+RAND_MAX) 

Answer 3

によって

N*rand()/RAND_MAX 

を交換する必要があり、0からRAND_MAXまでの間のランダムな整数を返します。 Nと(N-1)。おそらくそれはあなたがしたいことです。あなたの意図はSAVE1 & SAVE2を計算する文で `index1' にを使用する場合

save1 = int((N-1)*rand()/RAND_MAX); 
    save2 = int((N-1)*rand()/RAND_MAX); 

ただ不思議。それも問題を解決します。