Drawing cards from a deck
-
Hi, I'd like to run some simulations on a deck of 52 cards, but I don't know how to make it fast. Say, I want to draw 5 random cards from a deck. The most straightforward way to do this would be to create a List, List, List, etc. (whatever way the cards are represented), then draw a random number between 0-51, remove the card from the list, draw a number between 0-50, remove the card from the list, rinse & repeat until 5 cards are drawn. The problem is that adding/removing stuff is a costly operation. Can you see a fast way to randomly draw cards from a deck?
-
Hi, I'd like to run some simulations on a deck of 52 cards, but I don't know how to make it fast. Say, I want to draw 5 random cards from a deck. The most straightforward way to do this would be to create a List, List, List, etc. (whatever way the cards are represented), then draw a random number between 0-51, remove the card from the list, draw a number between 0-50, remove the card from the list, rinse & repeat until 5 cards are drawn. The problem is that adding/removing stuff is a costly operation. Can you see a fast way to randomly draw cards from a deck?
I don't think it is such slow. You may use an array (of card index or references) and that swap the random selected element with the last one. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
Hi, I'd like to run some simulations on a deck of 52 cards, but I don't know how to make it fast. Say, I want to draw 5 random cards from a deck. The most straightforward way to do this would be to create a List, List, List, etc. (whatever way the cards are represented), then draw a random number between 0-51, remove the card from the list, draw a number between 0-50, remove the card from the list, rinse & repeat until 5 cards are drawn. The problem is that adding/removing stuff is a costly operation. Can you see a fast way to randomly draw cards from a deck?
Ok, I just quickly implemented what you describe, populating a List with the numbers 0-51, and removing a random entry from the list 5 times. I did this in a big loop that repeats the operation a million times, and it took roughly a second. So unless you're planning on implementing your own List, rather than using the Generics one, I wouldn't worry about speed
Help me! I'm turning into a grapefruit! Buzzwords!
-
I don't think it is such slow. You may use an array (of card index or references) and that swap the random selected element with the last one. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles]That's a really nice idea. I'm going to try that.
-
Ok, I just quickly implemented what you describe, populating a List with the numbers 0-51, and removing a random entry from the list 5 times. I did this in a big loop that repeats the operation a million times, and it took roughly a second. So unless you're planning on implementing your own List, rather than using the Generics one, I wouldn't worry about speed
Help me! I'm turning into a grapefruit! Buzzwords!
Well 1 million is what I need in fact ;o Thank you for trying. It took 1 second even when you have to repopulate the list at every pass? I need to see this by myself!
-
Ok, I just quickly implemented what you describe, populating a List with the numbers 0-51, and removing a random entry from the list 5 times. I did this in a big loop that repeats the operation a million times, and it took roughly a second. So unless you're planning on implementing your own List, rather than using the Generics one, I wouldn't worry about speed
Help me! I'm turning into a grapefruit! Buzzwords!
This took 2.7s on my machine. What's your code?
List deck = new List();
uint[] cards = new uint[52];Random rnd = new Random();
DateTime st = DateTime.Now;
for (int i = 0; i < 1000000; i++)
{
deck.Clear();
deck.AddRange(cards);//remove 5 cards deck.RemoveAt(rnd.Next(0, deck.Count - 1)); deck.RemoveAt(rnd.Next(0, deck.Count - 1)); deck.RemoveAt(rnd.Next(0, deck.Count - 1)); deck.RemoveAt(rnd.Next(0, deck.Count - 1)); deck.RemoveAt(rnd.Next(0, deck.Count - 1));}
DateTime ed = DateTime.Now; -
This took 2.7s on my machine. What's your code?
List deck = new List();
uint[] cards = new uint[52];Random rnd = new Random();
DateTime st = DateTime.Now;
for (int i = 0; i < 1000000; i++)
{
deck.Clear();
deck.AddRange(cards);//remove 5 cards deck.RemoveAt(rnd.Next(0, deck.Count - 1)); deck.RemoveAt(rnd.Next(0, deck.Count - 1)); deck.RemoveAt(rnd.Next(0, deck.Count - 1)); deck.RemoveAt(rnd.Next(0, deck.Count - 1)); deck.RemoveAt(rnd.Next(0, deck.Count - 1));}
DateTime ed = DateTime.Now;Random rnd = new Random(); List myDeck = new List(); DateTime start = DateTime.Now; for (int loop = 0; loop < 1000000; ++loop) { myDeck.Clear(); for (int i = 0; i < 52; ++i) { myDeck.Add(i); } List hand = new List(); // Randomly remove a random card until the deck is empty for( int draw = 0; draw<5; ++draw ) { int cardIndex = rnd.Next(myDeck.Count); int card = myDeck[cardIndex]; myDeck.RemoveAt(cardIndex); hand.Add(card); } } DateTime end = DateTime.Now; [edit] - turned off the html tags - which kills the formatting, but at least you can see the generics! Help me! I'm turning into a grapefruit! Buzzwords!
-
Hi, I'd like to run some simulations on a deck of 52 cards, but I don't know how to make it fast. Say, I want to draw 5 random cards from a deck. The most straightforward way to do this would be to create a List, List, List, etc. (whatever way the cards are represented), then draw a random number between 0-51, remove the card from the list, draw a number between 0-50, remove the card from the list, rinse & repeat until 5 cards are drawn. The problem is that adding/removing stuff is a costly operation. Can you see a fast way to randomly draw cards from a deck?
Hi, the strategy of putting all candidates in a collection, and extracting from there as many as you need in a random way, is correct. However, if you only want to extract a small fraction, it may be more economical to forget the collection, and just try 5 random numbers; whenever one is chosen that has been picked already, just throw the dice again. For 5 out of 52 that will occur in some 10% of the cases. If on the other hand, you decide to stick with the collection, there is no real need to build it over and over; once done, you can add the chosen items back to the collection. That would change the order, but then you could sort the collection (not sure that would be faster than recreating it), or you could ignore the issue, just relying on the randomness of the picking process. Strict randomness would mean the outcome does not depend on the previous outcome, so all candidates have the same probability, no matter where they are in the collection. Of course, if you are creating the perfect poker playing app, and are gambling your fortune, you may want to make sure, and follow the official ways... :)
Luc Pattyn [Forum Guidelines] [My Articles]
I use ListBoxes for line-oriented text (not TextBoxes), and PictureBoxes for pictures (not drawings).
modified on Friday, June 10, 2011 12:23 PM
-
Random rnd = new Random(); List myDeck = new List(); DateTime start = DateTime.Now; for (int loop = 0; loop < 1000000; ++loop) { myDeck.Clear(); for (int i = 0; i < 52; ++i) { myDeck.Add(i); } List hand = new List(); // Randomly remove a random card until the deck is empty for( int draw = 0; draw<5; ++draw ) { int cardIndex = rnd.Next(myDeck.Count); int card = myDeck[cardIndex]; myDeck.RemoveAt(cardIndex); hand.Add(card); } } DateTime end = DateTime.Now; [edit] - turned off the html tags - which kills the formatting, but at least you can see the generics! Help me! I'm turning into a grapefruit! Buzzwords!
Don't move the data around so much... Instead of shifting half the deck to remove a card, just move the last card into the empty slot. Runs in 125 ms. on my puter: :)
public class Deck {
private int\[\] \_cards; private int \_used; private Random \_rnd; public Deck() { \_cards = new int\[52\]; \_used = 0; \_rnd = new Random(); } public void Init() { for (int i = 0; i < 52; i++) { \_cards\[i\] = i; } \_used = 52; } public void GetHand(int\[\] hand) { for (int i=0;i<5;i++) { int index = \_rnd.Next(\_used); hand\[i\] = \_cards\[index\]; \_used--; \_cards\[index\] = \_cards\[\_used\]; } }}
Deck deck = new Deck();
int[] hand = new int[5];
for (int i = 0; i < 1000000; i++) {
deck.Init();
deck.GetHand(hand);
}Despite everything, the person most likely to be fooling you next is yourself.
-
Hi, the strategy of putting all candidates in a collection, and extracting from there as many as you need in a random way, is correct. However, if you only want to extract a small fraction, it may be more economical to forget the collection, and just try 5 random numbers; whenever one is chosen that has been picked already, just throw the dice again. For 5 out of 52 that will occur in some 10% of the cases. If on the other hand, you decide to stick with the collection, there is no real need to build it over and over; once done, you can add the chosen items back to the collection. That would change the order, but then you could sort the collection (not sure that would be faster than recreating it), or you could ignore the issue, just relying on the randomness of the picking process. Strict randomness would mean the outcome does not depend on the previous outcome, so all candidates have the same probability, no matter where they are in the collection. Of course, if you are creating the perfect poker playing app, and are gambling your fortune, you may want to make sure, and follow the official ways... :)
Luc Pattyn [Forum Guidelines] [My Articles]
I use ListBoxes for line-oriented text (not TextBoxes), and PictureBoxes for pictures (not drawings).
modified on Friday, June 10, 2011 12:23 PM
Luc Pattyn wrote:
If on the other hand, you decide to stick with the collection, there is no real need to build it over and over; once done, you can add the chosen items back to the collection.
Interresting idea. It shaved off about 25% of the executon time of the code I posted earlier. What I did was actually to leave the chosen items in the array, only swapping them to the unused area at the end. :)
Despite everything, the person most likely to be fooling you next is yourself.
-
Luc Pattyn wrote:
If on the other hand, you decide to stick with the collection, there is no real need to build it over and over; once done, you can add the chosen items back to the collection.
Interresting idea. It shaved off about 25% of the executon time of the code I posted earlier. What I did was actually to leave the chosen items in the array, only swapping them to the unused area at the end. :)
Despite everything, the person most likely to be fooling you next is yourself.
Yes I did that too, and it ran pretty fast. (400ms on my old comp) It's probably the best method. The List approach is really too slow for what I need (Monte Carlo simulations). Thanks everyone for your time.
-
Luc Pattyn wrote:
If on the other hand, you decide to stick with the collection, there is no real need to build it over and over; once done, you can add the chosen items back to the collection.
Interresting idea. It shaved off about 25% of the executon time of the code I posted earlier. What I did was actually to leave the chosen items in the array, only swapping them to the unused area at the end. :)
Despite everything, the person most likely to be fooling you next is yourself.
Hi Guffa, I didn't see your code until now; if you have an array, rather than a vague collection, swapping cards out of sight as you did is the right way to go IMO. Reinserting the chosen ones would mean: undo the swaps (which you should do in reverse order of course). The advantage now is you are restoring the exact state the array had to begin with without touching things that hadn't changed in the process. :)
Luc Pattyn [Forum Guidelines] [My Articles]
I use ListBoxes for line-oriented text (not TextBoxes), and PictureBoxes for pictures (not drawings).
modified on Friday, June 10, 2011 12:23 PM
-
Hi Guffa, I didn't see your code until now; if you have an array, rather than a vague collection, swapping cards out of sight as you did is the right way to go IMO. Reinserting the chosen ones would mean: undo the swaps (which you should do in reverse order of course). The advantage now is you are restoring the exact state the array had to begin with without touching things that hadn't changed in the process. :)
Luc Pattyn [Forum Guidelines] [My Articles]
I use ListBoxes for line-oriented text (not TextBoxes), and PictureBoxes for pictures (not drawings).
modified on Friday, June 10, 2011 12:23 PM
Actually, I just left the deck in the new order and included all cards again. As you wrote before, the order of the cards in the deck doesn't matter when you draw cards by random. :)
Despite everything, the person most likely to be fooling you next is yourself.
-
Actually, I just left the deck in the new order and included all cards again. As you wrote before, the order of the cards in the deck doesn't matter when you draw cards by random. :)
Despite everything, the person most likely to be fooling you next is yourself.
Yes I know, however not everyone tends to believe that. They start arguing it might be true for real random stuff, but then it is only pseudo-random and ... WTF. :)
Luc Pattyn [Forum Guidelines] [My Articles]
I use ListBoxes for line-oriented text output (not TextBoxes), and PictureBoxes for pictures (not drawings).
modified on Friday, June 10, 2011 12:24 PM
-
Yes I know, however not everyone tends to believe that. They start arguing it might be true for real random stuff, but then it is only pseudo-random and ... WTF. :)
Luc Pattyn [Forum Guidelines] [My Articles]
I use ListBoxes for line-oriented text output (not TextBoxes), and PictureBoxes for pictures (not drawings).
modified on Friday, June 10, 2011 12:24 PM
No problem, I'll just use this then:http://thedailywtf.com/Articles/Random-Stupidity.aspx[^] :p
-
No problem, I'll just use this then:http://thedailywtf.com/Articles/Random-Stupidity.aspx[^] :p
Great. I especially like "Random() returns increasingly randomer numbers the more you call it". :)
Luc Pattyn [Forum Guidelines] [My Articles]
I use ListBoxes for line-oriented text output (not TextBoxes), and PictureBoxes for pictures (not drawings).
modified on Friday, June 10, 2011 12:24 PM
-
Hi, I'd like to run some simulations on a deck of 52 cards, but I don't know how to make it fast. Say, I want to draw 5 random cards from a deck. The most straightforward way to do this would be to create a List, List, List, etc. (whatever way the cards are represented), then draw a random number between 0-51, remove the card from the list, draw a number between 0-50, remove the card from the list, rinse & repeat until 5 cards are drawn. The problem is that adding/removing stuff is a costly operation. Can you see a fast way to randomly draw cards from a deck?
It's a bit late to be posting on this thread, but I've been busy. I wrote a Cribbage card game, some years ago and the way that I did it was to implement a deck class which had a shuffle method, which simply filled a list with random cards (numbers 0-51), drawing again if already used. Dealing then simply became a matter of taking the 'next' card, tracked by an 'index' field. This had many advantages during testing since the deck was still there in the original order. Dont know if this is a good idea, or even relevant to your simulation idea.
Henry Minute If you open a can of worms, any viable solution *MUST* involve a larger can.
-
It's a bit late to be posting on this thread, but I've been busy. I wrote a Cribbage card game, some years ago and the way that I did it was to implement a deck class which had a shuffle method, which simply filled a list with random cards (numbers 0-51), drawing again if already used. Dealing then simply became a matter of taking the 'next' card, tracked by an 'index' field. This had many advantages during testing since the deck was still there in the original order. Dont know if this is a good idea, or even relevant to your simulation idea.
Henry Minute If you open a can of worms, any viable solution *MUST* involve a larger can.
Thank you for your input. Nope in my case this won't work, as you have to rebuild the deck. Creating a list is really the most straightforward way, but when you have to do this 1 million times+, it's too slow.
