Banaticus407
04-17-2005, 12:09 AM
Ok, I don't really know much about perl. The following is from a friend that I thought I'd help out. After you read it all, anyone have any comments on it? See any ways to improve it?
The first implementation of this was to simulate the drawing of x cards from a deck of cards, jokers included. The immediate solution is to just roll a random number between 1 and 54, repeating it for x many of cards, however you'd need to check each iteration to make sure you hadn't already rolled that random number, and if you had, roll again.
However I didn't try to implement this the first time around for exactly the reason the technically minded would be thinking about; for high numbers of x, you'd be doing an awful lot of re-rolling. If the person asked for 54 cards then the final card would actually only have 1 valid option, and it'd keep on doing a random generation until it got that number. 54 cards would actually require approximately 1,458 random rolls, if my maths is correct.
So I decided to try and be tricky... for each iteration through the loop I'd reduce the random range by 1. First time around it'd be 1 - 54, 2nd time around it'd be 1 - 53, 3rd time around it'd be 1 - 52, etc etc.
Then, once I'd rolled the random number, I'd add one to it for every number lower than it that had been generated before.
for ($i=0;$i<$num_cards;$i++)
{
$this_roll = rubb_rand($die_size - $i);
for (sort { $card_drawn[$a] <=> $card_drawn[$b] } 0 .. $i - 1)
{
$this_roll++ if $this_roll >= $card_drawn[$_];
}
$card_drawn[$i] = $this_roll;
Now that I've scared everyone away with that, I did some benchmark testing.
Picking 4 cards from a deck of 54, it's twice as fast just to reroll duplicates than to try and do the trickery above. The more cards you pick the faster it is, picking 10 cards is six times faster, picking all 54 reveals that the 1,458 rolls that the hit & miss approach uses is about thirty times faster than trying to tally and compensate.
Going even further; 10,000 choosing 10,000 is one hundred and twenty times faster using the simple "reroll if already rolled" method. I guess that nested for loop takes a heavy toll, I even managed to optimise it so it doesn't need a sort, but that only improved it to the scores above.
The first implementation of this was to simulate the drawing of x cards from a deck of cards, jokers included. The immediate solution is to just roll a random number between 1 and 54, repeating it for x many of cards, however you'd need to check each iteration to make sure you hadn't already rolled that random number, and if you had, roll again.
However I didn't try to implement this the first time around for exactly the reason the technically minded would be thinking about; for high numbers of x, you'd be doing an awful lot of re-rolling. If the person asked for 54 cards then the final card would actually only have 1 valid option, and it'd keep on doing a random generation until it got that number. 54 cards would actually require approximately 1,458 random rolls, if my maths is correct.
So I decided to try and be tricky... for each iteration through the loop I'd reduce the random range by 1. First time around it'd be 1 - 54, 2nd time around it'd be 1 - 53, 3rd time around it'd be 1 - 52, etc etc.
Then, once I'd rolled the random number, I'd add one to it for every number lower than it that had been generated before.
for ($i=0;$i<$num_cards;$i++)
{
$this_roll = rubb_rand($die_size - $i);
for (sort { $card_drawn[$a] <=> $card_drawn[$b] } 0 .. $i - 1)
{
$this_roll++ if $this_roll >= $card_drawn[$_];
}
$card_drawn[$i] = $this_roll;
Now that I've scared everyone away with that, I did some benchmark testing.
Picking 4 cards from a deck of 54, it's twice as fast just to reroll duplicates than to try and do the trickery above. The more cards you pick the faster it is, picking 10 cards is six times faster, picking all 54 reveals that the 1,458 rolls that the hit & miss approach uses is about thirty times faster than trying to tally and compensate.
Going even further; 10,000 choosing 10,000 is one hundred and twenty times faster using the simple "reroll if already rolled" method. I guess that nested for loop takes a heavy toll, I even managed to optimise it so it doesn't need a sort, but that only improved it to the scores above.