Re: Is this a fair shuffle?

Replies are listed 'Best First'.
Re^2: Is this a fair shuffle? by Roy Johnson (Monsignor) on Apr 01, 2005 at 04:46 UTC
I guess I should have suspected that it had been done before. Thanks for the link. Good benchmark there. Incidentally, if you change the qshuf sub to be `sub qshuf { sort { .5 <=> rand(1) } sort { .5 <=> rand(1) } sort { .5 <=> rand(1) } sort { .5 <=> rand(1) } @_; }` [download] The Std Dev drops to competitive levels, but the performance drops to last. Two or three calls to sort isn't sufficient. It was surprising to me that the time required for two chained sorts is so much more than for one. Caution: Contents may have been coded under pressure.	[reply] [d/l]
Re^3: Is this a fair shuffle? by BrowserUk (Patriarch) on Apr 01, 2005 at 04:56 UTC
I often wondered how using a random "constant" would change things but I never got around to trying it. It would also be good to add List::Util::shuffle to the benchmark. I assume it would beat my perl implementation hands down for small arrays, but mine is probably still quicker for large arrays because it operates in place? Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. Rule 1 has a caveat! -- Who broke the cabal?	[reply]
Re^4: Is this a fair shuffle? by Roy Johnson (Monsignor) on Apr 01, 2005 at 05:12 UTC
I just looked again, and your shufl sorts things in-place. That's not fair. But it doesn't seem to make a lot of difference in the benchmark time. I also tried changing qshuf to not be inconsistent, like so: `sub qshuf { my %hash; sort { $hash{$a}{$b}\|\|=(.5 <=> rand 1) } @_; }` [download] That is, it caches the value for each pairwise comparison, but it still doesn't shuffle well. Of course, there is the possibility of a > b > c > a... Update: I have a winner! `sub qshuf { my %hash; sort { ($hash{$a}\|\|=rand 1) <=> ($hash{$b}\|\|=rand 1) } @_; } Rate xform slice shufl qshuf xform 65.6/s -- -34% -72% -100% slice 99.7/s 52% -- -57% -100% shufl 233/s 255% 133% -- -99% qshuf 44494/s 67764% 44534% 19019% -- permutation \| slice \| xform \| shufl \| qshuf -------------------------------------------------- Std. Dev. \| 69.974 \| 58.895 \| 53.532 \| 62.689` [download] Caution: Contents may have been coded under pressure.	[reply] [d/l] [select]
Re^5: Is this a fair shuffle? by blokhead (Monsignor) on Apr 01, 2005 at 05:29 UTC
Re^5: Is this a fair shuffle? by Anonymous Monk on Apr 01, 2005 at 09:39 UTC
Re^5: Is this a fair shuffle? by BrowserUk (Patriarch) on Apr 01, 2005 at 05:18 UTC
Re^6: Is this a fair shuffle? by Roy Johnson (Monsignor) on Apr 01, 2005 at 11:51 UTC
Some notes below your chosen depth have not been shown here
Re^4: Is this a fair shuffle? by tlm (Prior) on Apr 01, 2005 at 13:37 UTC
It would also be good to add List::Util::shuffle to the benchmark. I assume it would beat my perl implementation hands down for small arrays, but mine is probably still quicker for large arrays because it operates in place? If you are referring to the Perl implementation of `List::Util::shuffle`, then yes a Perl implementation of FY (like yours) wins, but naturally the C implementation of `List::Util::shuffle` (which is the default) handily beats a Perl implementation of FY (lup = `List::Util::shuffle` in Perl; luc = `List::Util::shuffle` in C; fyp = Fisher-Yates in Perl): `Rate lup fyp luc lup 1.64/s -- -12% -83% fyp 1.87/s 14% -- -80% luc 9.43/s 476% 406% --` [download] That's for sorting an array of 10⁵ elements. the lowliest monk	[reply] [d/l] [select]