http://qs321.pair.com?node_id=620387

logie17 has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks, I recently read this post on shuffling arrays. I put together a couple other methods of shuffling using the Knuth shuffle.
#! /usr/local/bin/perl use strict; use warnings; my @randomarray = ( 0 .. 100 ); my $sub1 = sub { for(my $j, my $x, my $i = scalar @randomarray; $i;$j = int(ran +d($i)), $x = $randomarray[--$i], $randomarray[$i] = $randomarray[$j], + $randomarray[$j] = $x){ } }; my $sub2 = sub { my $i = scalar @randomarray; while ($i){ my $j = int(rand($i)); my $x = $randomarray[--$i]; #next value $randomarray[$i] = $randomarray[$j]; #next value = ran +dom value $randomarray[$j] = $x; #current random value = next va +lue. } }; use Benchmark; timethese(100000, { 'Sub 1' => $sub1, 'Sub 2' => $sub2, });
I was wondering if I could get a little help to obfuscate the above benchmarks a little more? In true Perl style, such as perhaps using map or other better ways to iterate through the algorithm to help it gain even a better edge. Here are my benchmark results:
Benchmark: timing 100000 iterations of Sub 1, Sub 2... Sub 1: 28 wallclock secs (27.37 usr + 0.00 sys = 27.37 CPU) @ 36 +54.01/s (n=100000) Sub 2: 40 wallclock secs (32.25 usr + 0.00 sys = 32.25 CPU) @ 31 +00.78/s (n=100000)

It looks like using the For loop is a bit faster. Thank you for any comments in advance.

Cheers!
s;;5776?12321=10609$d=9409:12100$xx;;s;(\d*);push @_,$1;eg;map{print chr(sqrt($_))."\n"} @_;

Replies are listed 'Best First'.
Re: Array Shuffle
by GrandFather (Saint) on Jun 11, 2007 at 00:06 UTC

    List::Util's shuffle is a little faster still. Adding:

    my $sub3 = sub { shuffle (@randomarray); };

    and changing timethese to cmpthese (with other changes as required) gives:

    Rate Sub 2 Sub 1 Sub 32 Sub 2 14869/s -- -13% -89% Sub 1 17066/s 15% -- -87% Sub 32 131573/s 785% 671% --

    DWIM is Perl's answer to Gödel
      Isn't List::Util's shuffle implemented in C/XS? I'd be more interested in seeing a comparion where both algorithms were implemented in C/XS (or where both algorithms were implemented in Perl).
        ikegami,
        Well, yes. It falls back to a pure perl version if the XS version isn't available. This is unlikely to happen since List::Util is part of the core but there is nothing preventing you from using the pure perl version as part of the benchmark.

        Cheers - L~R

        I understand your intellectual curiosity wrt the algorithm, but my post was more a subtle hint that using a pre-packaged wheel is often a better way of spending time than polishing your own variant. Seems from OP's reply I picked the right answer.

        From the benchmark results I guessed XS was likely lurking in the background somewhere, but in this case that can be treated as a reasonable optimisation by the module author. There is no hint in the List::Util docs that indicate the implementation method, however the guts of the routine seems to be:

        for (index = items ; index > 1 ; ) { int swap = (int)(Drand01() * (double)(index--)); SV *tmp = ST(swap); ST(swap) = ST(index); ST(index) = tmp; } XSRETURN(items);

        DWIM is Perl's answer to Gödel
      GrandFather, Thank you for the reference to List::Util. I was actually just seeking a way to improve my current algorithms. (To squeeze as much out of Perl as I possibly could for my own personal edification). I would curious ot know if List Util using C to gain the edge?

      Thanks again
      s;;5776?12321=10609$d=9409:12100$xx;;s;(\d*);push @_,$1;eg;map{print chr(sqrt($_))."\n"} @_;