0

I would like to have IDs of different sizes from the alphabet 0-9. So I have 5-length IDs as in 10000 or 13531, etc.. I have 10, 15, 20, up to 39 digit strings (the size of a UUID). I would like to guarantee that I select a random one from the set of possible values and that it has never been used before. This isn't the same as the solution of using UUIDs, which are so large as to be basically guaranteed unique without any check. The 100-digit strings might fit into that category.

But I would like to have let's say 15 digit strings, and select one random one from the set, and guarantee it is unique. How do I do that?

What I tried to do is generate even a small subset of possible values like this:

var fs = require('fs')

// var x = build(90000, 10000)
// fs.writeFileSync('5.csv', x.join('\n'), 'utf-8')

var x = build(10)
fs.writeFileSync('10.csv', x.join('\n'), 'utf-8')

function build(size) {
  var x = {}
  var total = 100000000
  while (total--) {
    var n = new Array(size)
    n[0] = randomIntFromInterval(1, 9)
    var i = 1
    while (i < size) {
      n[i++] = randomIntFromInterval(0, 9)
    }
    var s = n.join('')
    if (x[s]) {
      total++
    } else {
      x[s] = true
    }
  }
  return Object.keys(x)
}

function randomIntFromInterval(min, max) { // min and max included
  return Math.floor(Math.random() * (max - min + 1) + min);
}

function shuffle(a) {
    var j, x, i;
    for (i = a.length - 1; i > 0; i--) {
        j = Math.floor(Math.random() * (i + 1));
        x = a[i];
        a[i] = a[j];
        a[j] = x;
    }
    return a;
}

But that gets slower and slower as you add more IDs to the hash. I tried creating a very large array and shuffling them (containing all the values), but that only works for smaller strings as arrays can't be too large (over 4 billion-ish). I have also imagined just creating a sequenced list of all possible values, and somehow shuffling that, but I don't know how that would work (it would be shuffling file lines in chunks or something? I dunno). I also imagined creating a sort of trie, but that also seems to break down as once it got relatively full of already generated values, you would have to search a lot for empty space. Maybe you could have a full trie, and remove any value you use, then maybe that would improve lookup time? I can't really think of anything else. Randomly generating a string each time and then checking it against a database would only work when the set was small, because after there's only 1000 remaining values of 100000000000, randomly generating one you would have a high chance of generating one that was already used, so it would slow down as it got more used up, like my above example is doing.

How can I accomplish this better? Basically, I would like to use IDs in this pattern, and have them be randomized (or pseudo-randomized, so it appears roughly random).

5
  • 6
    In what context? In a corporate context, you don’t. Unique indexes are a solved problem, either use DB implementation, uuids, or some service like Snowflake that gives you blocks of IDs. – Telastyn Jul 27 '20 at 4:01
  • 2
    These are ridiculously different requirements. It doesn't make much sense to lump them together. Your last requirement would allow you to assign 100,000,000,000,000,000,000 unique IDs to every atom in the observable universe, and even still 100,000,000,000 unique IDs to every photon in the known universe. Whereas your first requirement is barely enough to assign an ID to each file in the node_modules directory of a typical Node.js starter project. Expecting a single solution for that entire range doesn't make sense. 100 digits is 334 bits, you could fit ~3 entire UUIDs into that range. – Jörg W Mittag Jul 27 '20 at 10:04
  • Fine, a 128 bit number UUID is roughly 39 characters when converted to a 10-digit alphabet. Let's say instead of 100 it's 39 characters in length (the size of a UUID) at a max. – Lance Pollard Jul 27 '20 at 14:21
  • 2
    The fact that you were willing to modify your requirements by a factor of 1000000000000000000000000000000000000000000000000000000000000000% or roughly 10000 times the number of atoms in our solar system based on a comment from a random idiot on the internet who doesn't even know your business case, seems to imply that the requirements were not well-thought-through in the first place, which, if I were in your shoes, I would consider a much more serious problem than how to implement those requirements. This needs to go back to your project manager and business analyst ASAP. – Jörg W Mittag Jul 28 '20 at 11:39
  • Sometimes, it pays to look at existing implementations and find the underlying design decisions. GUIDs are, as you say, "so large as to be basically guaranteed unique without any check". The main reason for that is because it's significantly easier to just use a bigger range than it is to check for factual uniqueness in a smaller range. The sheer cost of checking increases, as you've already found ("But that gets slower and slower as you add more IDs to the hash"). Your question comes across to me as trying to take a more difficult/performance-heavy route for no (given) justifiable reason. – Flater Jul 29 '20 at 8:46
6

Math

You are looking for a formula that allows you to traverse the entire symbol space without every repeating itself.

One such formula for modulo integers is x := x + 1. Seed x with any value and repetitive apply the formula.

I believe Group theory is what you want to investigate if you take this approach.

Book Keeping

Keep a list of every id you have ever generated (or considered reserved by your own definition).

Generate a number somehow, test it. In a large enough address space this will only hit a few duplicates before finding a unique address.

If the number generation is random, then you will need to ensure the random number generator will generate across the entire range.

You can alternately address this by generating a random number, testing it, and then performing a search to find the next/prior unallocated id.

0
1

You are presenting a weird combination of requirements. I am all with those who say "just don't". But if you must...

The best option seems to be to pre-generate all ids in the address space (or an ample subset that will be large enough for your purpose), shuffle it and store it in a file. Then take the ids from the file in a locked context, starting at either the start or the end, and keep track of the last used index.

1
  • 2
    The problem with finding any sort of "best option" is the ridiculously wide range of requirements from 5 digits to 100. The OP essentially wants a solution that works for 100000 IDs up to 100,000,000,000 unique IDs for every single photon in the observable universe. You could literally fit two UUIDs behind each other and would still have 90 bits left to play with, which is basically another 3/4 of a UUID. – Jörg W Mittag Jul 27 '20 at 10:09
0

Use Snowlake generator to generate Long ids': https://github.com/twitter-archive/snowflake

Just change the logic from a server based generation to a local VM based generation.

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.