C# Random Number

Question

I am working on a project in which I need to generate 8 random numbers. I am having an issue with the random number part being very time consuming for some reason. What I mean by 8 random numbers is I need a string that is 8 characters long consisting of the numbers 0-9. Example 01234567 or 23716253 etc.

I tried looping 8 times generating a random number with Random.Next(0, 9) and just turning them to a string and concatenating them to the final string. I also tried generating a random number using Random.Next(0, 99999999) and just converting the number to a string and padding it to 8 with 0's.

It seems like both are pretty slow and I need to come up with a faster way. I dont mind making calls to other languages or somthing either if it will help performance.

Here is some extra info to add. I dont think im going to find anything super efficient. I have to generate this number about 50000 times. When I ran a test with 47000 it took 8:39 seconds. This is only like .011 seconds each time but it was just slowing thins down because im also working with a has table. I also called hashtable.ContainsKey() all 47000 times and it only took a total of 58 seconds. It just is such a big difference.

Here is the code I origanally used. Convert.ToString(rg.Next(0, 99999999)).PadLeft(8, '0');

Here is some code to try to figure this out. Here are the times that I get Contains Value: 00:00:00.4287102 Contains Key: 00:01:12.2539062 Generate Key: 00:08:24.2832039 Add: 00:00:00

        TimeSpan containsValue = new TimeSpan();
        TimeSpan containsKey = new TimeSpan();
        TimeSpan generateCode = new TimeSpan();
        TimeSpan addCode = new TimeSpan();

        StreamReader sr = new StreamReader(txtDictionaryFile.Text);
        string curWord = sr.ReadLine().ToUpper();
        int i = 1;
        DateTime start;
        DateTime end;
        while (!sr.EndOfStream)
        {
            start = DateTime.Now;
            bool exists = mCodeBook.ContainsValue(curWord);
            end = DateTime.Now;
            containsValue += end - start;
            if (!exists)
            {
                string newCode;
                bool kExists;
                do
                {
                    start = DateTime.Now;
                    Random rnd = new Random(); 
                    StringBuilder builder = new StringBuilder(8); 
                    byte[] b = new byte[8]; 
                    rnd.NextBytes(b); 
                    for (int i = 0; i < 8; i++) 
                    { 
                        builder.Append((char)((b[i] % 10) + 48)); 
                    } 
                    newCode = builder.ToString();
                    end = DateTime.Now;
                    generateCode += end - start;

                    start = DateTime.Now;
                    kExists = mCodeBook.ContainsKey(newCode);
                    end = DateTime.Now;

                    containsKey += end - start;
                }
                while (kExists);

                start = DateTime.Now;
                mCodeBook.Add(newCode, curWord);
                end = DateTime.Now;

                addCode += start - end;
            }
            i++;
            curWord = sr.ReadLine().ToUpper();
        }

Answer 1

It's unlikely that the actual problem you are seeing is is that the random number generation is slow, but rather that you are executing it very frequently. As the number of items in your "code book" grows, the probability of a collision on an existing number also increases. This will cause your do...while loop to keep executing over and over again until it finds something that is available.

I don't know how much data you are loading into the code book, but you if it is at all large, you need to think about what will happen with duplicate entries.

In your case, the issue is made dramatically worse because you are calling "new Random()" inside the loop. This causes the random number generator to be "reseeded" with a value derived from the current time (actually the total number of milliseconds since the system booted). That means that any time you do have a collision, the loop will immediately re-execute and will choose exactly the same random seed value as it had before, which will in cause the "random" number that you generate to also match the previously tried number. In fact, depending on the speed of your machine, it may generate the same number over and over again repeatedly.

The quickest workaround for this issue that fits with the structure of your current code would be to simply remove all of the places where you are calling "new Random" and have a single random number generator at the beginning of the method that you reuse. This will ensure that it is not reset every time you go through the loop and lower the likelyhood of repeatedly generating the same number.

To really fix this though, you are going to have to do some more thinking about the random numbers you are using. Is it really important that the numbers you generate are random or do they just need to be unique. In addition, you can generate larger random numbers to decrease the probability of any duplicates. A sufficiently large random number will all but eliminate the chance of duplication. The extreme of this would be to use Guid.NewGuid().ToString() to generate keys

Also, as a side note. The performance numbers that you are showing are likely not measuring what is going on very accurately. DateTime.Now doesn't have sufficient "resolution" to be useful for measuring things as small and fast as what you are using it for. Many times, the entire time spent inside of the tested code will be smaller than the resolution of DateTime.Now which will result in the measured time for that test being zero.

For example, when I run the following test on my machine:

#define StopTime
using System;
using System.Diagnostics;

class C
{
  static void Main() {
    Random rg = new Random();
#if StopTime
    Stopwatch stopTime = new Stopwatch();
#else
    TimeSpan time = TimeSpan.Zero;
#endif
    for(int i=0;i<1000000;++i) {
#if StopTime
      stopTime.Start();
#else
      DateTime start = DateTime.Now;
#endif
      Convert.ToString(rg.Next(0, 99999999)).PadLeft(8, '0');
#if StopTime
      stopTime.Stop();
#else
      DateTime end = DateTime.Now;
      time += end - start;
#endif
    }
#if StopTime
    Console.WriteLine(stopTime.Elapsed);
#else
    Console.WriteLine(time);
#endif
  }
}

The measured time using the DateTime.Now approach (00:00:00.7680442) is about half the time measured with the high-resolution Stopwatch (00:00:01.6195441)

Answer 2

Neither of the things you said you've tried should be "slow". Perhaps posting some code would help us help you find what's wrong. Also, what's the acceptance criteria for slow?

One thing it seems you have not tried is to call Random.Next in a way that will guarantee the number returned is 8 'chars' long: Random.Next(10000000, 100000000).