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

Question:

I'm creating an algorithm in JavaScript, and I'm already finding it too cumbersome. Now I need a string "multiplied" N times. I would like to know 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 executed several times in the program, it is important that it is more optimized, if possible.

Answer:

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

See the example:

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

As indicated by friend @LeoCaracciolo it doesn't work in Internet Explorer (as you would expect). If you need specific compatibility for this version you can use the polyfill that is on the documentation page.

performance

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

In fact, repeat is much more efficient, although it is only noticed for large amounts of repetitions. So if we analyze the two side by side for 5 repetitions for example, the execution time is basically the same:

Comparing for 5 reps :

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 ran it, the normal concatenation code was 3% faster.

See this test on 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 reps :

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

See these results also on jsben

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

This same test in jsperf gives identical results with description of how many times it was run. On my machine I got:

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 is it possible that it is so much? It has to do with the algorithm itself.

Algorithm

Contrary to what we might think, the basic algorithm for repeat is not concatenating word by word until the desired result is formed, in which this would have a complexity of O(N) with N being the number of repetitions.

The solution used has O(log2(n)) complexity, 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 concatenate the word to the result
  • In each step it discards the ultimo bit of the repetitions variable and "doubles" the word. If the word was "palavra " , it becomes "palavra palavra"

This logic makes it need much less concatenations, as the word being concatenated increases.

Confused ? A running example 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 doubled twice, leaving "palavra palavra palavra palavra " and only at the end it was concatenated again with the resultado forming the intended 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

Conclusion

Whenever you have native functions that do what you want, you should use them because not only are they much shorter in terms of code extension, but they can be much more performant, due to using algorithms that you can't even imagine!

Post Views: 4
Scroll to Top