Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
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
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 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
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

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 perusing the Monastery: (6)
As of 2014-12-27 07:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (176 votes), past polls