Your stats knowledge/understanding seems to be way above mine ... but wouldn't this be just as good:
sub shuffle
{
my @in = @_;
my @out;
push @out, splice(@in, rand @in, 1) while @in;
@out;
}
? I always get kinda concerned about swapping, I don't know why, when a simple random ordering would suffice. But, I didn't really do that well in stats in university, and that was altogether too long ago to remember anyway. :-) Comparing speeds ...
use strict;
use Benchmark qw(cmpthese);
my @cards = 1..52;
cmpthese(-1,
{
shuffle => sub { shuffle(@cards) },
random_perm => sub { random_perm(@cards) },
});
sub random_perm {
my $n = my @p = @_;
for ( my $i = $#p; $i > 0; --$i ) {
my $j = int rand( $i + 1 );
@p[ $i, $j ] = @p[ $j, $i ];
}
return @p;
}
sub shuffle
{
my @in = @_;
my @out;
push @out, splice(@in, rand @in, 1) while @in;
@out;
}
which gives:
Rate random_perm shuffle
random_perm 6000/s -- -30%
shuffle 8606/s 43% --
which says that if random_perm is the optimal pseudo-random shuffler, then my code must be suboptimal in that it's skipping something in making it random. For the life of me, I can't think of what.
Update: Changed the benchmark to actually test a real shuffle (woops) - thanks to anonymonk below. Anonymonk points out that this doesn't scale to 52000, which is quite valid for those who need to sort "large" amounts. For those who are only sorting a deck of cards (a very popular subset of shuffling), this may be sufficient ;-)
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.