I probably would have used a fisher-yates shuffle or the shuffle() from List::Util.
Benchmarking shows that the XS version is much, much faster
than anything done in Perl. But if you stick to a Perl
solution, one that acts on an array instead of a list is
the winner. Here are some benchmark results, followed by
the benchmark itself. Note the dramatic decrease in performance of 'coruscate' when the lenght of the list to
be sorted increases - this is due to the splicing, which
results in a quadratic algorithm; all other solutions are
linear.
Benchmarking with a deck of 13.
Rate roger coruscate fisher fisher2 list
roger 18931/s -- -0% -4% -21% -85%
coruscate 18959/s 0% -- -4% -20% -85%
fisher 19747/s 4% 4% -- -17% -85%
fisher2 23821/s 26% 26% 21% -- -82%
list 129419/s 584% 583% 555% 443% --
Benchmarking with a deck of 52.
Rate fisher roger coruscate fisher2 list
fisher 4917/s -- -2% -3% -18% -85%
roger 5021/s 2% -- -1% -17% -85%
coruscate 5062/s 3% 1% -- -16% -85%
fisher2 6031/s 23% 20% 19% -- -82%
list 33210/s 575% 561% 556% 451% --
Benchmarking with a deck of 1024.
Rate coruscate fisher roger fisher2 list
coruscate 246/s -- -2% -6% -21% -86%
fisher 251/s 2% -- -4% -19% -86%
roger 261/s 6% 4% -- -16% -85%
fisher2 310/s 26% 23% 19% -- -82%
list 1767/s 619% 603% 577% 471% --
Benchmarking with a deck of 50000.
Rate coruscate fisher roger fisher2 list
coruscate 0.909/s -- -72% -73% -85% -94%
fisher 3.19/s 251% -- -7% -47% -78%
roger 3.43/s 277% 7% -- -43% -76%
fisher2 6.03/s 563% 89% 76% -- -58%
list 14.3/s 1474% 349% 318% 137% --
#!/usr/bin/perl
use strict;
use warnings;
use List::Util;
use Benchmark qw /timethese cmpthese/;
our (@cards, @cards2, @tmp);
foreach my $size (qw /13 52 1024 50000/) {
@cards = 1 .. $size;
@cards2 = 1 .. $size;
print "Benchmarking with a deck of $size.\n";
cmpthese -10 => {
roger => '@tmp = roger @cards',
coruscate => '@tmp = coruscate @cards',
fisher => '@tmp = fisher @cards',
fisher2 => ' fisher2 \@cards2',
list => '@tmp = List::Util::shuffle @cards',
};
}
sub roger {
my @new = ();
for (@_) {
my $i = int rand($#new+1);
push @new, $new[$i];
$new[$i] = $_;
};
return(@new);
}
sub coruscate {
my @orig_deck = @_;
my @new_deck;
for (0 .. $#orig_deck) {
my $rand = int(rand $#orig_deck);
push @new_deck, splice(@orig_deck, $rand, 1);
}
return @new_deck;
}
sub fisher {
my $i = my @deck = @_;
while (-- $i) {
my $j = int rand ($i + 1);
@deck [$i, $j] = @deck [$j, $i];
}
@deck;
}
sub fisher2 {
my $deck = shift;
my $i = @$deck;
while (-- $i) {
my $j = int rand ($i + 1);
@$deck [$i, $j] = @$deck [$j, $i];
}
}
__END__
Abigail
| [reply]
[d/l] |
