P is for Practical PerlMonks

### Re^3: Randomize word

by zdog (Priest)
 on Sep 12, 2004 at 09:13 UTC ( #390387=note: print w/replies, xml ) Need Help??

in reply to Re^2: Randomize word

Good looking out: obviously not optimal. I tried to figure out for myself what was going wrong.

First, I simplified the code itself a little further:

print join "", sort { rand() <=> 0.5 } split //, "abcde";

That does basically the same thing, except calls rand() once less per comparison.

Staring at it didn't do much good for me so I came up with a little test script of my own:

```use strict;
use warnings;

sub compare {
my (\$a, \$b) = @_;
my \$rand = rand();
print "\$a: \$rand; \$b: 0.5\n";
return \$rand <=> 0.5;
}

print join "", sort { compare(\$a, \$b) } split //, "abcde";

The output of which was something like:

```\$ perl test.pl
a: 0.876941476789401; b: 0.5
c: 0.0768385185833438; d: 0.5
b: 0.203632482365844; c: 0.5
c: 0.234952540459695; a: 0.5
a: 0.746254431212112; d: 0.5
b: 0.648884088019244; e: 0.5
ebcda

After running this a few times and looking at the results, it hit me. This is going to be a rough explanation, but I'll give it a shot. After comparing the first four letters to one another it selects the "smallest" one (the one with the smallest rand() anyway) and compares it to the final letter: 'e' in this case. Because 'e' is the last to be compared (in the initial go, at least) and because the rand() number is regenerated at each comparison, it always has roughly a 50% chance of being the "smallest" since it has to only pass a single test to be the "smallest". The letters in front of it must not only pass their first test, but will always have to be compared to the letters following it, thus reducing their chances of being the "smallest".

In this way, my "solution" favors the letters towards the end and is more likely to stick them in front. That's why the distribution is so uneven. If you follow sort()'s algorithm ( quicksort, I believe (C's qsort(), I think ) ) through, it'll make sense.

I hope that makes some sense ...

Zenon Zabinski | zdog | zdog@perlmonk.org

Replies are listed 'Best First'.
Re^4: Randomize word
by ysth (Canon) on Sep 12, 2004 at 09:56 UTC
Not C's qsort, nor by default a quicksort at all anymore. Note that on older perls (5.005ish?) that do use qsort, some platforms have a tendency to coredump if the sort routine provides inconsistent results. (Just heresay, never actually seen it myself.)

Here it says:

We have changed sort to use mergesort, which for me is rather surprising since I have been told since I was a toddler to use quicksort. However, the old behavior can be controlled using the sort module; we even have a mystery stable quicksort!

So the switch from quicksort to merge sort apparently happened with 5.8.0. Gee .. I'm out of date. Thanks for pointing that out as well.

Zenon Zabinski | zdog | zdog@perlmonk.org

Create A New User
Node Status?
node history
Node Type: note [id://390387]
help
Chatterbox?
 [BarApp]: I can not use modules. I gain temporary access and still can not use modules. [Cosmic37]: ta erix - this szabo geezer is pretty cool methinks and he writes about undef but I cannot see instructions for redefining the record separator after having undefined it [Corion]: \$/ = "wahtever"; [Corion]: (it's a magic variable) [karlgoethebier]: BarApp: whoami [Cosmic37]: ok fankyou - I was wondering about that but thought there might be a redefine command or something; peachy [Lotus1]: Cosmic37 if you undef \$/ in a local context to a block it won't affect the global version after the block finishes [Lotus1]: or you can just do local \$/ in a block

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (4)
As of 2017-06-29 16:48 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (672 votes). Check out past polls.