CodeSOD: A Sort of Random

Linda found some C# code that generates random numbers. She actually found a lot of code which does that, because the same method was copy/pasted into a half dozen places. Each of those places was a View Model object, and each of those View Models contained thousands of lines of code.

There's a lot going on here, so we'll start with some highlights. First, the method signature:

// Draws a number of items randomly from a list of available items // numToDraw: the number of items required // availableList: the list of all possible items, including those previously drawn // excludeList: items previously drawn, that we don't want drawn again public List<MyObject> GetRandomNumbers(int numToDraw, List<MyObject> availableList, List<MyObject> excludeList)

We want to pull numToDraw items out of availableList, selected at random, but without including the excludeList. Seems reasonable.

Let's skip ahead, to the loop where we draw our numbers:

while (result.Count != numToDraw) { // Add a delay, to ensure we get new random numbers - see GetRand(min, max) below Task.Delay(1).Wait(1); // Get a random object from the available list int index = GetRand(nextMinValue, nextMaxValue);

Wait, why is there a Wait? I mean, yes, the random number generator is seeded by the clock, but once seeded, you can pull numbers out of it as fast as you want. Perhaps we should look at GetRand, like the comment suggests.

// Returns a random value between min (inclusive) and max (exclusive) private int GetRand(int min, int max) { // Get a new Random instance, seeded by default with the tick count (milliseconds since system start) // Note that if this method is called in quick succession, the seed could easily be the same both times, // returning the same value Random random = new Random(); return random.Next(min, max); }

Ah, of course, they create a new Random object every time. They could just create one in the GetRandomNumbers method, and call random.Next, but no, they needed a wrapper function and needed to make it the most awkward and difficult thing to use. So now they have to add a millisecond delay to every loop, just to make sure that the random number generator pulls a new seed.

There are some other highlights, like this comment:

// Copy-paste the logic above, but for the max value // This condition will never be true though, because nextRand(min, max) returns a number between min (inclusive) // and max (exclusive), so will never return max value. Which is just as well, because otherwise nextMaxValue // will be set to the largest value not picked so far, which would in turn never get picked.

But one really must see the whole thing to appreciate everything that the developer did here, which they helpfully thoroughly documented:

// Draws a number of items randomly from a list of available items // numToDraw: the number of items required // availableList: the list of all possible items, including those previously drawn // excludeList: items previously drawn, that we don't want drawn again public List<MyObject> GetRandomNumbers(int numToDraw, List<MyObject> availableList, List<MyObject> excludeList) { if (availableList == null || numToDraw > availableList.Count) { // Can't draw the required number of objects return new List<MyObject>(); } List<MyObject> result = new List<MyObject>(); // Get limits for drawing random numbers int nextMinValue = 0; int nextMaxValue = availableList.Count; // Keep track of which items have already been drawn List<int> addedIndex = new List<int>(); while (result.Count != numToDraw) { // Add a delay, to ensure we get new random numbers - see GetRand(min, max) below Task.Delay(1).Wait(1); // Get a random object from the available list int index = GetRand(nextMinValue, nextMaxValue); // Check if we have drawn this item before if (!addedIndex.Contains(index)) { // We haven't drawn this item before, so mark it as used // Otherwise... we'll continue anyway addedIndex.Add(index); // Using a sorted list would make checking for the presence of "index" quicker // Too bad we aren't using a sorted list, or a HashSet addedIndex.Sort(); } // In order to avoid redrawing random numbers previously drawn as much as possible, reduce the range if (nextMinValue == index) { // We have just drawn the minimum possible value, so find the next minimum value that hasn't been drawn int tempValue = nextMinValue + 1; while (true) { // Look through the list to find "tempValue". O(N), since it is a list, and I don't think the compiler // will know it's been sorted if (addedIndex.FindIndex(i => { return i == tempValue; }) < 0) { nextMinValue = tempValue; break; } if (tempValue == nextMaxValue) { // Check that we haven't drawn all possible numbers break; } tempValue++; } } // Copy-paste the logic above, but for the max value // This condition will never be true though, because nextRand(min, max) returns a number between min (inclusive) // and max (exclusive), so will never return max value. Which is just as well, because otherwise nextMaxValue // will be set to the largest value not picked so far, which would in turn never get picked. if (nextMaxValue == index) { int tempValue = nextMaxValue - 1; while (true) { if (addedIndex.FindIndex(i => { return i == tempValue; }) < 0) { nextMaxValue = tempValue; break; } if (tempValue == nextMinValue) break; tempValue--; } } // Check that the picked item hasn't been picked before (I thought this was the point of added index?) // and that it doesn't exist in the excluded list MyObject tempObj1 = result.Find(i => { return i.ID == availableList[index].ID; }); MyObject tempObj2 = null; if (excludeList != null) { // this could have been a one-liner with the null conditional excludeList?.Find..., but that's fine tempObj2 = excludeList.Find(i => { return i.ID == availableList[index].ID; }); } if (tempObj1 == null && tempObj2 == null) { // Hasn't been picked, and is allowed because it isn't in the exclude list availableList[index].IsSelected = true; result.Add(availableList[index]); } } return result; } // Returns a random value between min (inclusive) and max (exclusive) private int GetRand(int min, int max) { // Get a new Random instance, seeded by default with the tick count (milliseconds since system start) // Note that if this method is called in quick succession, the seed could easily be the same both times, // returning the same value Random random = new Random(); return random.Next(min, max); }

I love all the extra Sort calls, and I love this comment about them:

// Too bad we aren't using a sorted list, or a HashSet

If only, if only we could have made a different choice there.

[Advertisement] Keep the plebs out of prod. Restrict NuGet feed privileges with ProGet. Learn more.

This post originally appeared on The Daily WTF.

Leave a Reply

Your email address will not be published.