Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re^4: A bad shuffle

by tlm (Prior)
on Mar 22, 2005 at 02:41 UTC ( #441372=note: print w/ replies, xml ) Need Help??


in reply to Re^3: A bad shuffle
in thread A bad shuffle

Yes, I was looking at the code for List::Util earlier today. In addition to the C implementatin of the Fisher-Yates shuffle, it includes the following "backup" in Perl:

sub shuffle (@) { my @a=\(@_); my $n; my $i=@_; map { $n = rand($i--); (${$a[$n]}, $a[$n] = $a[$i])[0]; } @_; }
Pretty gnarleous, IMO. Kind of like a hybrid between F-Y and Tanktalus's shuffler.

The C implementation of List::Util::shuffle is 10-20x faster than the Perl implementation. For the practical programmer: end of story. Still, to satisfy my monkly preoccupation with how many angels can lambada on the head of a pin, and more importantly, in order to reduce this dead horse to a thin protein film, I benchmarked the three shufflers: ta = Tanktalus's shuffler; lu = Perl implementation of List::Util::shuffle; rp = random_perm:

N = 1000 Rate rp lu ta rp 230/s -- -10% -22% lu 257/s 12% -- -13% ta 296/s 29% 15% -- N = 10_000 Rate ta lu rp ta 14.3/s -- -27% -34% lu 19.6/s 37% -- -10% rp 21.7/s 52% 11% -- N = 100_000 Rate ta lu rp ta 0.144/s -- -92% -93% lu 1.75/s 1118% -- -13% rp 2.01/s 1302% 15% --

the lowliest monk


Comment on Re^4: A bad shuffle
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://441372]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (6)
As of 2015-07-31 01:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (274 votes), past polls