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

4

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 retry.

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 run several times in the program, it is important to be more optimized if possible.

    
asked by anonymous 08.06.2018 / 02:24

2 answers

6

Yes, you can use the repeat method. of string , 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 the friend @LeoCaracciolo does not work in Internet Explorer (as you would expect). If you need specific compatibility for this release you can use polyfill that is on the documentation .

Performance

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

In fact, repeat is much more efficient, although only 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 to 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 in the time I ran, the normal concatenation code was 3% faster.

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 reps :

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

See these results also in jsben

Here you see a very large difference in the execution of the two.

This same test in jsperf gives identical results with a description of how many times it has 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 could it be that much? It has to do with the algorithm itself.

Algorithm

Contrary to what we might think, the base algorithm for repeat is not to concatenate word by word until it has the desired result, in which it would have a complexity of O(N) being N 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 concatenates the word to the result
  • At each step it drops the ultimo bit of the repeats variable and "doubles" the word. If the word was "palavra " , it becomes "palavra palavra"

This logic causes you to need far fewer concatenations because the word being concatenated is increasing.

Confused? An example 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 doubled twice, getting "palavra palavra palavra palavra " and only at the end it was concatenated again with 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

Conclusion

Whenever you have native functions that do what you want you should use them because not only are they much shorter in code extension, but they can be much more performative due to algorithms you can not even imagine! / p>     

08.06.2018 / 02:28
0

There was no doubt about what would be que seja mais otimizado .

  

Could it be in the meaning of the context below?

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

  

To do so, simply 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(); 
    
08.06.2018 / 03:30