Re^3: Is this a fair shuffle?

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.

Comment on Re^3: Is this a fair shuffle?

Replies are listed 'Best First'.
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]

Replies are listed 'Best First'.

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]