Is there a more optimized way to "multiply" a string without using repetition?

Question

I’m creating an algorithm in Javascript, and I’m already finding it very heavy. Now I need a string "multiplied" N times. I wonder if it is possible to do this without using a repeat.

For example, for the algorithm to return "word " 5x in a single string:

var str = "palavra "
i = 0
j = 3;

while ( i < j){
    str = str+"palavra ";
    i++
}
return str
// o script retorna "palavra palavra palavra palavra palavra"

This type of algorithm will be run several times in the program, it is important that it is more optimized if possible.

Answer 1

Yes, you can use the method repeat of string, which takes as a parameter the amount of times to repeat.

Take the example:

var str = "palavra ";
console.log(str.repeat(5));

As indicated by the friend @Leocaracciolo does not work in Internet Explorer (as you would expect). If you need specific compatibility for this version you can use the polyfill which is on the page of documentation.

Performance

We already know that .repeat() is much shorter, but will the performance is different in terms of execution speed ?

It is indeed, the repeat is much more efficient, although it is only noted for large amounts of repetitions. So if we analyze both side by side for 5 repetitions for example, the running time is basically the same:

Comparing for 5 repetitions:

Código 1 - `repeat`                      |  Código 2 - concatenação

var resultado = str.repeat(repeticoes);  |  var resultado = "";
                                         |  for (var i = 0; i < repeticoes; ++i){
                                         |      resultado += str;
                                         |  }
------------------------------------------------------------------------------------------
Resultado: 100%                          |  Resultado 97%

Here you can see that the time I executed, the normal concatenation code was faster 3%.

See this test in jsben
_{Each test may vary slightly, so it is advisable to run the test a few times to get a more realistic idea of the comparison}

Comparing to 5000 repetitions:

Código 1 - `repeat`                      |  Código 2 - concatenação
------------------------------------------------------------------------------------------
Resultado: 1%                            |  Resultado 100%

See these results also in jsben

Here you already see a big difference in the execution of the two.

This same test in jsperf gives identical results with description of how many times you have executed. On my machine I obtained:

Código 1 - `repeat`                        |  Código 2 - concatenação
------------------------------------------------------------------------------------------
Resultado: 0%                              |  Resultado 100% mais lento
Execuções: 2,951,175                       |  Execuções: 12,281

When we look at the number of executions we see that it is an abysmal difference. How can it be so much ? It has to do with the algorithm itself.

Algorithm

Contrary to what we might think, the basic algorithm for the repeat is not to concatenate word by word until it forms the intended result, in which it would have a complexity of O(N) being the N the number of repetitions.

The solution used has complexity O(log2(n)), which can be described as follows:

• Only the last bit of the variable that has the number of repetitions is interpreted
• When the last bit is 1 concatenates the word to the result
• At each step discards the ultimo bit of the variable repetitions and "fold" the word. If the word was "palavra ", becomes "palavra palavra"

This logic makes it much less concatenative, because the word being concatenated is increasing.

Confusing ? An example of execution for "palavra ", 5 would be:

        | num(bin) | str                                | resultado  | ação
inicio  | 5(101)   | "palavra "                         |  ""        |   
passo 1 | 5(101)   | "palavra "                         | "palavra " | concatena, descarta o `1` dobra `str`
passo 2 | 2(10)    | "palavra palavra "                 | "palavra " | não concatena, descarta o `0` e dobra `str`
passo 3 | 1(1)     | "palavra palavra palavra palavra " | "palavra " | concatena, descarta o único bit, e dobra `str`
final   | 0(0)     |  ...                               | "palavra palavra palavra palavra palavra "

In this small example of execution the word was concatenated once at the beginning, then it was folded twice, leaving "palavra palavra palavra palavra " and only in the end was it concatenated again with the resultado forming the desired result.

Implementation:

function stringRepeat(str, num) {
  num = Number(num);

  var result = '';
  while (true) {
    if (num & 1) {
      result += str;
    }
    num >>>= 1;
    if (num <= 0) break;
    str += str;
  }

  return result;
}

console.log(stringRepeat("palavra ", 5));

Source of this code

Completion

Whenever you have native functions that do what you want you should use them because not only are they much shorter at the code extension level, they can be much more performative, because they use algorithms that you can’t even imagine!

Answer 2

Left to doubt what it would be que seja mais otimizado.

It would be perhaps in the meaning of the context below?

Why otimizar our Sites is so important? Simply because no user likes to waste time waiting for pages to load. It is extremely annoying.

To do so, just run the examples below and draw your own conclusions

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

function repeat(s,n) { return Array(n+1).join(s); }

var t = timer('Benchmark'); // <-- START BENCHMARK
for(var i = 0; i < 1000000; i++)
repeat("boo", 40);
t.stop();  // <-- STOP BENCHMARK

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

var repeat = function(str, count) {
    var array = [];
    for(var i = 0; i <= count;)
        array[i++] = str;
    return array.join('');
}

var t = timer('Benchmark'); 
for(var i = 0; i < 1000000; i++)
repeat("boo", 40);
t.stop();