Shuffle-Elemente von Array: stack-basierter Pufferüberlauffehler

Question

Mein angegebener Code ist der problematische Teil des ursprünglichen Programms. Er tauscht zwei Elemente von myArray zufällig N mal und in T Anzahl von Schleifen. Das Programm tut, was es soll, aber nachdem er "return 0" gedrückt hat, zeigt es die Fehler-Massage von "program.exe hat aufgehört zu arbeiten". Die Debug-Ausgabe zeigt

Warum zeigt das Programm Fehler, nachdem seine Arbeit erledigt ist? Wie kann ich das beheben?

#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: Ich hatte von 0 bis (N-1) ganze Zufallszahl zu erzeugen. Durch den Aufruf des N-ten Standorts in myArray wurde das Problem verursacht.

Aber keine der folgenden Methoden generiert zufällige Integer einheitlich.

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

noch

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

Es gibt einen schönen video auf das Problem dieser Methode. Es gibt auch das Problem des Überlaufs, verursacht durch (N-1)*rand(), wie Mic und Bob__ darauf hingewiesen haben.

Diese Modulo-Methode ist auch sehr ineffizient für große Bereich der zufälligen Ganzzahl (überprüfen Sie diese article für Details). Meine beste Chance, einheitliche Zufallszahlen zu erzeugen, ist die folgende Methode (entlehnt aus dem Artikel).

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

Auch Anordnungselemente für Shuffling ist es am besten random_shuffle Funktion oder Fisher–Yates shuffle für eine optimale Leistung zu verwenden.

Answer 1

Lassen Sie sich diese Linie betrachtet (die bearbeiteten qustion):

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

Wo save1 eine Variable vom Typ ist int, N ist ein const des gleichen Typs und rand() ein int im Bereich zurück [0, RAND_MAX].

In C++ wird dieser Ausdruck von links nach rechts ausgewertet, also zuerst die Multiplikation, dann die Division. Wenn rand() einen Wert größer als INT_MAX/(N - 1) zurückgibt, läuft diese Operation über und verursacht Undefined Behavior.In den meisten Implementierungen kann das Ergebnis aufgrund der Zweierkomplementdarstellung von ganzzahligen Werten ein negativer Wert sein.

Danach wird eine integer Division durch RAND_MAX durchgeführt wird, so dass für jeden Wert x, so dass -RAND_MAX < x < RAND_MAX das Ergebnis 0.

Sie here sehen können, dass Ihr Programm (ich nur fügte eine Zeile hinzu, um meinen Punkt zu beweisen) kompiliert und führt aus. Bitte beachten Sie, wie oft die Indezes nicht Null sind.

Eine übliche Art und Weise in C, unter Verwendung von rand(), eine Zufallszahl zwischen 0 und N (ausgenommen) ist, zu erzeugen:

int number = rand() % N; 

Betrachten wir auch einen besseren Algorithmus ein Array zu mischen, wie Fisher Yates, könnte man Implementierung in C als:

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; 
    } 
} 

in C++ Sie die Standardbibliothek statt Neuschreiben diese Algorithmen verwenden sollten:

#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); 
} 

Answer 2

Mindestens eine Sache zu beheben:

rand() liefert eine Zufallszahl zwischen 0 und RAND_MAX inklusive, so müssen Sie ersetzen

N*rand()/RAND_MAX 

von

N*rand()/(1+RAND_MAX) 

Answer 3

Sie sollten ersetzen N mit (N-1). Wahrscheinlich wollen Sie das tun.

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

nur fragen, ob Ihre Absicht ist es `Index1' in Aussagen zu verwenden SAVE1 & SPEICHERN2 zu berechnen. Das wird das Problem auch beheben.