C++

Forum

 
Slow run speed for code, randomizing array

geniusberry (83)
Hello!

I'm trying to finish an exercise where the goal is to emulate a deck of cards. I've created a class card, here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
class card {
	
	public:
	
		//Constructor/Destructor
		card(): itsSuite(0), itsValue(0) {}
		card(int nValue, int nSuite): itsSuite(nSuite), itsValue(nValue) {}
		~card() {}
	
		//Accessor Methods
		int getSuite() const {return itsSuite;}
		int getValue() const {return itsValue;}
		card getCard() const {return *this;}
		void getName() const;
		
		void setSuite(int nSuite) {itsSuite = nSuite;}
		void setValue(int nValue) {itsValue = nValue;}
	
	private:
		
		//Member Variables
		int itsSuite;
		int itsValue;
};


and a class deck, which has an array of 52 cards:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
class deck {
	
	public:
		
		//Constructor/Destrutor
		deck();
		~deck() {}
		
		//Accessor Methods
		void displayDeck() const;
		void drawCard() const;
		
		void orderDeck();
		void shuffleDeck();
		
	private:
		
		//Member Functions
		int randomNum(int max, int min) const;
		
		//Member Variables
		card pack[52];
};


I'm having trouble with the shuffleDeck() function. My problem is that it compiles, builds, and checks out, but when I try and run my full program, it stalls, and won't finish running no matter how long I leave it be. I've rewritten it twice, and have no idea what the problem is. Here's the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
void deck::shuffleDeck() {
	
	for(int i = 0; i < 52; i++) {
		
		pack[i].setSuite(0);
		pack[i].setValue(0);
	}
	
	bool shuffled = false;
	
	int packCard = 0;
	int cardRank = 1;
	int cardSuite = 1;
		
	while(shuffled != true) {
		
		packCard = randomNum(51, 0);
		
		if(pack[packCard].getValue() != 0) {
			
			continue;
		}
		else {
			
			pack[packCard].setSuite(cardSuite);
			pack[packCard].setValue(cardRank);
			
			cardSuite++;
				
			if(cardSuite == 5) {
				
				cardSuite = 1;
				cardRank++;
			}
			if(cardRank == 14) {
					
				cardRank = 0;
				cardSuite = 0;
				packCard = 0;
				shuffled = true;
				
				continue;
			}
		}
	}
}


Any suggestions?
JLBorges (13770)
1
2
3
4
5
 
void deck::shuffleDeck() {
    
     // http://www.cplusplus.com/reference/algorithm/random_shuffle/
     std::random_shuffle( pack, pack+52 ) ; // #include <algorithm>
}
geniusberry (83)
EDIT1:

Never mind, found it. cardRank never reaches 14! Thanks for your help JLBorges! After comparing output from random shuffle and my function, I've decided to use random shuffle, since it's more random.

Thanks JLBorges! My code works now. But I was wondering if you could shed light on how come my own code doesn't work? Thanks for your help so far!
Last edited on
Peter87 (11179)
Do you call srand inside randomNum?

If you seed the random number generator with the same seed you will get the same sequence of random numbers from rand(). std::time(0) returns the time in seconds so if you do std::srand(std::time()) each time randomNum is called you will get the same number for all calls within the same second. That would explain why your code takes so long to finish. Even in the best case you would have to wait at least 52 seconds.
geniusberry (83)
Peter87, I called srand inside deck's constructor since it's the only class with a random number generator. But, thanks for your suggestion!
Last edited on
Peter87 (11179)
Ok, but there could still be something wrong with the randomNum. Make sure it returns all values from min to max.
JLBorges (13770)
I think that this is what you intended to do:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
void deck::shuffleDeck() {
	
	for(int i = 0; i < 52; i++) {
		
		pack[i].setSuite(0);
		pack[i].setValue(0);
	}
	
	int packCard = 0;
	int cardRank = 1;
	int cardSuite = 1;
	
	while( cardSuite < 5 ) {
		
		packCard = randomNum(51, 0);
		
		if(pack[packCard].getValue() == 0) {

			pack[packCard].setSuite(cardSuite);
			pack[packCard].setValue(cardRank);
			
			++cardRank ;

			if(cardRank == 14) {
					
				cardRank = 1;
				++ cardSuite ;
		}
	}
}


This is very inefficient; there is no upper bound on the number of times the loop would be executed.

How many times would packCard = randomNum(51, 0); be evaluated before the very last card can be placed into the only free slot?
geniusberry (83)
Peter87, I've checked randomNum, and everything is fine. I've made it so it follows the example given on this site for generating random numbers with the c libraries. JLBorges, this is the working implementation of the shuffleDeck function before I changed it in favor of the random_shuffle function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
void deck::shuffleDeck() {
	
	for(int i = 0; i < 52; i++) {
		
		pack[i].setSuite(0);
		pack[i].setValue(0);
	}
	
	bool shuffled = false;
	
	int packCard = 0;
	int cardRank = 1;
	int cardSuite = 1;
	int cardsShuffled = 1;
	
	while(shuffled != true) {
		
		packCard = randomNum(51, 0);
		
		if(pack[packCard].getValue() != 0) {

			continue;
		}
		else {

			pack[packCard].setSuite(cardSuite);
			pack[packCard].setValue(cardRank);
			
			cardSuite++;
			cardsShuffled++;
				
			if(cardSuite == 5) {

				cardSuite = 1;
				cardRank++;
			}
			if(cardsShuffled == 51) {

				cardRank = 0;
				cardSuite = 0;
				packCard = 0;
				shuffled = true;
				
				continue;
			}
		}
	}
}


How would you recommend making it more efficient?
JLBorges (13770)
> How would you recommend making it more efficient?

Fisher–Yates shuffle O(N) time, O(1) space http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

The typical implementation of std::random_shuffle()
geniusberry (83)
thanks!
Topic archived. No new replies allowed.