Fastest way to generate a lot of unique small random numbers in JavaScript

Question

Wondering how to quickly generate lots of unique, small random numbers. When I implemented it like this it slows down exponentially it seems like, to the point where it never finishes, or will take hours to complete. Probably because it creates tons of duplicates toward the end.

var intsmap = {}
var intsarray = []
var i = 100000
while (i--) {
  var int = randominteger(6)
  if (intsmap[int]) i++
  else {
    intsmap[int] = true
    intsarray.push(int)
  }
}
// return intsarray

function randominteger(exp) {
  var string = rand(exp)
  return pad(string, exp)
}

function pad(num, size) {
  var s = rand(9) + num
  return s.substr(s.length - size)
}

function rand(exp) {
  var integer = Math.random() * Math.pow(10, exp) << 0
  var string = toString(integer, '0123456789')
  return string
}

function toString(value, code) {
  var digit
  var radix = code.length
  var result = ''

  do {
    digit = value % radix
    result = code[digit] + result
    value = Math.floor(value / radix)
  } while (value)

  return result
}

Wondering how to accomplish that but the code works within a few seconds if possible.

Update

• I would like for the set of numbers to be distributed evenly over an arbitrary range (in this example 1000000 strings, not necessarily from 0-1000000, eg maybe 5050000 is in there).
• I would like for the numbers to not necessarily be valid numbers, just a string of integers. So for example they can include 01010101 as a valid string, even though that's not a valid number.

Answer 1

You can use an object as a look up and only insert unique random number

var intsmap = {};
var i = 100000;
while (i--) {
  var int = Math.random() * Math.pow(10, 6) << 0;
  if(intsmap[int])
    continue;
  else
    intsmap[int] = true;
}

console.log(Object.keys(intsmap));

You can use also use Durstenfeld shuffle after generating number in the given range.

var arr = Array.from({length:1000000}, (_,i) => (i+1));

function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}
shuffleArray(arr);
console.log(arr);

Answer 2

Just try to shuffle the array of numbers 1 to maxNum

First create an array

var maxNum = 1000000;
var arr = Array(maxNum).fill().map((e,i)=>i+1);

Now shuffle the array

arr.sort(function() {
  return .5 - Math.random();
});

Now you have the array of unique random numbers

Demo

var startTime = new Date().getTime();

var maxNum = 1000000;
var arr = Array(maxNum).fill().map((e, i) => i + 1);

arr.sort(function() {
  return .5 - Math.random();
});

var endTime = new Date().getTime();
console.log( "Time taken to get " + maxNum + " size random unique number is " + ( endTime - startTime ) + " ms");

Answer 3

I can propose this approach:

• generate a random number
• cast it to a string (0.1234567812345678)
• and extract 6 substrings of length of 10

Code:

var res = {},
    s = "";
for (let i=0; i<1000000; ++i) {
    s = Math.random().toString();
    for (let j=0; j<6; ++j) {
        res[s.substring(2+j, 12+j)] = true; // extract 10 digits
    }
}

After 1,000,000 iterations, you have computed 6,000,000 numbers with very little collisions (1,800 in average). So you have your 1,000,000 numbers and more in few seconds.

Answer 4

 var acc = 0;
 const result = [];
 for(var i = 0; i < 100000; i++)
   result.push(acc += Math.floor(Math.random() * 10) + 1);

I think the most expensive operation is the hashtable lookup/insertion, so simply do it without it.

Answer 5

If you need unique big array try to think in other way. Just create range 0 ... 100000 and shuffle it and apply you function that you need for this array.

Answer 6

One place where you might loose performances is in the Math.random call.
It's a quite expensive call, and you are calling it a huge number of times to generate your strings.

One solution to leverage it is to grab the whole string from a single result of Math.random().

var intsmap = {}
var intsarray = []
var i = 100000

while (i--) {
  var int = randominteger(6)
  if (intsmap[int]) {
    i++
  } else {
    intsmap[int] = true
    intsarray.push(int)
  }
}

console.log(intsarray);

// It takes the whole string from a single call to 'random'.
// The maximum length is 16.
function randominteger(length){
  return (Math.random() + '').substr(2,length);
}