I've implemented something similar in my THC WP7 application for generating a 52 card deck. It goes something like this, and is probably something similar you'll find on the net,
1. Initialize a byte array and int array, the former for the selected cards and the latter the result.
2. Pick a number at random if it's not selected add it the card[i], mark initial[i] as true.
3. Continue until i == 52.
There are a few improvements I might make:
1. Instead of storing the byte array I can initialize the int array to a sentinel, i <= -1 || i > 52. This eliminates the 52*size(byte) values on the stack. However, it requires an O(n) amount of time to initialize the values, possible constant for all intents and purposes.
2. Improve the random distribution by using the Fisher-Yates (Knuth) variant. This means that the range of values selected decreases by one meaning that the Nth value is only ever selected once. This is an O(c) improvement as 1 number per iteration is not selected.
However, I'm going to try to performance test before I make any improvements to gauge the necessity, aside from improving the random distribution. Currently I have 8 threads each selecting a random number, not yet selected. Maybe by moving to the other algorithms I can eliminate the need for concurrency.
No comments:
Post a Comment