Geschwindigkeitsproblem bei Zufallszahlen

Hundefutter

Hallo. Habe ein kleines Problem mit Zufallszahlen.
Schreibe gerade an einem kleinen Memory-Spiel. Wollte das ganze mit einem array machen. Also ich habe ein 6x6 Feld, also ein Array mit 36 Feldern. Diese Felder fülle ich mit Zufallzahlen, und zwar die ersten 18 mit den Werten von 1-18 und dann index 19-36 nochmals mit den Werten 1-18, weil es ja "Pärchen" geben soll. Wichtig dabei ist, dass bei den jeweiligen Zufallszahlen jede genau 2 mal vorkommt, d. h. bei jeder Füllung, sowohl von 1-18, als auch bei 19-36 jeder Werte genau ein mal vorkommt.
Das ganze habe ich mal folgendermaßen realisiert:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
  int zwischenspeicher;
  int cards[36];
  int mem_zaehler = 1;
  int i;
  bool gleich = false;

  for(mem_zaehler=1;mem_zaehler< 19;mem_zaehler++)
    {
        do
        {
           srand ( time(NULL) );
	       zwischenspeicher = (rand()%19);

           gleich = false;

           for(i=1;i<19;i++)
           {
              if (zwischenspeicher == cards[i])
              {
                 gleich = true;
              } //if
           } //for
        }while(gleich);

        cards[mem_zaehler]	 = zwischenspeicher;

        std::cout << cards[mem_zaehler] << std::endl;
    } //for

   std::cout << "----------------------------------" << std::endl;

   for(mem_zaehler=19;mem_zaehler < 37;mem_zaehler++)
   {
       do
        {
           srand ( time(NULL) );
	       zwischenspeicher = (rand()%19);

           gleich = false;

           for(i=18;i<37;i++)
           {
              if (zwischenspeicher == cards[i])
              {
                 gleich = true;
              } //if
           } //for
        }while(gleich);

        cards[mem_zaehler]	 = zwischenspeicher;

        std::cout << cards[mem_zaehler] << std::endl;
   } //for

  cin >> i;

  return 0;
};

Wenn ich das ganze jetzt mal ausführe, dann dauert das ganz schön lange, bis alle Zufallszahlen generiert sind. Naja, könnte das ganze ja in einem wunderschönen Ladebildschirm packen, wenns aber eben ginge, dann wärs schon, wenn ich das ganze noch etwas schneller kriegen könnte.

Weiß ja, wie sehr so ein Ladebildschirm nerven kann...

Also weiß jemand, wie ich das Programm noch etwas "tunen" kann?

MfG
Hundefutter

akari

Hallo

verteile die Werte erstmal der Reihe nach in dem Array, und dann benutzt du std::random_shuffle um das ganze zu verrütteln.

bis bald
akari

Hundefutter

Danke, werde es mal ausprobieren, wird bestimmt ne Geschwindigkeitsverbesserung bringen!

-----------------------------------
Edit:

Habe es jetzt mal mit random_shuffle gemacht und es ist auch um vieles schneller. Nur liefert das Programm jetzt immer die gleiche ausgabe, d. h. random_shuffle sortiert die werte immer gleich um, und es kommt auch irgendwie ein fehler rein, weil auf einmal eine Null in der Zahlenreihe kommt, welche erst nach random_shuffle drin ist.

Das Programm sieht nun folgendermaßen aus:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
  // Define a template class vector of int
  typedef vector<int, allocator<int> > IntVector ;

  IntVector cards(36);

  int mem_zaehler = 1;
  int i;

  for(i=1;i< 19;i++)
    {
        cards[i] = mem_zaehler;
        mem_zaehler++;
    }

  mem_zaehler = 1;

  for(i=19;i<37;i++)
   {
        cards[i] = mem_zaehler;
        mem_zaehler++;
   }

   std::random_shuffle(cards.begin(),cards.end());

   for(i=1;i<37;i++)
   {
       cout << cards[i] << endl;

       if(i==18) {cout << endl;}
   }

   cin >> i;

  return 0;
};

Kann man das ganze mit random_shuffle auch ncoh etwas zufälliger machen, weil die Karten ja nicht immer gleich gegeben werden sollen....

MfG
Hundefutter

Hundefutter

Habe jetzt etwas über Funktionsobjekte durchgelesen und bei random_shuffle noch einen zufallgenerator eingebaut, damit die Zahlen nicht bei jedem Programmstart die gleiche Reihenfolge haben.

Jetzt habe ich nur noch das Problem, dass nachdem ich random_shuffle aufgerufen habe, manche Zahlen mehrfach vorkommen, oder auch eine Null in der Zahlenreihe ist. Wo kommt die her, wenn nur geordnet wurde und vorher keine Null vorhanden war?

Hier ist das aktuelle Programm:

#include <iostream>
#include <algorithm>
#include <vector>
#include <time.h>

using namespace std;

class RandomNumber {
public:
    RandomNumber() {
        srand(time(0));
    }

    int operator() ( int n) {
        return (int)((double)n * rand()/(RAND_MAX+1.0));
    }
};

int main()
{
  typedef vector<int, allocator<int> > IntVector ;

  IntVector cards(36);

  int mem_zaehler = 1;
  int i;

  for(i=1;i< 19;i++)
    {
        cards[i] = mem_zaehler;
        mem_zaehler++;
    }

  mem_zaehler = 1;

  for(i=19;i<37;i++)
   {
        cards[i] = mem_zaehler;
        mem_zaehler++;
   }

   RandomNumber rnd;

   std::random_shuffle(cards.begin(),cards.end(),rnd);

   for(i=1;i<37;i++)
   {
       cout << cards[i] << endl;

       if(i==18) {cout << endl;}
   }

   cin >> i;

  return 0;
};

Hoffe, ihr könnt meinen Fehler finden..

MfG
Hundefutter

Hallo Hundefutter,

bei mir kommt ein Assert, wenn ich deinen Code kompiliere.

Desweiteren ist mir aufgefallen,

#include <iostream>
#include <algorithm>
#include <vector>
#include <time.h>

using namespace std;

class RandomNumber {
public:
    RandomNumber() {
        srand(time(0));
    }

    int operator() ( int n) {
        return (int)((double)n * rand()/(RAND_MAX+1.0));
    }
};

int main()
{
  typedef vector<int, allocator<int> > IntVector ;

  IntVector cards(36);

  int mem_zaehler = 1;
  int i;

  //---------------------------------
  //Sollte die nicht bei 0 loslaufen?
  //---------------------------------
  for(i=1;i< 19;i++)
    {
        cards[i] = mem_zaehler;
        mem_zaehler++;
    }

  mem_zaehler = 1;

  //--------------------------------
  //Nicht doch lieber i < 36?
  //--------------------------------
  for(i=19;i<37;i++)
   {
        cards[i] = mem_zaehler;
        mem_zaehler++;
   }

   RandomNumber rnd;

   std::random_shuffle(cards.begin(),cards.end(),rnd);

  //--------------------------------
  //Nicht doch lieber i < 36?
  //--------------------------------
   for(i=1;i<37;i++)
   {
       cout << cards[i] << endl;

       if(i==18) {cout << endl;}
   }

   cin >> i;

  return 0;
};

Zu den Nullen:
Bei mir wird der IntVector beim Erzeugen mit 0en vorbelegt
(benutze Visual C++ 2005)

Die doppelten Zahlen:
Naja, durch die zwei Vorschleifen kommen doch jeweils zweimal die gleichen Zahlen vor.

Gruss
Tobi

Hundefutter

Wenn ich den Vektor einfach nur Fülle und ausgeben lasse, also das random_shuffle mal wegklammer, dann gibt er mir 2 mal jeweils für 1-18 und für 19-36 die Zahlen von 1-18 aus. Also das Füllen funktioniert einwandfrei.

Daher würde ich auch sagen, dass die Bedingungen der For-schleifen auch richig gewählt sind, da diese ja für das Füllen verantwortlich sind und dieses auch perfekt funktioniert.

Nur wenn ich dann das random_shuffle wieder reinnehme, dann tauchen in den 2 Zahlenreihen (1-18 u. 19-36) manche Zahlen doppelt auf und es kommen auch Nullen vor, wobei doch eigentlich in Jeder Zahlenreihe die Zahlen von 1-18 durcheinandergewürfelt vorkommen müssten, keine doppelt und auch keine Nullen.

Denke also, dass es am random_shuffle liegt, da nach dem Füllen ja noch alles richtig ist.

MfG
Hundefutter

niemand

std::vector beginnt bei 0 nicht bei 1. Daher sind Deine Grenzen falsch.
std::randon_shuffle nutzt daher die Werte von cards[0]...cards[35]. Du schreibst aber nach cards[1]...cards[36]
Daher Dein Problem.
Wenn Du natürlich nach cards[1]...cards[36] schreibst und das dann wieder ausgibst, ist die Wahrscheinlichkeit, dass das richtige rauskommt sehr hoch. Wenn Du Pech hast, gibt es aber einen Absturz, da cards[36] nicht mehr gültig ist. Oder wie schon berichtet eine Assertion, wenn die STL prüft, ob die Zugriffe gültig sind.

random_shuffle würfelt Deine 36 Zahlen insgesamt durcheinander, d.h. in den ersten 18 Werten können Zahlen doppelt vorkommen.
Ich würde erwarten, dass eine Zahl != 0 nur einmal vorkommt, dafür einmal die 0 und alle anderen Zahlen zweimal.

BTW, die RandomNumber Klasse ist unnötig. Das macht random_shuffle bis auf das srand selbst (das fehlte Dir im ersten Ansatz).

Ausserdem sollte vector<int> reichen, die Angabe des allocators sollte nicht notwendig sein.

Braunstein

Das hier sollte es auch tun

#include <iostream>
#include <algorithm>
#include <ctime> // statt time.h
#include <vector>
#include <cstdlib> // statt stdlib.h (stdio ist unnötig)

using namespace std;

int main()
{
    vector<int> cards(36);
// mem_zaehler ist unnötig, i sollte in der Schleife deklariert werden
    for(int i=0;i< 18;i++) // eine Schleife reicht
    {
        cards[i] = i+1;
        cards[i+18] = i+1;
    }
    srand(time(0)); // Initialisierung Zufallsgenerator nur einmal
// Beide Teile separat mischen (evtl. besser zwei Vektoren verwenden)
    std::random_shuffle(cards.begin(),cards.begin()+17);
    std::random_shuffle(cards.begin()+18,cards.end());
    for( int i=0; i<36; ++i)
    {
        cout << cards[i] << "\n";
        if( i== 17 ) cout << "\n";
    }

}

Hundefutter

ok, jetzt funktioniert es!

Vielen Dank für die ganzen Hilfen.

MfG
Hundefutter

Hundefutter

Hätte jetzt nur noch ein weiteres kleines Problem:

Bin jetzt mal dabei, das ganze in mein eigentliches Projekt einzubauen. Jetzt wollte ich den Vector in einer Klasse als Protected deklarieren, damit er nur durch Methoden der Klasse verändert werden kann:

#include <vector> 

class Cmemory
{

//[...]

protected:
	std::vector<int> cards(36);
};

Jetzt gibt er mir jedoch folgende Fehlermeldung beim Kompilieren aus:

error C2059: Syntaxfehler : 'constant'
Fehler beim Ausführen von cl.exe.

Es bezieht sich auf die Zeile, in der der Vector deklariert wird. Was ist jetzt daran falsch?

MfG
Hundefutter

akari

Hallo

der von dir gezeigte Ausschnitt ist soweit in Ordnung, der eigentliche Fehler wird wo anders ausgelöst.
Insbesondere

error C2059: Syntaxfehler : 'constant'

deutet darauf hin. Hast du irgendwo constant stehen? Soll doch sicher const heißen

bis bald
akari

Hundefutter

Das wundert mich ja, habe nirgendswo ein const drin....

Hier ist die gesammte Datei:

#include <vector> 

class Cmemory
{

public:

	Cmemory();
    virtual ~Cmemory();

	void init_memory(void);

	void change_card(int i);

	void clean_up(void);

protected:

	std::vector<int> cards(36);
};

Habe keine ahnung, wo der da ein const sieht..

MfG
Hundefutter

MFK

Hundefutter schrieb:

protected:
	std::vector<int> cards(36);

Initialisieren kannst du diesen vector erst im Konstruktor.

Hundefutter

Alles klar, danke!