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

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).

Answer 2

This should be quite efficient. It allocates a buffer of eight characters and adds characters to it. There is no extra step of turning each digit into a string and concatenating the strings, the characters are placed directly in the buffer. Then the buffer is returned in the form of a string, so there is no extra step of creating a string from the buffer either:

StringBuilder builder = new StringBuilder(8);
for (int i = 0; i < 8; i++) {
   builder.Append((char)rnd.Next(48,58));
}
string code = builder.ToString();

Turning a single random number into a string has the advantage of only calling the random generator once. You can make it faster by doing the conversion into a string yourself:

StringBuilder builder = new StringBuilder(8);
int num = rnd.Next(0, 100000000);
for (int i = 0; i < 8; i++) {
   builder.Append((char)((num % 10) + 48));
   num /= 10;
}
string code = builder.ToString();

(Note that the second parameter to the Next method is not inclusive, so it should be 100000000 rather than 99999999. The number is actually rendered backwards into the string this way, but that doesn't matter as it's a random number.)

Answer 3

Similar to Guffa's answer, but perhaps faster on a nanoscale level since it avoid "costly" division.

        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));
        }
        string code = builder.ToString();

Answer 4

It's likely in the scenario you describe that string operations are taking up as much or more time than the calls to Random.Next(). I have not tested the libraries, but converting the binary random-number to a decimal string is likely to be much slower than generating it. When you generate the string character-by-character this is even more likely to be the case.

So consider retaining the number as an int if possible, and then converting only for display purposes.

Answer 5

Well, I decided to try to beat Guffa :) I suspected his version had too much indirection. So, here's a variant on his solution, which uses a character array instead of a stringbuilder. It runs in about 70% of the time of his faster solution, when I benchmarked it via Stopwatch.

char[] fauxbuilder = new char[8];
int num = rnd.Next(0, 100000000);
for (int i = 0; i < 8; i++)
{
    fauxbuilder[i] = (char)((num % 10) + 48);
    num /= 10;
}
string code = new string(fauxbuilder);

Answer 6

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 7

As an aside, I just ran a test on my machine of the relative speeds of the approaches mentioned.

On my machine, this gives the following times:

Testing: Guffa1
00:00:05.2472507
Testing: Guffa2
00:00:03.6620228
Testing: Simple
00:00:03.7890637
Testing: Brian
00:00:01.8473002
Testing: JohnDagg
00:00:03.8853139
Testing: chsh
00:00:05.9960557

The only approach that seems to really help is to skip over the StringBuilder and work directly from a character buffer

Code follows:

using System;
using System.Text;
using System.Diagnostics;

class C
{
  const int IterationCount = 10000000;

  static void Main() {
    Test("Guffa1", Guffa1);
    Test("Guffa2", Guffa2);
    Test("Simple", Simple);
    Test("Brian", Brian);
    Test("JohnDagg", JohnDagg);
    Test("chsh", chsh);
  }

  delegate string TestDelegate(Random rg);

  private static void Test(string name, TestDelegate testMethod) {
    Console.WriteLine("Testing: " + name);
    Random rg = new Random(0);//Start each test with the same random seed

    //Call the method once outside of the test to make sure the JIT has run etc.
    for(int i=0;i<1000000;++i) {
      testMethod(rg);
    }
    Stopwatch timer = new Stopwatch();
    timer.Start();
    for(int i=0;i<IterationCount;++i) {
      testMethod(rg);
    }
    timer.Stop();
    Console.WriteLine(timer.Elapsed);
  }

  private static string Simple(Random rg) {
    return Convert.ToString(rg.Next(0, 99999999)).PadLeft(8, '0');
  }

  private static string Brian(Random rg) {
    char[] fauxbuilder = new char[8];
    int num = rg.Next(0, 100000000);
    for (int i = 0; i < 8; i++) {
      fauxbuilder[i] = (char)((num % 10) + 48);
      num /= 10;
    }
    return new string(fauxbuilder);
  }

  private static string Guffa1(Random rg) {
    StringBuilder builder = new StringBuilder(8);
    for (int i = 0; i < 8; i++) {
      builder.Append((char)rg.Next(48,58));
    }
    return builder.ToString();
  }

  private static string Guffa2(Random rg) { 
    StringBuilder builder = new StringBuilder(8);
    int num = rg.Next(0, 100000000);
    for (int i = 0; i < 8; i++) {
      builder.Append((char)((num % 10) + 48));
      num /= 10;
    }
    return builder.ToString();
  }

  private static string JohnDagg(Random rg) {
    StringBuilder builder = new StringBuilder(8);
    byte[] b = new byte[8];
    rg.NextBytes(b);
    for (int i = 0; i < 8; i++) {
      builder.Append((char)((b[i] % 10) + 48));
    }
    return builder.ToString();
  }

  private static string chsh(Random rg) {
    return (
      NextSpecial(rg, 10000000) +
      NextSpecial(rg, 1000000) +
      NextSpecial(rg, 100000) +
      NextSpecial(rg, 10000) +
      NextSpecial(rg, 1000) +
      NextSpecial(rg, 100) +
      NextSpecial(rg, 10) +
      NextSpecial(rg, 1))
      .ToString().PadLeft(8,'0');
  }

  static int NextSpecial(Random rg, int multiplier) {
    return rg.Next(0, 10) * multiplier;
  }   
}

Answer 8

This code is what I hacked together as a solution and has no real optimization (other than initializing the list to the known size). On my system over repeated tests it was sub-1 second. I have it write out the file at the end for quality control purposes. It seems like it generates what you're looking for, but feel free to point out any flaws.

    static Random rand = new Random();

    static int NextSpecial(this Random r, int multiplier)
    {
        return r.Next(0, 10) * multiplier;
    }

    static string randomString()
    {
        return (rand.NextSpecial(10000000) +
               rand.NextSpecial(1000000) +
               rand.NextSpecial(100000) +
               rand.NextSpecial(10000) +
               rand.NextSpecial(1000) +
               rand.NextSpecial(100) +
               rand.NextSpecial(10) +
               rand.NextSpecial(1))
               .ToString().PadLeft(8,'0');
    }

    static void Main()
    {
        int MAXITEMS = 1000000;
        IList<string> numbers = new List<string>(MAXITEMS);
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < MAXITEMS; i++)
        {
            numbers.Add(randomString());
        }
        sw.Stop();

        Console.WriteLine("{0} iterations took: {1}", MAXITEMS.ToString(), sw.Elapsed);

        File.WriteAllLines(@"c:\test.txt", numbers.ToArray());
        Console.ReadLine();
    }

Answer 9

Looking at your original code:

You're creating a new random number generator in each loop. Create it once and keep calling the .Next() function it that.