Thursday 7 May 2009

System.Random not so random in a loop

When you need to generate a random number System.Random comes to mind:

int randomNumber = new Random ().Next ();

All well and good but did you know new Random () actually generates a sequence of random numbers and Next () simply returns the next random number in the sequence? The Random class could have been named more accurately as RandomSequence but I digress…. One more thing, did you know the random sequence is generated using a seed value and that if you specify the same seed value when constructing a new Random object you’ll get the same sequence of random numbers? And finally: did you know if you don’t specify a seed value, the seed value is initialised using the system clock which naturally “has finite resolution.”

If you answered no to all of the above and you need a random number go read the doco. If you’re an attentive reader, you’ll read this:

…using the parameterless constructor to create different Random objects in close succession creates random number generators that produce identical sequences of random numbers.

Which sucks because that’s exactly what happens if you use the above code in a loop on a machine that can execute that loop more than once before the clock ticks over. If that happens, the same seed value will be use and calling Next () on the new Random object will return the same value it did last time.

The easiest way to work around this is to instantiate your Random object outside the loop and then call Next () on that instance in the body of the loop:

Random randomSequence = new Random ();

for (int i = 0; i < 10; i++)
randomSequence.Next ();

If that doesn't suit, consider passing the Random constructor a seed value that increments with each iteration of the loop (the MSDN documentation suggests there may be performance implications if you create a new Random object repeatedly so watch out).

For what it’s worth, today we were dealing with this exact problem in the context of an anonymous method passed to the List<T>.Sort () delegate. The IComparer<T>.Compare () method supplied to Sort () only accepts two parameters (those to be compared).

int Compare( T x, T y)

As a developer, it’s easy to assume the anonymous method only has access to its parameters. In actual fact, variables in the “outer scope” are captured and made available to the delegate until the delegate referencing the anonymous method itself goes out of scope and become eligible for garbage collection:

The local variables and parameters whose scope contain an anonymous method declaration are called outer or captured variables of the anonymous method.

Read more about closures if you're interested...

What this means is that our anonymous method can access the Random instance declared in the outer scope:

Random randomSequence = new Random ();

delegate (string x, string y)
return x == y ? 0 : randomSequence.Next (-1, 1);

There’s some extra stuff going on here because the result returned must conform to the IComparer<T> interface in that it must return –1, 0, or 1 but the code in bold calls out the use of the outer variable within the anonymous method.

1 comment:

  1. Thanks for sharing - just what i needed. Google is indeed your friend ;-)


Spam comments will be deleted

Note: only a member of this blog may post a comment.