Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Re: Re: Re: random elements from array - new twist

by BrowserUk (Pope)
on Nov 05, 2002 at 18:23 UTC ( #210544=note: print w/ replies, xml ) Need Help??


in reply to Re: Re: random elements from array - new twist
in thread random elements from array - new twist

FWIW. To the best of my ability to test it, and walking on the shoulders of those better versed in statistics than I, my implementation of Fisher-Yates algorithm compares favourably with that given in the FAQ.

Perhaps you would point out the flaws in my testing method?

Test code

#!/usr/bin/perl -w use strict; use vars qw/$size $iter/; use Benchmark qw(cmpthese); use Data::Dumper; $size ||= 1000; $iter ||= 1000; sub FAQ_FY { my $array = shift; my $i; for ($i = @$array; --$i; ) { my $j = int rand ($i+1); next if $i == $j; @$array[$i,$j] = @$array[$j,$i]; } } sub shuffl (\@) { my $r=pop; $a = $_ + rand @{$r} - $_ and @$r[$_, $a] = @$r[$a, $_] for (0..$#{$r}); } my @array = 1 .. $size; cmpthese(-1, { FAQ_FY => sub { FAQ_FY \@array }, shuffl => sub { shuffl @array }, }); my (%buckets, %d, @temp);; my @set = qw(A B C D); for (1 .. $iter ) { @temp=@set; FAQ_FY \@temp; $buckets{"@temp"}{FAQ_FY}++; @temp=@set; shuffl @temp; $buckets{"@temp"}{shuffl}++; } print "\npermutation | FAQ_FY | shuffl \n"; print "----------------------------------\n"; for my $key (sort keys %buckets) { printf "%8.8s: | %4d | %4d \n", $key, $buckets{$key}{FAQ_FY}, $buckets{$key}{shuffl}, $d{FAQ_FY}{Ex} += $buckets{$key}{FAQ_FY}; $d{FAQ_FY}{Ex2} += $buck +ets{$key}{FAQ_FY}**2; $d{shuffl}{Ex} += $buckets{$key}{shuffl}; $d{shuffl}{Ex2} += $buck +ets{$key}{shuffl}**2; } print "------------------------------------------------------\n"; printf "Std. Dev. | %0.3f | %0.3f \n", sqrt( ($d{FAQ_FY}{Ex2} - ($d{FAQ_FY}{Ex}**2/24))/23 ), sqrt( ($d{shuffl}{Ex2} - ($d{shuffl}{Ex}**2/24))/23 ); __END__

C:\test>199981 -size=100 -iter=100000 Benchmark: running FAQ_FY, shuffl, each for at least 1 CPU seconds... FAQ_FY: 2 wallclock secs ( 1.14 usr + 0.00 sys = 1.14 CPU) @ 39 +2.64/s (n=448) shuffl: 1 wallclock secs ( 1.08 usr + 0.00 sys = 1.08 CPU) @ 44 +2.70/s (n=479) Rate FAQ_FY shuffl FAQ_FY 393/s -- -11% shuffl 443/s 13% -- permutation | FAQ_FY | shuffl ---------------------------------- A B C D: | 4140 | 4221 A B D C: | 4231 | 4211 A C B D: | 4205 | 4151 A C D B: | 4247 | 4257 A D B C: | 4076 | 4275 A D C B: | 4107 | 4244 B A C D: | 4207 | 4165 B A D C: | 4159 | 4240 B C A D: | 3941 | 4187 B C D A: | 4136 | 4116 B D A C: | 4158 | 4126 B D C A: | 4185 | 4111 C A B D: | 4126 | 4231 C A D B: | 4224 | 4122 C B A D: | 4135 | 4139 C B D A: | 4123 | 4097 C D A B: | 4179 | 4001 C D B A: | 4228 | 4175 D A B C: | 4295 | 4057 D A C B: | 4264 | 4131 D B A C: | 4206 | 4169 D B C A: | 4138 | 4239 D C A B: | 4167 | 4208 D C B A: | 4123 | 4127 ------------------------------------------------------ Std. Dev. | 72.382 | 67.643 C:\test>

Nah! You're thinking of Simon Templar, originally played (on UKTV) by Roger Moore and later by Ian Ogilvy


Comment on Re: Re: Re: random elements from array - new twist
Select or Download Code
Replies are listed 'Best First'.
Re: Re: Re: Re: random elements from array - new twist
by jsprat (Curate) on Nov 05, 2002 at 19:49 UTC
    Your algorithm is not a Fisher-Yates shuffle. shuffl chooses a random number between 1 and the number of elements (inclusive) each time. A Fisher-Yates shuffle chooses from a smaller set each iteration to avoid performing a biased shuffle.

    Using the dataset A, B, C and D there are 24 possible outcomes (4!), each one with an equal probability of 1/24. The algorithm used for sub shuffl selects 4 random numbers each with a possible value of 1, 2, 3 or 4, or a total of 44 (256) possible outcomes, each with a probability of 1/256 (some of the final permutations are duplicated). 256 is not evenly divisible by 24, so some of the outcomes must be more likely than others.

    Update: Oops. BrowserUK's shuffle is indeed a Fisher-Yates shuffle. $a = $_ + rand @{$r} - $_ is parsed as $a = $_ + (rand @{$r} - $_). I assumed it would be parsed as $a = $_ + (rand @{$r}) - $_

      Look again!

      Update: Maybe this will clarify things a little?

      #! perl -sw use strict; sub shuffl (\@) { my $r=pop; for (0..$#{$r}) { my $size = scalar @{$r}; my $choices = $size - $_; printf 'iteration: %2d Size: %2d rand(%2d) range: %2d .. % +2d %s', $_, $size, $choices, $_, $cho +ices + $_, $/; $a = $_ + rand @{$r} - $_; @$r[$_, $a] = @$r[$a, $_]; } } my @array = (1 ..15); shuffl @array; __END__ C:\test>210557 iteration: 0 Size: 15 rand(15) range: 0 .. 15 iteration: 1 Size: 15 rand(14) range: 1 .. 15 iteration: 2 Size: 15 rand(13) range: 2 .. 15 iteration: 3 Size: 15 rand(12) range: 3 .. 15 iteration: 4 Size: 15 rand(11) range: 4 .. 15 iteration: 5 Size: 15 rand(10) range: 5 .. 15 iteration: 6 Size: 15 rand( 9) range: 6 .. 15 iteration: 7 Size: 15 rand( 8) range: 7 .. 15 iteration: 8 Size: 15 rand( 7) range: 8 .. 15 iteration: 9 Size: 15 rand( 6) range: 9 .. 15 iteration: 10 Size: 15 rand( 5) range: 10 .. 15 iteration: 11 Size: 15 rand( 4) range: 11 .. 15 iteration: 12 Size: 15 rand( 3) range: 12 .. 15 iteration: 13 Size: 15 rand( 2) range: 13 .. 15 iteration: 14 Size: 15 rand( 1) range: 14 .. 15 C:\test>

      Nah! You're thinking of Simon Templar, originally played (on UKTV) by Roger Moore and later by Ian Ogilvy
Re: Re: Re: Re: random elements from array - new twist
by petral (Curate) on Nov 08, 2002 at 19:48 UTC
    "MAKEUP!", er, I mean, "Did somebody say 'Benchmark'?":
    use vars '@r'; sub supffl (\@) { local *r = pop; my $sz = @r; my $i = -1; while ($sz) { $a = ++$i + rand $sz--; @r[$i, $a] = @r[$a, $i]; } } =pod $ supshfl.pl Benchmark:running FAQ_FY, shuffl, supffl, each for at least 2 CPU sec FAQ_FY: 2 wc secs(2.19 usr + 0.00 sys = 2.19 CPU) @ 19.63/s (n=43) shuffl: 2 wc secs(2.13 usr + 0.00 sys = 2.13 CPU) @ 21.60/s (n=46) supffl: 2 wc secs(2.16 usr + 0.00 sys = 2.16 CPU) @ 23.15/s (n=50) Rate FAQ_FY shuffl supffl FAQ_FY 19.6/s -- -9% -15% shuffl 21.6/s 10% -- -7% supffl 23.1/s 18% 7% -- permutation | FAQ_FY | shuffl | supffl ------------------------------------------- ------------------------------------------- Std. Dev. | 6.404 | 6.397 | 5.746 =cut
    Though 20% hardly seems worth it.

    Basically, it's their efficiently checking for  $i == $j which slows down FAQ_FY!    mumble, mumble . . . premature optimization . . . mumble, mumble . . .
    sub FAQ_FY { my $array = shift; my $i; for ($i = @$array; --$i; ) { my $j = int rand ($i+1); # next if $i == $j; @$array[$i,$j] = @$array[$j,$i]; } } =pod $ supshfl.pl Benchmark:running FAQ_FY, shuffl, supffl, each for at least 1 CPU sec FAQ_FY: 1 wc secs(1.05 usr + 0.00 sys = 1.05 CPU) @ 21.90/s (n=23) shuffl: 1 wc secs(1.07 usr + 0.00 sys = 1.07 CPU) @ 21.50/s (n=23) supffl: 1 wc secs(1.04 usr + 0.00 sys = 1.04 CPU) @ 23.08/s (n=24) Rate shuffl FAQ_FY supffl shuffl 21.5/s -- -2% -7% FAQ_FY 21.9/s 2% -- -5% supffl 23.1/s 7% 5% -- permutation | FAQ_FY | shuffl | supffl -------------------------------------------- -------------------------------------------- Std. Dev. | 7.305 | 6.105 | 5.998 =cut

      p
Re: Re: Re: Re: random elements from array - new twist
by Anonymous Monk on Nov 06, 2002 at 03:26 UTC
    You are right...and accidentally demonstrated why you should break things out a little more and put in parens. I am a decent Perl programmer, and that code is unmaintainable.

    Just because Perl lets you do something doesn't mean that you should.

      You have a good point. In truth, I wrote that function several months back when I first started exploring perl's syntax. When the question came up, I just grepped for the line and c&p'd it into the answer as a means of demonstrating the concept. I wasn't trying to sell or promote that particular implementation of shuffle.

      I am kind of embarrassed to have had to defend it.



      Nah! You're thinking of Simon Templar, originally played (on UKTV) by Roger Moore and later by Ian Ogilvy

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (4)
As of 2015-07-30 03:50 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 (269 votes), past polls