Re^2: Is this a fair shuffle?

Along the lines you mentioned, this works:

   my @shuffled = map { $_->[0] }
                  sort { $a->[1] <=> $b->[1] }
                  map { [ $_, rand() ] }
                  @unshuffled;
[download]

But compared to other approaches it is slow and memory-expensive.

This topic came up at a recent kw.pm meeting, and I played around and did some rudimentary benchmarks:

http://kw.pm.org/wiki/index.cgi?ListShuffle

2005-04-02 Janitored by Arunbear - replaced pre tags with code tags, to allow code extraction

Comment on Re^2: Is this a fair shuffle? Download Code

Replies are listed 'Best First'.
Re^3: Is this a fair shuffle? by Thargor (Scribe) on Apr 01, 2005 at 19:55 UTC
Hey even though I didn't start this question it is really interesting to me. Could you explain, point to somewhere I can read about it, or otherwise instruct me as to why my solution is slow. I see lots of posts with map and such in them and I have no clue about its function so I assume it will come up later in my reading of the llama book. And thankyou to any who take the time to give me some information on this subject.	[reply]
Re^4: Is this a fair shuffle? by fishbot_v2 (Chaplain) on Apr 01, 2005 at 21:59 UTC
Well, I pointed to the link with the discussion: http://kw.pm.org/wiki/index.cgi?ListShuffle ...but here is a quick summary. Your algorithm (and my mostly equivalent one) are memory expensive because they have to allocate for a random number for each element in the list. If you are sorting numbers, this amounts to a doubling of the memory footprint. It is slow because it is two pass, the first O(N), the second (the sort) O(NlogN). That's not terribly slow, but list shuffling can be accomplished with O(N) running time. So, a pure perl swap-shuffle is about 4 times faster, and the List::Util version is about 70 times faster, depending, of course on list-size.	[reply]
Re^3: Is this a fair shuffle? by Anonymous Monk on Apr 01, 2005 at 19:45 UTC
Sorry, I don't post here often and didn't preview as well as I should have. That should obviously have been: `my @shuffled = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [ $_, rand() ] } @unshuffled;` [download]	[reply] [d/l]