What is the most efficient approach to compose a string of length N where random characters are selected from a-f, 0-9

Question

The requirement is to determine the most efficient approach to render a string, for example, "#1a2b3c", where "1a2b3c" are randomly selected from the set

"abcdef0123456789"

or

["a", "b", "c", "d", "e", "f", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]

---

For the uniformity of comparing results, the string .length should be precisely 7, as indicated at example above.

The number of iterations to determine resulting time of procedure should be 10000 as used in the code below.

---

We can commence the inquiry with two prospective examples and benchmarks. Benchmarks for the approaches should be included within the text of the Answer. Note, if more accurate benchmarks can be utilized, or text of Question can be improved, do advise at comment. Related: Can someone fluent in Javascript explain to me whats going on here SIMPLY.

function randColor() {
  return '#' + (function co(lor) {
    return (lor += [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f'][Math.floor(Math.random() * 16)]) &&
      (lor.length == 6) ? lor : co(lor);
  })('');
}

console.time("random string recursion");

for (let i = 0; i < 10000; i++) {
  randColor()
}

console.timeEnd("random string recursion");

console.time("random string regexp");

for (let i = 0; i < 10000; i++) {
  "xxxxxx".replace(/x/g, function() {
    return "abcdef0123456789".charAt(Math.floor(Math.random() * 16))
  });
}

console.timeEnd("random string regexp");

What is the most efficient, where efficiency is defined as the least amount of resource necessary for "speed" and "storage", to achieve returning a string of having .length of N?

Does the efficiency of speed and storage decrease as N increases?

Answer 1

An alternative approach, assuming that the characters are between [a-f0-9]. It's efficient both in speed and storage.

function randColor() {
  return '#' + (Math.floor(Math.random() * 16777216)).toString(16).padStart(6, '0');
}

console.time("random string hexa");

for (let i = 0; i < 10000; i++) {
  randColor()
}

console.timeEnd("random string hexa");

I compared its speed to the methods described in the question, using jsPerf. These are the results: https://jsperf.com/generating-hex-string-of-n-length

Answer 2

I managed:

function iter() {
return '#'+('000000'+Math.floor(Math.random()*16777216).toString(16)).slice(-6);
}

console.time('go');
for (let i=0;i++<10000;) iter();
console.timeEnd('go');
console.log(clr=iter());
document.body.style.backgroundColor=clr;

I'm not sure how this compares overall, it seems pretty fast. I'm not sure either whether the shorthand for-loop achieves anything.

Answer 3

Although the bottleneck in processing is often in the ALU, for such atomic operations like multiplication, the optimisions are done by the compiler at compile time. The only real difference between multiplication and the recursion method is the number of random numbers to be generated at the run time. The recursion method generates 6 random numbers while the multiplication method generates just one random number, so that is the real bottleneck step in this example.

function recc() {
  return '#' + (function co(lor) {
    return (lor += [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f'][Math.floor(Math.random() * 16)]) &&
      (lor.length == 6) ? lor : co(lor);
  })('');
}

console.time("random string recursion");

for (let i = 0; i < 100000; i++) {
  recc()
}

console.timeEnd("random string recursion");

function single_mult(len) {
  var max = 0;
  for (var i = 0; i < len; i++)
    max += 15 * Math.pow(16, i);

  return '#' + (Math.floor(Math.random() * max)).toString(16);
}

console.time("random string multiplication");

for (let i = 0; i < 100000; i++) {
  single_mult(6)
}

console.timeEnd("random string multiplication");

Other noticeable delays are the number of calls to a function. If you are able to avoid calling a function n times, by placing the loop inside the function, then the function will execute faster.

function loop_outside_function(){
  return Math.floor(Math.random() * 16777216).toString(16);
}

console.time('n function calls');
for (let i = 0; i < 100000; i++) {
  loop_outside_function();
}
console.timeEnd('n function calls');

console.time('loop inside function');
function loop_inside_function(){
  for (let i = 0; i < 100000; i++) {
    Math.floor(Math.random() * 16777216).toString(16);
  }
}
console.timeEnd('loop inside function');

---

Original Answer

Efficiency roughly translates to the number of clock cycles spent by the computer (in the ALU). So here is a sense of the cycles per operation:

• Multiplication: 5-6 cc
• Addition: 2 cc
• Division: 25 cc
• Subtraction: 2 cc
• If..else: Depends on number of else conditions. (1 cc for each else condition, but optimised by branch prediction)

The one provided initially involves six multiplications. A more efficient way to do this is by ncardeli's answer because, he reduces the multiplications to just one. You can make his algorithm a bit efficient by caching the length property. JonMark Perry's answer is essentially the same as ncardeli's answer, but he's hard coded the value to multiply for a given length and base.

function recc() {
  return '#' + (function co(lor) {
    return (lor += [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f'][Math.floor(Math.random() * 16)]) &&
      (lor.length == 6) ? lor : co(lor);
  })('');
}

console.time("random string recursion");

for (let i = 0; i < 100000; i++) {
  recc()
}

console.timeEnd("random string recursion");

function single_mult(len) {
  var max = 0;
  for (var i = 0; i < len; i++)
    max += 15 * Math.pow(16, i);

  return '#' + (Math.floor(Math.random() * max)).toString(16);
}

console.time("random string multiplication");

for (let i = 0; i < 100000; i++) {
  single_mult(6)
}

console.timeEnd("random string multiplication");

function get_length(len) {
  if (!get_length.cache) get_length.cache = {};
  if (get_length.cache[len] == null) {
    var max = 0;
    for (var i = 0; i < len; i++)
      max += 15 * Math.pow(16, i);
    get_length.cache[len] = max;
  }
  return get_length.cache[len];
}

function mult_with_cache(len) {
  let max = get_length(len)
  return '#' + (Math.floor(Math.random() * max)).toString(16);
}

console.time("random string Multiplication_cache");

for (let i = 0; i < 100000; i++) {
  mult_with_cache(6)
}

console.timeEnd("random string Multiplication_cache");

function iter() {
  for (let i = 0; i++ < 100000;) Math.floor(Math.random() * 16777216).toString(16);
}

function hard_coded(){
  return Math.floor(Math.random() * 16777216).toString(16);
}

console.time('hard coding values');
for (let i = 0; i < 100000; i++) {
  hard_coded();
}
console.timeEnd('hard coding values');

Benchmarks from different browsers:

                  Firefox     Chrome     Safari
Recursion          24.635     53.190     58.100
Mult                9.015     34.550     20.400
Mult_with_cache     8.950     32.105     19.500
HardCoded           6.340     29.610     16.500

Answer 4

I compared 3 different methods (and added the method from the original question as generate4). The algorithm does have a linear complexity, which means time of execution will grow in linear way relatively to the number of characters. Same can be said about memory usage.

So using your wording, efficiency of speed and memory indeed decreases as N increases, but in a linear way, which is very good.

Functions are here:

function generate1(n) {
    var str = '#';
    for (var i = 0; i < n; i++) {
        // <<0 is faster than Math.floor
        str += (Math.random()*16<<0).toString(16);
    }
    return str;
}

function generate2(n) {
    var str = '#';
    var arr = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];
    for (var i = 0; i < n; i++) {
        // <<0 is faster than Math.floor
        str += arr[Math.random()*16<<0];
    }
    return str;
}

function generate3(n) {
    var str = '';
    var temp = Math.ceil(n/6);
    for (var i = 0; i < temp; i++) {
        // <<0 is faster than Math.floor
        str += (Math.random()*0xFFFFFF<<0).toString(16); // 6 chars each
    }
    return '#' + str.substr(0, n);
}

function generate4(n) {
  return '#' + (function co(lor) {
    return (lor += [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f'][Math.floor(Math.random() * 16)]) &&
      (lor.length == n) ? lor : co(lor);
  })('');
}

This is created JSPerf: https://jsperf.com/generating-hex-strings

And below are the results:

Those results are clearly showing that choosing 1 method over the other may produce different results on different browsers. Although all the methods give the same algorithmical complexity, therefore I wouldn't worry about it too much.