Re: A bad shuffle

[Tanktalus]

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 ;-)