Drawing Blanks

Premature Optimization is a Prerequisite for Success

Random Shuffle

with one comment

Here is a really funny story

http://techcrunch.com/2010/02/22/microsoft-ballot-screen/

I imagine how that happened:

Dude1: “Dude, how do I randomly shuffle an array?”

Dude2: “Easy: just sort it in a random order.”

Dude1: “Awesome idea! Here I go: array.Sort(randomOrder)”.

Instead of sorting the array in a random order, the dude sorted it using a random comparer. Which resulted in a non-uniform shuffle with distribution that depends on the sorting algorithm.

While this shuffle algorithm http://en.wikipedia.org/wiki/Fisher-Yates_shuffle remains the fastest, simplest and safest, sorting by a random key is not a wrong approach. But if we choose it, we need to be very cautious. We need to make sure the random keys don’t change during sorting, otherwise it may be same as using a random comparer. Check this out:

var list = Enumerable.Range(1, 10);
Random rand = new Random();
var sorted = list.OrderBy(i => rand.NextDouble()); 
 

The code looks suspiciously similar to the wrong implementation. But the parameter of Enumerable.OrderBy() is not a comparer, but rather a key selector. So this code should result in a uniform shuffle (assuming Random.NextDouble() is uniform). But imagine what happens if the OrderedEnumerable enumerator calls the key selector function each time it compares two elements. Then our random key selector becomes equivalent to the random comparer and the result is not uniform. I attempted to figure out how OrderedEnumerable actually works using Reflector, but I gave up. Instead I just ran some tests to check how many times the key selector gets called, and it appeared that it’s called only once for each element. But I would still use the Knuth – Fisher – Yates, of course.

Anagram of the day “uniform shuffle” = “snuff life humor”

Advertisements

Written by bbzippo

02/25/2010 at 6:46 am

Posted in fun, programming

One Response

Subscribe to comments with RSS.

  1. […] Keep in mind, if you want to simulate card games, use a reliable shuffling algorithm. […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: