comment on

Just for the heck of it, I decided to test the suffle() function found in Math::Random::MT::Auto. It, too, is an XS implementation like List::Util's shuffle().

#!/usr/bin/perl

use warnings;
use strict;

use Benchmark ':all';

use List::Util;
use Math::Random::MT::Auto;

my @sd;

my %shtest = (
    'LU'    => sub { my @r = List::Util::shuffle(@sd); },
    'MRMA'  => sub { my @r = @{Math::Random::MT::Auto::shuffle(@sd)}; 
+},
);

for my $N (map { 1 + 2 * 3**$_ } 0 .. 8) {
    print "\nTesting on $N elements\n";
    @sd = map { rand } 1 .. $N;
    cmpthese(-10, \%shtest);
}
[download]

Here's the results using Perl 5.8.8 under Cygwin:

Testing on 3 elements
         Rate MRMA   LU
MRMA 211325/s   -- -57%
LU   497044/s 135%   --

Testing on 7 elements
         Rate MRMA   LU
MRMA 149022/s   -- -35%
LU   230127/s  54%   --

Testing on 19 elements
        Rate MRMA   LU
MRMA 73936/s   -- -18%
LU   89976/s  22%   --

Testing on 55 elements
        Rate MRMA   LU
MRMA 30976/s   --  -2%
LU   31768/s   3%   --

Testing on 163 elements
        Rate   LU MRMA
LU   10788/s   --  -3%
MRMA 11109/s   3%   --

Testing on 487 elements
       Rate   LU MRMA
LU   3620/s   --  -5%
MRMA 3796/s   5%   --

Testing on 1459 elements
       Rate   LU MRMA
LU   1199/s   --  -6%
MRMA 1271/s   6%   --

Testing on 4375 elements
      Rate   LU MRMA
LU   397/s   --  -4%
MRMA 413/s   4%   --

Testing on 13123 elements
      Rate   LU MRMA
LU   122/s   --  -0%
MRMA 122/s   0%   --

I was happily surprised to see that for anything more than a few dozen items in the array, MRMA's shuffle() was as fast or a little faster than LU's. (I find this even more interesting given that LU is using the core rand functionality which is 5x faster than MRMA's irand function.)

However, if you want real speed, you should take advantage of MRMA's capability to shuffle an array in situ (something that LU's shuffle can't do). You do this by feeding it an array ref, and it shuffles the contents of the array itself (and not a copy of it).

Replacing the corresponding line above with:

    'MRMA' => sub { Math::Random::MT::Auto::shuffle(\@sd); }
[download]

yields:

Testing on 3 elements
         Rate   LU MRMA
LU   504901/s   -- -17%
MRMA 609845/s  21%   --

Testing on 7 elements
         Rate   LU MRMA
LU   232298/s   -- -49%
MRMA 457814/s  97%   --

Testing on 19 elements
         Rate   LU MRMA
LU    90294/s   -- -65%
MRMA 261096/s 189%   --

Testing on 55 elements
         Rate   LU MRMA
LU    32105/s   -- -72%
MRMA 114858/s 258%   --

Testing on 163 elements
        Rate   LU MRMA
LU   10830/s   -- -75%
MRMA 42676/s 294%   --

Testing on 487 elements
        Rate   LU MRMA
LU    3616/s   -- -76%
MRMA 14863/s 311%   --

Testing on 1459 elements
       Rate   LU MRMA
LU   1199/s   -- -76%
MRMA 5044/s 321%   --

Testing on 4375 elements
       Rate   LU MRMA
LU    397/s   -- -76%
MRMA 1683/s 324%   --

Testing on 13123 elements
      Rate   LU MRMA
LU   124/s   -- -78%
MRMA 565/s 355%   --

Even for the smallest of lists, MRMA is faster. For large lists, the comparison is overwhelming.

Remember: There's always one more bug.

In reply to Re: Benchmarking perfect shuffles by jdhedden
in thread Benchmarking perfect shuffles by ambrus

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.


Clear questions and runnable code get the best and fastest answer
	PerlMonks