Change random methods without losing too much performance

Question

I have a class in C# that uses a Random object to get a list of numbers randomized from an array of 1-25. Now what I need is improve this method to use RNGCryptoServiceProvider because it is not random enough for the application.

I know that RNGCryptoServiceProvider is slower than Random, but I need to change it and I don't know anything about this class. How big should the Buffer storage be so as to not slow down the client PC too much?

What I'm passing to the method is this array:

string[] num25 = { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25" };

This is the actual code:

public static class RandomStringArrayTool
{
 /// <summary>
 /// Stores the current random number
 /// </summary>
 static Random _random = new Random();
 /// <summary>
 /// Return randomized version of the string array
 /// </summary>
 public static string[] RandomizeStrings(string[] arr)
 {
 List<KeyValuePair<int, string>> list = new List<KeyValuePair<int, string>>();
 // Add all strings from array
 // Add new random int each time
 foreach (string s in arr)
 {
 list.Add(new KeyValuePair<int, string>(_random.Next(), s));
 }
 // Sort the list by the random number
 var sorted = from item in list
 orderby item.Key
 select item;
 // Allocate new string array
 string[] result = new string[arr.Length];
 // Copy values to array
 int index = 0;
 foreach (KeyValuePair<int, string> pair in sorted)
 {
 result[index] = pair.Value;
 index++;
 }
 // Return copied array
 return result;
 }
}

• Magus: What exactly isn't random enough about Random?
• Phoenix_uy: This is a raffle application, that's why i need something better than Random object.
• Magus: Do you mean you want an even distribution (less random)?
• Phoenix_uy: No.. i want a most random.
• rolfl: I have rolled back the edit you made which adds your 'revised' code. Please read what you can and cannot do after receiving answers

Answer 1

First of all, you should shuffle the array instead of sorting it on a random number. There can be duplicates in the random numbers, which means that lower numbers would end up earlier in the array slightly more often. This is naturally a small difference as the random numbers are large, but as you want to avoid any predictable pattern, it is still important.

Look at the Fisher-Yates algorithm for shuffling the values in an array.

To use the crypto random generator, you need a way to transform the bytes that it returns into a number in a specific range. You can use a method like the following to get a number in a range with the same probability for all numbers in the range (limited only by the randomness of the generator). It calculates the largest range of numbers that can be used to create a number in the desired range, then loops until it has picked a number in that range.

public static int GetInt(RNGCryptoServiceProvider rnd, int max) {
 byte[] r = new byte[4];
 int value;
 do {
 rnd.GetBytes(r);
 value = BitConverter.ToInt32(r, 0) & Int32.MaxValue;
 } while (value >= max * (Int32.MaxValue / max));
 return value % max;
}

This is based on the example on documentation page for the GetBytes method, but adapted for larger numbers.

On my computer the function will generate a million random numbers in 450 ms. The Random class does it in 20 ms, so it's slower, but not very slow. Shuffling on the other hand is faster than sorting, so you will get some performance back there.

Answer 2

I finally ended up with this approach:

public static class RandomStringArrayTool
{
 public static void RandomizeStrings<T>(T[] array)
 {
 using (var cryptoServiceProvider = new RNGCryptoServiceProvider())
 {
 for (int i = array.Length; i > 1; i--)
 {
 // Pick random element to swap.
 int j = GetInt(cryptoServiceProvider, i); // 0 <= j <= i-1
 // Swap.
 T tmp = array[j];
 array[j] = array[i - 1];
 array[i - 1] = tmp;
 }
 }
 }
 public static int GetInt(RNGCryptoServiceProvider rnd, int max)
 {
 byte[] r = new byte[4];
 int value;
 do
 {
 rnd.GetBytes(r);
 value = BitConverter.ToInt32(r, 0) & Int32.MaxValue;
 } while (value >= max * (Int32.MaxValue / max));
 return value % max;
 }
}

• Malachi: please read point 3 of This Meta Answer carefully it explains about what you should do with a self answer like this