Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Card shuffling on ArrayList hangs..

 
Jon Camilleri
Ranch Hand
Posts: 664
Chrome Eclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
My card shuffling algorithm seems to be hanging up my machine quite a bit, any idea why?


 
Rob Spoor
Sheriff
Pie
Posts: 20550
57
Chrome Eclipse IDE Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Check your nested loop. The inner loop guard may never end because it's guard (previousIndex == newIndex) may never become true. But let's assume that eventually it will. Then your outer loop's guard (swapCount < number_of_swaps) will never become true because you never change swapCount.
 
Matthew Brown
Bartender
Posts: 4567
8
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You don't appear to be incrementing swapCount anywhere, which is probably why it hangs - the loop never ends.

That doesn't seem a very efficient shuffle algorithm, if you don't mind me saying - just randomly swapping pairs. For any given card, there's a reasonable chance it'll never be swapped. And if you want a better one - there happens to be one built in to the collections framework. You could swap your entire shuffle method for:
 
Jon Camilleri
Ranch Hand
Posts: 664
Chrome Eclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Matthew Brown wrote:You don't appear to be incrementing swapCount anywhere, which is probably why it hangs - the loop never ends.

That doesn't seem a very efficient shuffle algorithm, if you don't mind me saying - just randomly swapping pairs. For any given card, there's a reasonable chance it'll never be swapped. And if you want a better one - there happens to be one built in to the collections framework. You could swap your entire shuffle method for:


You are right, in fact I had the 'Ace of Spades' listed twice on my algorithm somehow, even though it's the swapping algorithm I've been using since I was 12 years old. My algorithm has taken advantage of the existing Collections.shuffle() method:


By the way do you know of any IDE backed code where I can switch on and off debugging code, similarly to the way #if is used in C#? (http://msdn.microsoft.com/en-us/library/4y6tbswk.aspx).
 
Matthew Brown
Bartender
Posts: 4567
8
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jon Camilleri wrote:By the way do you know of any IDE backed code where I can switch on and off debugging code, similarly to the way #if is used in C#?

I think the most common approach would be to use a logging framework such as log4j. Your log statements state the level they are at (e.g. "debug", "warning", "error"), and then a configuration file defines which levels should be output.

The advantage that has over conditional compilation is that it can be changed without recompiling, so you can turn on debugging on a deployed application. It also gives you lots of control over where the log is output - to the console, to a file, to a database etc.
 
Carey Brown
Ranch Hand
Posts: 1540
18
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I find that the suggest approach:

while being the simplest to implement, does not do a sufficient enough job of randomization for games. I find that, though the cards will be shuffled about, they tend to stay in the same general region of the deck. The approach I use is to, one by one, move a random card from one list to a new list.
 
Matthew Brown
Bartender
Posts: 4567
8
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:I find that the suggest approach:

while being the simplest to implement, does not do a sufficient enough job of randomization for games. I find that, though the cards will be shuffled about, they tend to stay in the same general region of the deck. The approach I use is to, one by one, move a random card from one list to a new list.

Really? The algorithm that the documentation describes wouild be perfectly random if the random number generator was perfectly random. In particular, it's actually functionally identical to the one you've just described - it shuffles in place but it performs the same logic:

This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.


Do that, with a perfect generator, and all permutations have exactly the same likelihood.
 
Campbell Ritchie
Sheriff
Pie
Posts: 49411
62
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Never write == true or == false. They are clumsy, and error-prone bits of code. You write if (shuffled) or if (!shuffled).
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic