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?

Ribald

"Does the efficiency of speed and storage decrease as N increases?" - I cannot imagine a solution that would be anyhow become faster or need less memory as it creates longer strings. – Hanschen

@Hanschen Then we can more conclusively define the rather potentially broad term of "efficiency" within the scope of the inquiry, and graph the comparisons of the resources needed for each approach. – Ribald

It's your inquiry now. Please edit the question if you think the definition needs improvement. – Hanschen

@Hanschen What needs to be edited at Question? What is not clear as to requirement? Which portion of OP can be improved? – Ribald

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

Zygo

Firefox 57 logs random string hexa: 30.01ms at 10000 iterations, Chromium 61 logs random string hexa: 23.75390625ms. For code at OP Firefox 57 logs random string recursion: 11.93ms, and as low as random string recursion: 10.02ms random string regexp: 32ms, Chromium 60 logs random string recursion: 23.130ms and random string regexp: 37.270ms – Ribald

I got better times in my pc with this algorithm. Maybe we could compare with jsperf? Could you create one and link to it in the question? Thanks! – Zygo

If you have a sense that jsperf, or another alternative for performing the tests, will provide different results, you can include the test results at your Answer. – Ribald

This does not work. randColor always needs to return a 7-character string. – Hanschen

The question doesn't say that the length of the string must be 7 characters. I think you should make that clear in the question. In any case, if it must be 7 characters long, I can simplify the algorithm, and improve the execution time. – Zygo

@Zygo "The question doesn't say that the length of the string must be 7 characters" See OP at "for example, "#1a2b3c"". "I updated my answer, simplifying the algorithm." Note, less than seven characters are still being returned by randColor() call – Ribald

I'm not the only one who interpeted that as just an example. But it's ok, I updated my answer. To avoid further misunderstandings I think it won't hurt if you update the question to clarify the length of the response you are expecting. – Zygo

@Zygo "to clarify the length of the response you are expecting." Is "for example, "#1a2b3c", where "1a2b3c" are randomly selected from the set" not clear? – Ribald

Sorry, but if that's important for the answer, no. My original algorithm could return the string of the example, but it failed in some other cases, so I consider that an example is not clear enough. – Zygo

@Zygo See updated post. Does the text of the Question now resolve any ambiguity as to expected result and parameters used to evaluate the time taken to return result? – Ribald

Because of the way random & floor works, it should be times 16777216. Otherwise, #ffffff would not be possible. – Southeast

Why does code set "0" at second argument to .padStart()? – Ribald

To pad with "0" until the string is 6 characters long. If no character is specified, padStart will pad with whitespace. – Zygo

@Zygo That would make the result not random if "0" is hard coded within the pattern, correct? Why do you not provide a random character at argument passed to .padStart()? – Ribald

The result is still random, the "0" is to format the random hexadecimal number so it will be 6 characters long, but that doesn't change the fact that the number resulting from (Math.floor(Math.random() * 16777216)).toString(16) is random. – Zygo

i tried to add another test case to yours, but that jsperf website was buggy as hell so it didn't work out, although my code which was basically rgb to hex didn't have as many ops/sec as the randColorHex() code so it was rather pointless anyway. flies away – Udelle

@Zygo The "0" is not random. You could alternatively call Math.random() of other method and pass the value to .padStart() to pad the string to .length of 6 – Ribald

My point is that the number generated by (Math.floor(Math.random() * 16777216)).toString(16) is already a random number between 0 and 0xFFFFFF. The zeros added are to make it have 6 characters long, but that doesn't change its randomness. If I do what you suggest, it won't be any more random. In fact, it will make the function return numbers lower than 0x100000 less frequently. – Zygo

Answer 2

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.

Pandora

The results are wildly different on firefox. Can anyone explain why? – Emulsion

The only explanation would be different JS engine. Chrome and Safari should be similar. IEs and FF are different story. – Pandora

I take it back - Chrome and Safari are not similar at all... Edited my answer and added screenshots of Safari and FF. No IE as I can only run it on VM which will most likely produce misleading numbers. – Pandora

Answer 3

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.

Cuman

This does not work. The string is asked to start with # and always be 7 characters long. – Hanschen

Answer 4

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

Emulsion

I don't think it makes sense to measure JS execution time in clock cycles, as it depends a great lot on the jit compiler and which optimisations it applies. Also the performance of the algorithm will largely depend on the Math.random() call(s) and the approach on string concatenation. – Hanschen

How else would you measure it? You generally tend to minimize time spent in the bottleneck step and thats almost always in the ALU. So I think clock cycles is a very effective measure of execution time – Emulsion

Yes, however a) you cannot read the cycle counter from JS b) you don't know how many cycles a JS operation takes - it doesn't directly translate to ALU ops. c) measuring in wall clock time is much easier, and that's what console.time does as well - it prints milliseconds. Also I'm pretty certain the bottleneck is memory and native function calls, not logic operations or even this trivial arithmetic (and if that multiplication code gets thrown into an optimising compiler, it will get eliminated by constant propagation anyway). – Hanschen

You are right about memory being the bottle neck here as, on Mark Perry's answer just removing the function calls made the code execute much faster than the others that were benchmark. But that's the incorrect way to measuring it, as the function is required to be called n times to determine how much more/less efficient it really is. – Emulsion

You mean you inlined the iter function in his code? Yes, that probably made everything much faster, as the compiler ate the dead code for breakfast. – Hanschen

@Hanschen Interesting. Should the efficiency also be measured using exactly one run of the procedure? – Ribald

Answer 5

trust but verify for the win:

function color(){
 var buff = "#" + Math.random().toString(16).slice(-7,-1);
 return buff[6] ? buff : color();
}

Regality

Why is return buff[6] ? buff : color() necessary? – Ribald

because a very few Math.randoms() will be too short as strings via omitted trailing zeros. if you can live with ~99.999999% success, you can omit the check for an even faster function. – Regality

@guest271314: why didn't this get the points? it's much faster than the one you gave +50 to... – Regality

Can you create a jsperf or other site which stores public code to demonstrate? For posterity and proof positive clarity can you also include all of the code at Answers at the Question, both for a single run of the code and multiple runs of the code? – Ribald

Just tried the approach at your Answer and Answer where bounty was awarded. Results at 10000 calls within for loop: randColor(): 14.96826171875ms, color(): 23.98291015625ms. For a single call your approach does appear to return results in least amount of time: 0.110107421875ms, 0.015869140625ms respectively. The time could probably be reduced by not using recursion when the call is made more than once, or less than the required .length of characters are returned? – Ribald

@guest271314: I tried to use jsperf but they got all scary about github signins, add it if you have perms, it might be useful to someone. weird that it's much faster individually but seemingly slower in a loop; there should not be many "fails" and thus recalls/recursions. Anyway, thanks for taking a look and forget what i said about the bounty if it's not a clear winner; w/o jsperf it seemed a lot faster... – Regality

Answer 6

For me following code worked best so far on all three browsers-

function getRandomColor(){
  return '#'+ (~~(Math.random()*(1<<24))).toString(16);
}

Following are the results Snapshots-

Please find test on jsperf.com here

Loveinidleness