H.L. Mencken once said:

There is always a well-known solution to every human problem--neat, plausible, and wrong.

It's generally agreed in the programming world that simple, easy to understand code is preferred over highly convoluted code even if it is at the expense of some efficiency.

A few days ago, Jeff Attwood wrote about what seemed to be a trivial programming exercise -- shuffling a deck of cards. Jeff's first idea went something like this:

for (int i = 0; i < cards.Length; i++)
{
    int n = rand.Next(cards.Length);
    Swap(ref cards[i], ref cards[n]);
}

It is only a couple of lines of code. How hard can it be to get it right? If only it were that simple!

Jeff explains in a later post how seriously flawed that shuffle algorithm is. The seemingly simple shuffle algorithm has a distinct bias. This becomes apparent only when it's tested over a very large number of runs.

The right way to shuffle is the Knuth-Fisher-Yates algorithm:

for (int i = cards.Length - 1; i > 0; i--)
{
    int n = rand.Next(i + 1);
    Swap(ref cards[i], ref cards[n]);
}

The difference in the code is subtle, to say the least. But as Jeff explains quite beautifully, it makes a world of difference in the net result.

This simple example explains excellently the need for two things:

1. A well thought out testing strategy, and
2. A deep understanding of the domain you're working in.

Who would've thought shuffling a deck of cards would be so hard to get right?

No Comments