2
\$\begingroup\$

Objective

To create a unique id with few characters as possible.

  • Language: C#
  • Engine Unity3D
  • Target : iOS && iPadOS

Scenario

I found quite a few solutions from Stack Exchange but would like to know if someone could just look at my code to review it. It is a very important module IMO

Code

    /// <summary>
    /// Identifiers the generation.
    /// </summary>
    /// <returns>A Unique ID</returns>
    private string generateUniqueID(int _characterLength = 11)
    {
        StringBuilder _builder = new StringBuilder();
        Enumerable
            .Range(65, 26)
            .Select(e => ((char)e).ToString())
            .Concat(Enumerable.Range(97, 26).Select(e => ((char)e).ToString()))
            .Concat(Enumerable.Range(0, 10).Select(e => e.ToString()))
            .OrderBy(e => Guid.NewGuid())
            .Take(_characterLength)
            .ToList().ForEach(e => _builder.Append(e));
        return _builder.ToString();
    }

In the above code, I always pass _characterLength to be always 11.

Request

  1. Would you recommend the above method? If not, could you please specify why?
\$\endgroup\$
  • \$\begingroup\$ I would probably just use System.Guid.NewGuid().ToString().Substring(0, _characterLength); Is there some reason you're specifically using uppercase strings instead of just a Guid directly? This is what they're for after all. \$\endgroup\$ – Turksarama Dec 5 '19 at 4:04
  • \$\begingroup\$ How often would you create an ID, and what is the scope (i.e. how broadly are they going to be used)? If you are going to make one every hour, then using a dated timestamp would guarantee uniqueness! After all, unique does not have to be random. \$\endgroup\$ – AJD Dec 5 '19 at 5:49
  • 3
    \$\begingroup\$ This does not generate a unique ID, it generates a random ID \$\endgroup\$ – Anders Dec 5 '19 at 8:27
  • \$\begingroup\$ Thank you for the comments. Based on the response from @Turksarama && @Anders | if I just use return Guid.NewGuid().ToString().Substring(0, 9); 1. Would that be good. 2. What are the chances of not getting a unique string? \$\endgroup\$ – karsnen Dec 5 '19 at 8:39
  • 1
    \$\begingroup\$ @karsnen Guids are significantly more unique than your algorithm. You are limiting uniqueness both by length and by not allowing repeating characters. Note that I wouldn't even use substring ideally (I don't know why you're limiting length). Just use Guid.NewGuid() and be done with it. \$\endgroup\$ – Turksarama Dec 5 '19 at 9:10
4
\$\begingroup\$
    /// <summary>
    /// Identifiers the generation.
    /// </summary>
    /// <returns>A Unique ID</returns>
    private string generateUniqueID(int _characterLength = 11)

A good summary should describe what the method does. This summary doesn't really tell me anything. Keep it simple: the method generates IDs, so write the summary as such.

generateUniqueID does not follow C# method naming conventions. Call it GenerateUniqueID. Note the PascalCase.

A character always has a length of 1, so _characterLength is a bit of a confusing name for me. What it describes is actually the length of the ID, so call it idLength, or just length since the thing it's describing is obvious from the method name anyway.

You got the camelCasing right for parameter and local identifiers, but it's not conventional to use underscores. Get rid of those.

It's not clear why you'd give such a method a default value, but in any case that 11 should be defined as a constant somewhere. Avoid magic numbers. By giving that number a name, you give it a meaning that's obvious to the next person who reads your code.

private const int DefaultIDLength = 11;

private string GenerateUniqueID(int length = DefaultIDLength)
...

StringBuilder _builder = new StringBuilder();

It's common to use var when the expression type is obvious.

Your ID will always be length characters long, so use the StringBuilder constructor that takes an initial capacity:

var builder = new StringBuilder(length);

Enumerable
            .Range(65, 26)
            .Select(e => ((char)e).ToString())
            .Concat(Enumerable.Range(97, 26).Select(e => ((char)e).ToString()))
            .Concat(Enumerable.Range(0, 10).Select(e => e.ToString()))
            .OrderBy(e => Guid.NewGuid())
            .Take(_characterLength)
            .ToList().ForEach(e => _builder.Append(e));

This is the crux of your implementation, and there's a lot to unpack here, so let's go step by step.

Enumerable
            .Range(65, 26)
            .Select(e => ((char)e).ToString())
            .Concat(Enumerable.Range(97, 26).Select(e => ((char)e).ToString()))
            .Concat(Enumerable.Range(0, 10).Select(e => e.ToString()))

This produces the same sequence every time you run it. It's painful to read. Why not just specify it as a constant? This gets the point across far easier:

private const string AllowableIDCharacters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

But we'll see later that none of this is necessary.

You don't need all those ToStrings everywhere. You gain nothing by using string as an intermediate representation instead of char. Keep them as chars during the shuffle: StringBuilder.Append() has an overload that accepts char.

I try to avoid writing lambdas with side effects. This would be more conventionally written as a foreach loop, which also avoids the need to convert the thing to a list:

foreach (char c in AllowableIDCharacters
            .OrderBy(e => Guid.NewGuid())
            .Take(length))
{
    builder.Append(c);
}

But by far the biggest problem here is your source of entropy, as Turksarama pointed out in the comments. By shuffling the alphabet, you are not allowing any repeated characters! This cuts down the number of unique IDs you can generate by more than half. Drop the shuffling idea entirely, it's not the best tool for this job.


You cannot generate unique IDs without keeping some kind of state. GUIDs work by generating sequences that, while not unique in a pure sense, are so astronomically unlikely to be repeated that they are "unique" for all practical intents and purposes.

If you embrace the non-determinism approach of generating unique IDs that GUID takes, then the question is no longer "how to generate a unique ID with as few characters as possible". It is now "what is an acceptable trade-off between ID length and probability of collision".

Because your method is just a mechanism for generating IDs given a length, then half of your problem reduces to something much simpler:

  1. Given an ID length n, how do I minimize the probability of a collision?
  2. How do I maximize the amount of information contained within a string of length n?

Both of these are straightforward problems. To minimize collisions you need a source of entropy that is both uniformly distributed and unpredictable. There are a lot of ways to do this, with varying degrees of uniformity and unpredictability, but do note that GUIDs are not uniformly distributed, are somewhat predictable, and are therefore not a great choice here. There is plenty of literature on how to generate such entropy so I won't go into detail for now. A common choice in .NET is to use RNGCryptoServiceProvider.

Maximizing the information contained in the ID means trying to squeeze as many bits of data as possible into that string. You chose an encoding that can represent 62 different things per character, or about 5.95 bits of data per character -- but because of the shuffling issue we talked about earlier, the actual number will be much smaller. For IDs of length 11 it's less than half.

I assume you're limited to ID strings of 8-bit ASCII-ish characters. But the alphabet you came up with is really close to Base 64, so why not just use Base 64? That'll give you an even 6 bits of information per character. By selecting a standard encoding as such, you'll avail to yourself a suite of standard tools for converting to and from that encoding.


Here's an example of how you could do it:

private static readonly RNGCryptoServiceProvider random = new RNGCryptoServiceProvider();

private string GenerateUniqueID(int length)
{
    // We chose an encoding that fits 6 bits into every character,
    // so we can fit length*6 bits in total.
    // Each byte is 8 bits, so...
    int sufficientBufferSizeInBytes = (length * 6 + 7) / 8;

    var buffer = new byte[sufficientBufferSizeInBytes];
    random.GetBytes(buffer);
    return Convert.ToBase64String(buffer).Substring(0, length);
}

This gives you 6 bits of entropy per character. It's up to you and the constraints of your business domain to pick an appropriate length. By the "birthday problem" rule of thumb, the probability of two random IDs of n bits to conflict with each other is about one in 2^(n/2); so an ID length of 11 gives you 66 bits, with a one in 2^33 chance of two IDs conflicting.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for the answer. Besides the solution and how to approach the problem - I also learned about naming conventions & how to document. Have a great day. \$\endgroup\$ – karsnen Dec 8 '19 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.