A random collection of unique integers is a requirement for most card games and for many other applications as well. This is part two of a four part series about different ways to create a random selection of unique integers. Both the efficiency and the statistical distribution are analyzed with graphical results using the StopWatch object. The previous article (you can read it at this link) shows the commonly recommended but flawed methods recommended in other pages. This article shows you how to create the collection using a lambda expression and how this method performs with graphical results using the StopWatch object.
John McIlhinney left a comment to a blog I wrote about solving this problem using arrays. His comment showed a method to solve the problem using lambda expressions and collections. Actually, John did more than required since his code also dealt the cards:
Dim rng As New Random 'Create the deck. Dim deck = Enumerable.Range(1, 52) 'Shuffle the deck. deck = deck.OrderBy(Function(n) rng.Next) 'Deal four hands of five cards. Dim hands(3) As List(Of Integer) For i = 0 To 3 hands(i) = deck.Skip(i * 5).Take(5).ToList() Next
There's a tendency for some programmers - and I admit that I'm one of them - to use what they know instead of taking advantage of new technologies. Then there are others, like John, who gobble up the new stuff like a kid in a candy factory. It's instructive to take a closer look at John's code.
The first difference to notice is that he doesn't create an array; his code creates a System.Collections.Generic.IEnumerable(Of Integer) object instead.
Dim deck = Enumerable.Range(1, 52)
I used that object, but I immediately converted it into an array and use array processing for the rest of the program. Here's my code:
Dim Cards() As Integer ... Cards = Enumerable.Repeat(-1, Me.theSize).ToArray()
The second difference is that John uses a Lambda expression to generate the random integers:
Dim rng As New Random ... deck = deck.OrderBy(Function(n) rng.Next)
Lambda is a very compact technology often marked by how confusing it can be as much as anything else. This one is no exception. The place to start is the OrderBy method of the collection. OrderBy will sort a generic source by a keySelector value. But in this case we just want to sort the collection by itself. Next provides a random number and Function(n) returns an element of the collection selected using that random number. OrderBy, using deferred execution, places the deck collection in the order dictated by the random keySelector values, but doesn't replace the elements. The result is a random ordering.
In effect, this is a variation of the "shuffle" method, but you wouldn't know it just by looking at it. Microsoft recommends using these new technologies because they add "power and flexibility". But they do take some effort to learn about.
Since I checked out the relative efficiency of the previous two methods, I felt duty bound to check this one out too. For my first attempt, I simply recoded John's suggestion so it fit into my test program. To make everything equal, I assigned John's collection to an array at the end. The result seemed to show that these new methods made the efficiency of the program even worse!
Click Here to display the illustration
When I eliminated just that one assignment and ran the test again, the new methods dropped to a fraction of the previous results. In a later email, "Chris" explained that this happens due to the deferred execution feature of lambda expressions, "When you don't actually read any of the elements out of the shuffled enumerable, the elements never need to be ordered, so the OrderBy method isn't called." Good point!
I started to wonder how much benefit the lambda expression was providing and how much was due to the use of a collection rather than an array. So I recoded the entire thing to use collections throughout. Here's the result of that experiment:Comparing the "old style" shuffle with the "lambda" shuffle - using collections with both - gives this result.
Click Here to display the illustration
Surprise, "old style" code is still more efficient than using lambda expressions! But in the third article, we discover that it's not actually a statistically valid distribution.
So, the bottom line is ...
- Yes, collections are more efficient than arrays and it's worth learning how to use them.
- Lambda expressions are not only confusing, they're also not necessarily more efficient.
For the most efficient code, it always pays to check.
For those who might be interested in more depth, you can download this program here. I've left the old "array" statements in the code as comments so you can see what I've changed.
In the third article in this series, "Chris" weighs in with a new algorithm that beats everything to this point and shows us some well designed programming. Click here for the third article.