What's the efficiency and quality of this shuffling algorithm?

Question

This recent question about sorting randomly using C# got me thinking about the way I've sometimes shuffled my arrays in Perl.

@shuffled = sort { rand() <=> rand() } @array;

The proposed solution in the mentioned question is Fisher-Yates shuffle, which works in a linear time.

The question is: how efficient is my snippet and is such shuffle "really" random?

Answer 1

This is just intuition, but I think that using a sort like this will produce a set whose order is to some degree dependent on the order of the original set. The results of a truly random sort should not depend at all on the order of the original set. I can't explain why/how, maybe somebody else can (or show that it is in fact random)?

As to how efficient it is, I'm not sure, but it's probably not a whole lot less efficient than any other sort using sort, since AFAIK rand() is relatively cheap. I could be wrong there, though.

Answer 2

I'm not a Perl internals expert, so I don't know how "sort" will work here. However, most sort functions expect consistency in their comparisons, and I would expect them to work unpredictably if the function is itself random. Unfortunately, unpredictability is not the same as randomness, and so I'd have no confidence in your shuffled array. It may tend to put elements in some sort of order, just as a hastily created and complicated recurrence relation may not be random.

Rather than analyze the sort function, I'd suggest going with Fisher-Yates.

As Knuth said, randomness is too important to be left to chance.

Answer 3

I'm actually a bit surprised that your proposed shuffle works. In the implementation of the Perl sort function, it tries to get the elements of the array into ascending order depending on the value of your comparison function. The problem is, your comparison function doesn't return consistent answers! Sometimes it might say "foo" lt "bar", while other times it might say "bar" lt "foo". This has the possibility of confusing the sorting algorithm to the point where it never terminates, or terminates with a fatal error, or some other catastrophic failure.

Answer 4

The perl documentation on sort says this

The comparison function is required to behave. If it returns inconsistent results (sometimes saying $x[1] is less than $x[2] and sometimes saying the opposite, for example) the results are not well-defined.

So it's a bad idea to do that.

ETA: I just did a benchmark. On a 100000 element array, using a FY-shuffle is more than 10 times faster too.

Answer 5

There's a better Fisher-Yates shuffle function that doesn't use the sort builtin in the perlfaq4: How do I shuffle an array randomly?.

Answer 6

For one thing, you know that no matter the comparator you use sort() can't possibly be faster than O(n log n). So even if the shuffle it performs is fair, its performance will be worse.

So is the shuffle fair? It's obviously not fair for some (easy to analyze) sorting algorithms. Consider a simple bubble sort - in order for an element to move from one end to the other, the comparison function has to evaluate positive for n consecutive calls - a 1 in 2^n probability for what should be a 1 in n event. For quick sort, it's hard to analyze and it's possible that ends up being fair. But if it's important that it be right, do it the right way.

Answer 7

$ perldoc List::Util
⋮
  shuffle LIST
       Returns the elements of LIST in a random order

           @cards = shuffle 0..51      # 0..51 in a random order
⋮

That would be my suggestion.

Answer 8

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