4

Estou criando um algoritmo em JavaScript, e já estou achando ele muito pesado. Agora preciso de uma string "multiplicada" N vezes. Gostaria de saber se é possível fazer isso sem usar uma repetição.

Por exemplo, para o algoritmo retornar "palavra " 5x em uma única 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"

Esse tipo de algoritmo irá ser executada diversas vezes no programa, é importante que seja mais otimizado, se possível.

2
  • 1
    Por definição não tem como, o que pode ser feito é usar uma função que faça isto por você, conforme a resposta do Isac mostra.
    – Maniero
    Commented 8/06/2018 às 0:54
  • Que seria mais otimizado?
    – user60252
    Commented 8/06/2018 às 0:58

2 Respostas 2

8

Sim, pode usar o método repeat de string, que recebe como parâmetro a quantidade de vezes a repetir.

Veja o exemplo:

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

Assim como indicado pelo amigo @LeoCaracciolo não funciona no Internet Explorer (como já seria de esperar). Se precisar de compatibilidade especifica para essa versão pode usar o polyfill que está na pagina da documentação.

Performance

Já sabemos que .repeat() é bem mais curto, mas e será que a performance é diferente em termos de velocidade de execução ?

É de facto, o repeat é bem mais eficiente, embora só se note para quantidades grandes de repetições. Por isso se analisarmos os dois lado a lado para 5 repetições por exemplo, o tempo de execução é basicamente o mesmo:

Comparando para 5 repetições:

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%

Aqui dá para ver que na vez que eu executei, o código de concatenação normal foi mais rápido 3%.

Veja este teste no jsben
Cada teste pode variar ligeiramente, por isso é aconselhável que corra o teste algumas vezes para ter uma ideia mais realista da comparação

Comparando para 5000 repetições:

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

Veja estes resultados também no jsben

Aqui já vê uma diferença bem grande na execução dos dois.

Este mesmo teste no jsperf dá resultados idênticos com descrição de quantas vezes executou. Na minha máquina obtive:

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

Quando olhamos para a quantidade de execuções vemos que é uma diferença abismal. Como é possível que seja assim tanto ? Tem a ver com o algoritmo em si.

Algoritmo

Ao contrário do que poderíamos pensar, o algoritmo base para o repeat não é ir concatenando palavra a palavra até formar o resultado pretendido, em que isso teria uma complexidade de O(N) sendo o N o número de repetições.

A solução utilizada tem complexidade O(log2(n)), que pode ser descrito da seguinte forma:

  • Apenas o último bit da variável que tem o número de repetições é interpretado
  • Quando o ultimo bit é 1 concatena a palavra ao resultado
  • Em cada passo descarta o ultimo bit da variável repetições e "dobra" a palavra. Se a palavra era "palavra ", passa a ficar "palavra palavra"

Esta lógica faz com que precise de bem menos concatenações, pois a palavra que está a ser concatenada vai aumentando.

Confuso ? Um exemplo de execução para "palavra ", 5 seria:

        | 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 "

Neste pequeno exemplo de execução a palavra foi concatenada uma vez no inicio, depois foi dobrada duas vezes, ficando "palavra palavra palavra palavra " e só no fim foi concatenada de novo com o resultado formando o resultado pretendido.

Implementação:

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));

Fonte deste código

Conclusão

Sempre que tiver funções nativas que fazem o que pretende deve utiliza-las pois não só elas são bem mais curtas a nível de extensão de código, como podem ser muito mais performáticas, devido a utilizarem algoritmos que nem está a imaginar!

11
  • Nossa, bem simples e eu não conhecia. Muito obrigado! Commented 8/06/2018 às 0:37
  • Seria bom informar a compatibilidade dos navegadores, parece não funcionar no IE
    – user60252
    Commented 8/06/2018 às 0:56
  • @LeoCaracciolo Sim é verdade, Obrigado pelo aviso.
    – Isac
    Commented 8/06/2018 às 1:01
  • 2
    @dvd em Python isso funciona. ideone.com/lXm0RG
    – Largato
    Commented 8/06/2018 às 1:22
  • 1
    @DVD veja essa linha casasTestadas = [[False]*8 for i in range(8)] Nessa resposta: pt.stackoverflow.com/a/170854/70 - Usei a multiplicação pra fazer 8 x 8 variáveis false. Só não fiz [[false]*8]*8 diretamente, com receio de gerar um array por referência, por isso o range.
    – Largato
    Commented 8/06/2018 às 1:30
0

Restou a duvida do que seria que seja mais otimizado.

Seria talvez no significado do contexto abaixo?

Por que otimizar nossos Sites é tão importante? Simplesmente porque nenhum usuário gosta de perder tempo esperando o carregamento das páginas. É extremamente irritante.

Para tanto, basta rodar os exemplos abaixo e tirar as próprias conclusões

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(); 

1
  • Sim, já estou usando um timer para testar o tempo de execução. O algoritmo é bem extenso, pois trata-se de uma espécie de pequeno programa online, onde o usuário insere certos dados e recebe um arquivo completo com eles. Outrora, para um mesmo efeito demorava 15 minutos (isso mesmo, 15 minutos, muita coisa), fiz algumas modificações incluindo essa do 'repeat' e agora está demorando 2 minutos. Uma redução de 87%. Ainda acho muito, 2 minutos, e estou trabalhando para melhorar ainda mais... Commented 8/06/2018 às 16:36

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .