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