Repetir String - Javascript

271

Qual é o método melhor ou mais conciso para retornar uma sequência repetida várias vezes?

O seguinte é o meu melhor tiro até agora:

function repeat(s, n){
    var a = [];
    while(a.length < n){
        a.push(s);
    }
    return a.join('');
}
Brad
fonte
5
Há mais de 10 anos, havia uma solução bem conhecida minha para esse problema, e que eu usei como exemplo em um artigo de otimização de JavaScript alguns meses antes de você fazer esta pergunta: webreference.com/programming/javascript/jkm3/3 .html Aparentemente, a maioria das pessoas esqueceu esse código e não vejo nenhuma solução tão boa quanto a minha. O melhor algoritmo parece ter sido retirado do meu código; exceto devido a um mal-entendido de como meu código funciona, ele executa uma etapa extra de concatenação exponencial que é eliminada no original com um loop especial.
Joseph Myers
10
Ninguém levantou a solução de Joseph. O algoritmo tem 3700 anos. O custo da etapa extra é insignificante. E este artigo contém erros e conceitos errados sobre a concatenação de cadeias de caracteres em Javascript. Para qualquer pessoa interessada em como o Javascript realmente lida com seqüências de caracteres internamente, consulte Rope .
Artistoex
4
Ninguém parece ter notado que a repetição do protoype String é definida e implementada, pelo menos no Firefox.
Kennebec
3
@kennebec: Sim, esse é um recurso do EcmaScript 6 que não existia quando essa pergunta foi feita. É razoavelmente bem suportado agora.
rvighne
3
@rvighne - Eu só agora verificado kangax.github.io/compat-table/es6/#String.prototype.repeat eu não iria considerar o apoio exclusivamente a partir de Firefox e Chrome como "razoavelmente bem suportado"
aaaaaa

Respostas:

406

Nota para os novos leitores: Essa resposta é antiga e não é muito prática - é apenas "inteligente" porque usa coisas de Array para fazer as coisas de String. Quando escrevi "menos processo", definitivamente quis dizer "menos código" porque, como outros observaram nas respostas subseqüentes, ele funciona como um porco. Portanto, não o use se a velocidade for importante para você.

Eu colocaria essa função no objeto String diretamente. Em vez de criar uma matriz, preenchê-la e uni-la com um caractere vazio, basta criar uma matriz com o comprimento adequado e associá-la à string desejada. Mesmo resultado, menos processo!

String.prototype.repeat = function( num )
{
    return new Array( num + 1 ).join( this );
}

alert( "string to repeat\n".repeat( 4 ) );
Peter Bailey
fonte
36
Tento não estender objetos nativos, mas, caso contrário, essa é uma solução bonita. Obrigado!
brad
34
@ Brad - por que não? Você prefere poluir o espaço para nome global com uma função que tenha uma casa bastante bem definida (o objeto String)?
Peter Bailey
16
Na verdade, os dois argumentos também se aplicam ao espaço para nome global. Se pretendo expandir um espaço para nome e tiver possíveis colisões, prefiro fazê-lo 1) não no global 2) em um que seja relevante e 3) seja fácil de refatorar. Isso significa colocá-lo no protótipo String, não no global.
22468 Peter Bailey
11
uma mudança que eu faria nessa função seria colocar parseInt () em torno de "num", pois se você tiver uma sequência numérica, poderá ter um comportamento estranho devido ao malabarismo do tipo JS. por exemplo: "minha string" .repeat ("6") == "61"
nickf
19
Se você não deseja estender objetos nativos, você pode colocar a função no objeto String em vez, como este: String.repeat = function(string, num){ return new Array(parseInt(num) + 1).join(string); };. Chame assim:String.repeat('/\', 20)
Znarkus 31/08/10
204

Eu testei o desempenho de todas as abordagens propostas.

Aqui está a variante mais rápida que eu tenho.

String.prototype.repeat = function(count) {
    if (count < 1) return '';
    var result = '', pattern = this.valueOf();
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    return result + pattern;
};

Ou como função autônoma :

function repeat(pattern, count) {
    if (count < 1) return '';
    var result = '';
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    return result + pattern;
}

É baseado no algoritmo artistoex . É realmente rápido. E quanto maior count, mais rápido ele se compara à new Array(count + 1).join(string)abordagem tradicional .

Eu mudei apenas duas coisas:

  1. substituído pattern = thispor pattern = this.valueOf()(limpa uma conversão de tipo óbvia);
  2. inclusão de if (count < 1)verificação de prototypejs na parte superior da função para excluir ações desnecessárias nesse caso.
  3. otimização aplicada a partir da resposta de Dennis (5-7% de velocidade)

UPD

Criou um pequeno parque de teste de desempenho aqui para aqueles que interessados.

variável count~ 0 .. 100:

Diagrama de desempenho

constante count= 1024:

Diagrama de desempenho

Use-o e torne-o ainda mais rápido, se puder :)

desfigurado
fonte
4
Bom trabalho! Eu acho que o count < 1caso é realmente otimização desnecessária.
Jayvee
Excelente algoritmo O (log N). Obrigado pela ótima otimização com valueOf ()
vp_arth
2
Links de imagem estão mortos.
Benjamin Gruenbaum
Os links estão bem. Pode haver indisponibilidade temporária
disfated
O teste JSFiddle não funciona mais corretamente; parece apenas manter funcionando a primeira função e outra vez (deixou correr por meia hora para ter certeza)
RevanProdigalKnight
47

Esse problema é um problema de otimização conhecido / "clássico" para JavaScript, causado pelo fato de que as strings JavaScript são "imutáveis" e a adição pela concatenação de um único caractere a uma string exige a criação de, incluindo alocação de memória e cópia para , uma nova sequência inteira.

Infelizmente, a resposta aceita nesta página está errada, onde "errado" significa um fator de desempenho de 3x para seqüências de caracteres simples de um caractere e 8x-97x para seqüências curtas repetidas mais vezes, a 300x para repetir frases e infinitamente errado quando tomando o limite das proporções de complexidade dos algoritmos como nvai para o infinito. Além disso, há outra resposta nesta página que está quase correta (com base em uma das muitas gerações e variações da solução correta que circula pela Internet nos últimos 13 anos). No entanto, essa solução "quase correta" perde um ponto-chave do algoritmo correto, causando uma degradação de 50% no desempenho.

Resultados de desempenho de JS para a resposta aceita, a outra resposta com melhor desempenho (com base em uma versão degradada do algoritmo original nesta resposta) e essa resposta usando meu algoritmo criado há 13 anos

Em outubro de 2000, publiquei um algoritmo para esse problema exato, que foi amplamente adaptado, modificado e, eventualmente, pouco compreendido e esquecido. Para corrigir esse problema, em agosto de 2008, publiquei um artigo http://www.webreference.com/programming/javascript/jkm3/3.html explicando o algoritmo e usando-o como um exemplo de otimizações simples de JavaScript de uso geral. Até agora, a Referência da Web limpou minhas informações de contato e até mesmo meu nome neste artigo. E mais uma vez, o algoritmo foi amplamente adaptado, modificado, depois mal compreendido e amplamente esquecido.

Algoritmo JavaScript de repetição / multiplicação de strings original de Joseph Myers, por volta do Y2K como uma função de multiplicação de texto no Text.js; publicado em agosto de 2008 neste formulário pela Web Reference: http://www.webreference.com/programming/javascript/jkm3/3.html (O artigo usou a função como um exemplo de otimizações de JavaScript, que é o único para os estranhos nome "stringFill3.")

/*
 * Usage: stringFill3("abc", 2) == "abcabc"
 */

function stringFill3(x, n) {
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
}

Dois meses após a publicação desse artigo, essa mesma pergunta foi postada no Stack Overflow e voou sob meu radar até agora, quando aparentemente o algoritmo original para esse problema foi novamente esquecido. A melhor solução disponível nesta página Stack Overflow é uma versão modificada da minha solução, possivelmente separada por várias gerações. Infelizmente, as modificações arruinaram a otimização da solução. De fato, ao alterar a estrutura do loop do meu original, a solução modificada executa uma etapa extra completamente desnecessária de duplicação exponencial (juntando, assim, a maior cadeia usada na resposta adequada por um tempo extra e descartando-a).

Abaixo segue uma discussão sobre algumas otimizações de JavaScript relacionadas a todas as respostas para esse problema e para o benefício de todos.

Técnica: Evite referências a objetos ou propriedades de objetos

Para ilustrar como essa técnica funciona, usamos uma função JavaScript da vida real que cria seqüências de caracteres de qualquer tamanho necessário. E como veremos, mais otimizações podem ser adicionadas!

Uma função como a usada aqui é criar preenchimento para alinhar colunas de texto, formatar dinheiro ou preencher dados de bloco até o limite. Uma função de geração de texto também permite a entrada de comprimento variável para testar qualquer outra função que opere no texto. Essa função é um dos componentes importantes do módulo de processamento de texto JavaScript.

À medida que prosseguimos, abordaremos mais duas das técnicas de otimização mais importantes, enquanto desenvolvemos o código original em um algoritmo otimizado para a criação de strings. O resultado final é uma função de alto desempenho e força industrial que já usei em todos os lugares - alinhando preços e totais de itens em formulários de pedidos JavaScript, formatação de dados e formatação de email / mensagem de texto e muitos outros usos.

Código original para criar strings stringFill1()

function stringFill1(x, n) { 
    var s = ''; 
    while (s.length < n) s += x; 
    return s; 
} 
/* Example of output: stringFill1('x', 3) == 'xxx' */ 

A sintaxe aqui é clara. Como você pode ver, já usamos variáveis ​​de função local, antes de avançar para mais otimizações.

Esteja ciente de que há uma referência inocente a uma propriedade de objeto s.lengthno código que prejudica seu desempenho. Pior ainda, o uso dessa propriedade de objeto reduz a simplicidade do programa ao assumir que o leitor conhece as propriedades dos objetos de sequência JavaScript.

O uso dessa propriedade de objeto destrói a generalidade do programa de computador. O programa assume que xdeve ser uma sequência de comprimento um. Isso limita a aplicação da stringFill1()função a qualquer coisa, exceto a repetição de caracteres únicos. Mesmo caracteres únicos não podem ser usados ​​se eles contiverem vários bytes como a entidade HTML &nbsp;.

O pior problema causado por esse uso desnecessário de uma propriedade de objeto é que a função cria um loop infinito se testada em uma sequência de entrada vazia x. Para verificar a generalidade, aplique um programa à menor quantidade possível de entrada. Um programa que trava quando solicitado a exceder a quantidade de memória disponível tem uma desculpa. Um programa como este, que trava quando solicitado a produzir nada, é inaceitável. Às vezes, um código bonito é um código venenoso.

A simplicidade pode ser um objetivo ambíguo da programação de computadores, mas geralmente não é. Quando um programa não possui um nível razoável de generalidade, não é válido dizer: "O programa é bom o suficiente na medida do possível". Como você pode ver, o uso da string.lengthpropriedade impede que este programa funcione em uma configuração geral e, de fato, o programa incorreto está pronto para causar uma falha no navegador ou no sistema.

Existe uma maneira de melhorar o desempenho desse JavaScript e cuidar desses dois problemas sérios?

Claro. Basta usar números inteiros.

Código otimizado para criar strings stringFill2()

function stringFill2(x, n) { 
    var s = ''; 
    while (n-- > 0) s += x; 
    return s; 
} 

Código de tempo para comparar stringFill1()estringFill2()

function testFill(functionToBeTested, outputSize) { 
    var i = 0, t0 = new Date(); 
    do { 
        functionToBeTested('x', outputSize); 
        t = new Date() - t0; 
        i++; 
    } while (t < 2000); 
    return t/i/1000; 
} 
seconds1 = testFill(stringFill1, 100); 
seconds2 = testFill(stringFill2, 100); 

O sucesso até agora de stringFill2()

stringFill1()leva 47,297 microssegundos (milionésimos de segundo) para preencher uma cadeia de 100 bytes e stringFill2()leva 27,68 microssegundos para fazer a mesma coisa. Isso quase dobrou o desempenho, evitando a referência a uma propriedade de objeto.

Técnica: Evite adicionar cadeias curtas a longas

Nosso resultado anterior parecia bom - muito bom, de fato. A função aprimorada stringFill2()é muito mais rápida devido ao uso das nossas duas primeiras otimizações. Você acreditaria se eu lhe dissesse que pode ser melhorado muitas vezes mais rápido do que é agora?

Sim, podemos alcançar esse objetivo. No momento, precisamos explicar como evitar anexar cadeias curtas a longas.

O comportamento a curto prazo parece ser bastante bom, em comparação com a nossa função original. Os cientistas da computação gostam de analisar o "comportamento assintótico" de uma função ou algoritmo de programa de computador, o que significa estudar seu comportamento a longo prazo, testando-o com entradas maiores. Às vezes, sem fazer mais testes, nunca se percebe como um programa de computador pode ser aprimorado. Para ver o que vai acontecer, vamos criar uma string de 200 bytes.

O problema que aparece com stringFill2()

Usando nossa função de temporização, descobrimos que o tempo aumenta para 62,54 microssegundos para uma sequência de 200 bytes, em comparação com 27,68 para uma sequência de 100 bytes. Parece que o tempo deve ser dobrado para fazer o dobro do trabalho, mas, em vez disso, é triplicado ou quadruplicado. Da experiência em programação, esse resultado parece estranho, porque, se houver algo, a função deve ser um pouco mais rápida, pois o trabalho está sendo realizado com mais eficiência (200 bytes por chamada de função em vez de 100 bytes por chamada de função). Esse problema tem a ver com uma propriedade insidiosa de strings JavaScript: as strings JavaScript são "imutáveis".

Imutável significa que você não pode alterar uma sequência depois que ela é criada. Ao adicionar um byte de cada vez, não estamos gastando mais um byte de esforço. Na verdade, estamos recriando a string inteira mais um byte.

Com efeito, para adicionar mais um byte a uma string de 100 bytes, são necessários 101 bytes de trabalho. Vamos analisar brevemente o custo computacional para criar uma sequência de Nbytes. O custo da adição do primeiro byte é de 1 unidade de esforço computacional. O custo de adicionar o segundo byte não é uma unidade, mas duas unidades (copiar o primeiro byte para um novo objeto de string e adicionar o segundo byte). O terceiro byte requer um custo de 3 unidades, etc.

C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2). O símbolo O(N^2)é pronunciado Big O of N ao quadrado e significa que o custo computacional a longo prazo é proporcional ao quadrado do comprimento da string. Criar 100 caracteres requer 10.000 unidades de trabalho e criar 200 caracteres requer 40.000 unidades de trabalho.

É por isso que demorou mais que o dobro para criar 200 caracteres e 100 caracteres. De fato, deveria ter levado quatro vezes mais. Nossa experiência em programação estava correta, pois o trabalho está sendo realizado de forma um pouco mais eficiente para seqüências mais longas e, portanto, levou apenas cerca de três vezes mais. Quando a sobrecarga da chamada de função se torna insignificante quanto ao comprimento de uma string que estamos criando, na verdade levará quatro vezes mais tempo para criar uma string com o dobro do tempo.

(Nota histórica: Essa análise não se aplica necessariamente a cadeias de caracteres no código-fonte, como html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n', uma vez que o compilador de código-fonte JavaScript pode unir as cadeias antes de transformá-las em um objeto de cadeia JavaScript. Há alguns anos, a implementação do KJS de O JavaScript congelava ou falhava ao carregar longas seqüências de código-fonte unidas por sinais de mais.Como o tempo computacional O(N^2)não era difícil de criar páginas da Web que sobrecarregavam o navegador Konqueror ou o Safari, que usava o núcleo do mecanismo JavaScript do KJS. deparei com esse problema quando eu estava desenvolvendo uma linguagem de marcação e um analisador de linguagem de marcação JavaScript e descobri o que estava causando o problema quando escrevi meu script para o JavaScript Inclui.

Claramente, essa rápida degradação do desempenho é um enorme problema. Como podemos lidar com isso, já que não podemos mudar a maneira do JavaScript de manipular strings como objetos imutáveis? A solução é usar um algoritmo que recria a string o menor número de vezes possível.

Para esclarecer, nosso objetivo é evitar adicionar cadeias curtas a longas, pois, para adicionar a cadeia curta, toda a cadeia longa também deve ser duplicada.

Como o algoritmo funciona para evitar adicionar cadeias curtas a longas

Aqui está uma boa maneira de reduzir o número de vezes que novos objetos de string são criados. Concatene comprimentos maiores de cadeia juntos para que mais de um byte de cada vez seja adicionado à saída.

Por exemplo, para criar uma sequência de comprimento N = 9:

x = 'x'; 
s = ''; 
s += x; /* Now s = 'x' */ 
x += x; /* Now x = 'xx' */ 
x += x; /* Now x = 'xxxx' */ 
x += x; /* Now x = 'xxxxxxxx' */ 
s += x; /* Now s = 'xxxxxxxxx' as desired */

Para isso, era necessário criar uma sequência de comprimento 1, criar uma sequência de comprimento 2, criar uma sequência de comprimento 4, criar uma sequência de comprimento 8 e, finalmente, criar uma sequência de comprimento 9. Quanto custo economizamos?

Custo antigo C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45.

Novo custo C(9) = 1 + 2 + 4 + 8 + 9 = 24.

Observe que tivemos que adicionar uma string de comprimento 1 a uma string de comprimento 0, depois uma string de comprimento 1 a uma string de comprimento 1, depois uma string de comprimento 2 a uma string de comprimento 2, depois uma string de comprimento 4 para uma cadeia de comprimento 4, depois uma cadeia de comprimento 8 para uma cadeia de comprimento 1, a fim de obter uma cadeia de comprimento 9. O que estamos fazendo pode ser resumido como evitar adicionar cadeias curtas a cadeias longas ou em outras palavras, tentando concatenar cadeias de comprimento igual ou quase igual.

Para o antigo custo computacional, encontramos uma fórmula N(N+1)/2. Existe uma fórmula para o novo custo? Sim, mas é complicado. O importante é que sim O(N), e dobrar o comprimento da corda dobrará aproximadamente a quantidade de trabalho, em vez de quadruplicar.

O código que implementa essa nova idéia é quase tão complicado quanto a fórmula para o custo computacional. Ao ler, lembre-se de que isso >>= 1significa mudar para a direita em 1 byte. Então, se n = 10011é um número binário, n >>= 1resulta no valor n = 1001.

A outra parte do código que você talvez não reconheça é o operador bit a bit e escrito &. A expressão n & 1avalia true se o último dígito binário de nfor 1 e false se o último dígito binário de nfor 0.

Nova stringFill3()função altamente eficiente

function stringFill3(x, n) { 
    var s = ''; 
    for (;;) { 
        if (n & 1) s += x; 
        n >>= 1; 
        if (n) x += x; 
        else break; 
    } 
    return s; 
} 

Parece feio para os olhos destreinados, mas seu desempenho é nada menos que adorável.

Vamos ver o quão bem essa função executa. Depois de ver os resultados, é provável que você nunca esqueça a diferença entre um O(N^2)algoritmo e um O(N)algoritmo.

stringFill1()leva 88,7 microssegundos (milionésimos de segundo) para criar uma sequência de 200 bytes, stringFill2()leva 62,54 e stringFill3()leva apenas 4,608. O que tornou esse algoritmo muito melhor? Todas as funções tiraram vantagem do uso de variáveis ​​de função locais, mas tirar proveito da segunda e terceira técnicas de otimização adicionou uma melhoria de vinte vezes ao desempenho de stringFill3().

Análise mais profunda

O que faz com que essa função em particular afaste a concorrência da água?

Como já mencionei, a razão para que ambas as funções, stringFill1()e stringFill2(), corra tão lentamente é que as cordas JavaScript são imutáveis. A memória não pode ser realocada para permitir que mais um byte de cada vez seja anexado aos dados da string armazenados pelo JavaScript. Toda vez que mais um byte é adicionado ao final da string, a string inteira é regenerada do começo ao fim.

Portanto, para melhorar o desempenho do script, é necessário pré-computar cadeias de comprimento mais longas concatenando duas cadeias antes do tempo e depois construindo recursivamente o comprimento de cadeia desejado.

Por exemplo, para criar uma sequência de 16 bytes, primeiro uma sequência de dois bytes seria pré-computada. Em seguida, a cadeia de dois bytes seria reutilizada para pré-calcular uma cadeia de quatro bytes. Em seguida, a cadeia de quatro bytes seria reutilizada para pré-calcular uma cadeia de oito bytes. Finalmente, duas seqüências de oito bytes seriam reutilizadas para criar a nova sequência desejada de 16 bytes. No total, quatro novas cadeias tiveram que ser criadas, uma de comprimento 2, uma de comprimento 4, uma de comprimento 8 e uma de comprimento 16. O custo total é de 2 + 4 + 8 + 16 = 30.

A longo prazo, essa eficiência pode ser calculada adicionando-se na ordem inversa e usando uma série geométrica começando com o primeiro termo a1 = N e tendo uma razão comum de r = 1/2. A soma de uma série geométrica é dada por a_1 / (1-r) = 2N.

Isso é mais eficiente do que adicionar um caractere para criar uma nova cadeia de comprimento 2, criando uma nova cadeia de comprimento 3, 4, 5 e assim por diante, até 16. O algoritmo anterior usou esse processo de adição de um único byte por vez , e o custo total seria n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136.

Obviamente, 136 é um número muito maior que 30 e, portanto, o algoritmo anterior leva muito, muito mais tempo para construir uma string.

Para comparar os dois métodos, é possível ver com que rapidez o algoritmo recursivo (também chamado de "dividir e conquistar") está em uma sequência de comprimento 123.457. No meu computador com FreeBSD, esse algoritmo, implementado na stringFill3()função, cria a string em 0,001058 segundos, enquanto a stringFill1()função original cria a string em 0,0808 segundos. A nova função é 76 vezes mais rápida.

A diferença no desempenho aumenta à medida que o comprimento da string se torna maior. No limite, à medida que cadeias cada vez maiores são criadas, a função original se comporta aproximadamente como C1tempos (constantes) N^2e a nova função se comporta como C2tempos (constantes) N.

Do nosso experimento, podemos determinar o valor de C1ser C1 = 0.0808 / (123457)2 = .00000000000530126997e o valor de C2ser C2 = 0.001058 / 123457 = .00000000856978543136. Em 10 segundos, a nova função poderia criar uma sequência contendo 1.166.890.359 caracteres. Para criar essa mesma string, a função antiga precisaria de 7.218.384 segundos de tempo.

São quase três meses em comparação com dez segundos!

Só estou respondendo (vários anos atrasado) porque minha solução original para esse problema está flutuando na Internet há mais de 10 anos e, aparentemente, ainda é pouco compreendida pelos poucos que se lembram dele. Eu pensei que, escrevendo um artigo sobre o assunto aqui, eu ajudaria:

Otimizações de desempenho para JavaScript de alta velocidade / Página 3

Infelizmente, algumas das outras soluções apresentadas aqui ainda são aquelas que levariam três meses para produzir a mesma quantidade de saída que uma solução adequada cria em 10 segundos.

Quero dedicar um tempo para reproduzir parte do artigo aqui como uma resposta canônica no Stack Overflow.

Observe que o algoritmo de melhor desempenho aqui é claramente baseado no meu algoritmo e provavelmente foi herdado da adaptação de terceira ou quarta geração de outra pessoa. Infelizmente, as modificações resultaram na redução de seu desempenho. A variação da minha solução apresentada aqui talvez não entenda minha for (;;)expressão confusa que se parece com o loop infinito principal de um servidor escrito em C e que foi simplesmente projetada para permitir uma declaração de interrupção cuidadosamente posicionada para controle de loop, a maneira mais compacta de evite replicar exponencialmente a string um tempo extra desnecessário.

Joseph Myers
fonte
4
Esta resposta não deveria ter recebido tantas votações. Antes de tudo, as reivindicações de propriedade de Joseph são ridículas. O algoritmo subjacente tem 3700 anos.
Artistoex
2
Segundo, contém muita desinformação. As implementações modernas de Javascript nem tocam o conteúdo de uma string ao executar a concatenação (v8 representa cadeias de caracteres concatenadas como um objeto do tipo ConsString). Todas as melhorias restantes são insignificantes (em termos de complexidade assintótica).
Artistoex
3
Sua idéia de como as seqüências de caracteres são concatenadas está errada. Para concatenar duas cadeias, o Javascript não lê os bytes das cadeias constituintes. Em vez disso, apenas cria um objeto que se refere às partes esquerda e direita. É por isso que a última concatenação no loop não é mais cara que as primeiras.
Artistoex
3
Obviamente, isso resulta em um custo maior que O (1) para indexar a string, de modo que a concatenação pode ser achatada posteriormente, o que de fato merece mais avaliações.
Artistoex
1
Esta foi uma excelente leitura. Você deve escrever um livro sobre eficiência e tudo isso!
39

Este é bastante eficiente

String.prototype.repeat = function(times){
    var result="";
    var pattern=this;
    while (times > 0) {
        if (times&1)
            result+=pattern;
        times>>=1;
        pattern+=pattern;
    }
    return result;
};
artistoex
fonte
11
@Olegs, acho que a idéia de votar é menos do que votar em uma pessoa ou na criatividade de uma pessoa (o que é realmente aplaudível), mas a idéia é votar na solução mais completa, para que ela possa ser facilmente encontrada no no topo da lista, sem ter que ler todas as respostas na busca pela perfeita. (Porque, infelizmente, todos nós temos tempo limitado ...)
Sorin Postelnicu
38

Boas notícias! String.prototype.repeaté agora uma parte de JavaScript .

"yo".repeat(2);
// returns: "yoyo"

O método é suportado por todos os principais navegadores, exceto o Internet Explorer e o Android Webview. Para obter uma lista atualizada, consulte MDN: String.prototype.repeat> Compatibilidade do navegador .

O MDN possui um polyfill para navegadores sem suporte.

André Laszlo
fonte
Obrigado por relatar o estado atual das coisas, embora eu ache que o polyfill da Mozilla é muito complicado para a maioria das necessidades (suponho que eles tentem imitar o comportamento eficiente da implementação de C) - portanto, não responderá realmente ao requisito de conciência do OP. Qualquer uma das outras abordagens configurar como um polyfill são obrigados a ser mais conciso ;-)
Guss
2
Definitivamente! Mas o uso do built-in deve ser a versão mais concisa. Como os polyfills são basicamente apenas portas traseiras, eles tendem a ser um pouco complexos para garantir a compatibilidade com as especificações (ou especificações propostas, neste caso). Eu o adicionei por completo, cabe ao OP decidir qual método usar, eu acho.
André Laszlo
19

String.prototype.repeat agora é o ES6 Standard.

'abc'.repeat(3); //abcabcabc
Lewis
fonte
legais! .. mas não é utilizável para mim (não é suportado no ios <9): kangax.github.io/compat-table/es6
Benjamin
@ Benjamin Use o polyfill no link.
Lewis
Eu acho que deveria ser uma resposta fixa .
precisa
17

Expandindo a solução de P.Bailey :

String.prototype.repeat = function(num) {
    return new Array(isNaN(num)? 1 : ++num).join(this);
    }

Dessa forma, você deve estar protegido contra tipos de argumentos inesperados:

var foo = 'bar';
alert(foo.repeat(3));              // Will work, "barbarbar"
alert(foo.repeat('3'));            // Same as above
alert(foo.repeat(true));           // Same as foo.repeat(1)

alert(foo.repeat(0));              // This and all the following return an empty
alert(foo.repeat(false));          // string while not causing an exception
alert(foo.repeat(null));
alert(foo.repeat(undefined));
alert(foo.repeat({}));             // Object
alert(foo.repeat(function () {})); // Function

EDIT: Créditos a jerone por sua ++numidéia elegante !

antichris
fonte
2
Alterou o seu é um pouco:String.prototype.repeat = function(n){return new Array(isNaN(n) ? 1 : ++n).join(this);}
jerone 13/07/10
De qualquer forma, de acordo com este teste ( jsperf.com/string-repeat/2 ), fazer um loop for simples com concatanação de strings parece ser muito mais rápido no Chrome em comparação com o Array.join. Não é engraçado ?!
Marco Demaio 26/03
8

Usar Array(N+1).join("string_to_repeat")

Kalpesh Patel
fonte
Eu gosto disso. Idk porque não está lá em cima.
Joe Thomas
adoro. tão simples e limpo
ekkis
5
/**  
@desc: repeat string  
@param: n - times  
@param: d - delimiter  
*/

String.prototype.repeat = function (n, d) {
    return --n ? this + (d || '') + this.repeat(n, d) : '' + this
};

é assim que se repete a string várias vezes usando o delimeter.

BitOfUniverse
fonte
4

Aqui está uma melhoria de 5-7% na resposta da disfated.

Desenrole o loop parando em count > 1e execute uma result += pattnernconcat adicional após o loop. Isso evitará que os loops finais não sejam utilizados anteriormente pattern += patternsem a necessidade de usar uma verificação de if cara. O resultado final ficaria assim:

String.prototype.repeat = function(count) {
    if (count < 1) return '';
    var result = '', pattern = this.valueOf();
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    result += pattern;
    return result;
};

E aqui está o violino de disfated bifurcado para a versão desenrolada: http://jsfiddle.net/wsdfg/

Dennis
fonte
2
function repeat(s, n) { var r=""; for (var a=0;a<n;a++) r+=s; return r;}
Joel Coehoorn
fonte
2
A concatenação de cadeias de caracteres não é cara? Esse é pelo menos o caso em Java.
Vijay Dev
Por que sim eles são. No entanto, ele realmente não pode ser otimizado em javarscript. :(
McTrafik
E sobre esse desempenho: var r=s; for (var a=1;...:)))) De qualquer forma, de acordo com este teste ( jsperf.com/string-repeat/2 ), fazendo um loop for simples com concatanação de strings, como o que você sugeriu parece ser muito mais rápido no Chrome, em comparação com o Array .Junte-se.
Marco Demaio 26/03
@VijayDev - não de acordo com este teste: jsperf.com/ultimate-concat-vs-join
jbyrd
2

Testes dos vários métodos:

var repeatMethods = {
    control: function (n,s) {
        /* all of these lines are common to all methods */
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return '';
    },
    divideAndConquer:   function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        with(Math) { return arguments.callee(floor(n/2), s)+arguments.callee(ceil(n/2), s); }
    },
    linearRecurse: function (n,s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return s+arguments.callee(--n, s);
    },
    newArray: function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return (new Array(isNaN(n) ? 1 : ++n)).join(s);
    },
    fillAndJoin: function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        var ret = [];
        for (var i=0; i<n; i++)
            ret.push(s);
        return ret.join('');
    },
    concat: function (n,s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        var ret = '';
        for (var i=0; i<n; i++)
            ret+=s;
        return ret;
    },
    artistoex: function (n,s) {
        var result = '';
        while (n>0) {
            if (n&1) result+=s;
            n>>=1, s+=s;
        };
        return result;
    }
};
function testNum(len, dev) {
    with(Math) { return round(len+1+dev*(random()-0.5)); }
}
function testString(len, dev) {
    return (new Array(testNum(len, dev))).join(' ');
}
var testTime = 1000,
    tests = {
        biggie: { str: { len: 25, dev: 12 }, rep: {len: 200, dev: 50 } },
        smalls: { str: { len: 5, dev: 5}, rep: { len: 5, dev: 5 } }
    };
var testCount = 0;
var winnar = null;
var inflight = 0;
for (var methodName in repeatMethods) {
    var method = repeatMethods[methodName];
    for (var testName in tests) {
        testCount++;
        var test = tests[testName];
        var testId = methodName+':'+testName;
        var result = {
            id: testId,
            testParams: test
        }
        result.count=0;

        (function (result) {
            inflight++;
            setTimeout(function () {
                result.start = +new Date();
                while ((new Date() - result.start) < testTime) {
                    method(testNum(test.rep.len, test.rep.dev), testString(test.str.len, test.str.dev));
                    result.count++;
                }
                result.end = +new Date();
                result.rate = 1000*result.count/(result.end-result.start)
                console.log(result);
                if (winnar === null || winnar.rate < result.rate) winnar = result;
                inflight--;
                if (inflight==0) {
                    console.log('The winner: ');
                    console.log(winnar);
                }
            }, (100+testTime)*testCount);
        }(result));
    }
}
Fordi
fonte
2

Aqui está a versão segura do JSLint

String.prototype.repeat = function (num) {
  var a = [];
  a.length = num << 0 + 1;
  return a.join(this);
};
Erik Aigner
fonte
2

Para todos os navegadores

Isso é o mais conciso possível:

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

Se você também se importa com o desempenho, esta é uma abordagem muito melhor:

function repeat(s, n) { var a=[],i=0;for(;i<n;)a[i++]=s;return a.join(''); }

Se você deseja comparar o desempenho de ambas as opções, consulte este Fiddle e este Fiddle para testes de benchmark. Durante meus próprios testes, a segunda opção foi cerca de 2 vezes mais rápida no Firefox e cerca de 4 vezes mais rápida no Chrome!

Apenas para navegadores modernos:

Nos navegadores modernos, agora você também pode fazer isso:

function repeat(s,n) { return s.repeat(n) };

Essa opção não é apenas mais curta que as outras duas opções, mas é ainda mais rápida que a segunda opção.

Infelizmente, ele não funciona em nenhuma versão do Internet Explorer. Os números na tabela especificam a primeira versão do navegador que suporta totalmente o método:

insira a descrição da imagem aqui

John Slegers
fonte
2

Apenas outra função de repetição:

function repeat(s, n) {
  var str = '';
  for (var i = 0; i < n; i++) {
    str += s;
  }
  return str;
}
oboshto
fonte
2

ES2015foi realizado este repeat()método!

http://www.ecma-international.org/ecma-262/6.0/#sec-string.prototype.repeat
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/ String / repeat
http://www.w3schools.com/jsref/jsref_repeat.asp

/** 
 * str: String
 * count: Number
 */
const str = `hello repeat!\n`, count = 3;

let resultString = str.repeat(count);

console.log(`resultString = \n${resultString}`);
/*
resultString = 
hello repeat!
hello repeat!
hello repeat!
*/

({ toString: () => 'abc', repeat: String.prototype.repeat }).repeat(2);
// 'abcabc' (repeat() is a generic method)

// Examples

'abc'.repeat(0);    // ''
'abc'.repeat(1);    // 'abc'
'abc'.repeat(2);    // 'abcabc'
'abc'.repeat(3.5);  // 'abcabcabc' (count will be converted to integer)
// 'abc'.repeat(1/0);  // RangeError
// 'abc'.repeat(-1);   // RangeError

xgqfrms
fonte
1

Este pode ser o menor recursivo: -

String.prototype.repeat = function(n,s) {
s = s || ""
if(n>0) {
   s += this
   s = this.repeat(--n,s)
}
return s}
John
fonte
1

Concatenação recursiva simples

Eu só queria fazer uma festança e fiz o seguinte:

function ditto( s, r, c ) {
    return c-- ? ditto( s, r += s, c ) : r;
}

ditto( "foo", "", 128 );

Não posso dizer que pensei muito, e provavelmente mostra :-)

Isto é sem dúvida melhor

String.prototype.ditto = function( c ) {
    return --c ? this + this.ditto( c ) : this;
};

"foo".ditto( 128 );

E é como uma resposta já postada - eu sei disso.

Mas por que ser recursivo?

E que tal um pouco de comportamento padrão também?

String.prototype.ditto = function() {
    var c = Number( arguments[ 0 ] ) || 2,
        r = this.valueOf();
    while ( --c ) {
        r += this;
    }
    return r;
}

"foo".ditto();

Porque , embora o método não recursivo processe repetições arbitrariamente grandes sem atingir os limites da pilha de chamadas, é muito mais lento.

Por que me incomodei em adicionar mais métodos que não são tão inteligentes quanto os que já foram publicados?

Em parte por diversão, e em parte pela maneira mais simples: sei que existem várias maneiras de esfolar um gato e, dependendo da situação, é bem possível que o melhor método aparentemente não seja o ideal.

Um método relativamente rápido e sofisticado pode travar e queimar efetivamente sob certas circunstâncias, enquanto um método mais lento e simples pode fazer o trabalho - eventualmente.

Alguns métodos podem ser pouco mais de exploits, e, como tal, propenso a ser fixado fora da existência, e outros métodos podem funcionar muito bem em todas as condições, mas são construídos de tal modo que um simplesmente não tem idéia de como ele funciona.

"Então, e se eu não sei como isso funciona ?!"

Seriamente?

O JavaScript sofre de um dos seus maiores pontos fortes; é altamente tolerante ao mau comportamento e é tão flexível que se inclina para trás para retornar resultados, quando poderia ter sido melhor para todos se tivesse sido quebrado!

"Com grande poder, vem grande responsabilidade" ;-)

Mas, mais sério e importante, embora questões gerais como essa levem à grandiosidade na forma de respostas inteligentes que, se nada mais, expandem o conhecimento e os horizontes, no final, a tarefa em mãos - o roteiro prático que usa o método resultante - pode exigir um pouco menos, ou um pouco mais inteligente do que é sugerido.

Esses algoritmos "perfeitos" são divertidos e tudo, mas "tamanho único" raramente será melhor do que o feito sob medida.

Este sermão foi oferecido a você como cortesia da falta de sono e de um interesse passageiro. Vá em frente e codifique!

Fred Gandt
fonte
1

Em primeiro lugar, as perguntas do OP parecem ser concisas - o que entendo como "simples e fácil de ler", enquanto a maioria das respostas parece ser sobre eficiência - o que obviamente não é a mesma coisa e também acho que, a menos que você implemente algumas algoritmos específicos de manipulação de dados grandes, não deve se preocupar quando você implementar funções JavaScript de manipulação básica de dados. Concisão é muito mais importante.

Em segundo lugar, como observou André Laszlo, o String.repeat faz parte do ECMAScript 6 e já está disponível em várias implementações populares - portanto, a implementação mais concisa String.repeaté não implementá-lo ;-)

Por fim, se você precisar oferecer suporte a hosts que não oferecem a implementação do ECMAScript 6, o polyfill do MDN mencionado por André Laszlo é tudo menos conciso.

Portanto, sem mais delongas - aqui está o meu polyfill conciso :

String.prototype.repeat = String.prototype.repeat || function(n){
    return n<=1 ? this : this.concat(this.repeat(n-1));
}

Sim, isso é uma recursão. Eu gosto de recursões - elas são simples e, se feitas corretamente, são fáceis de entender. Em relação à eficiência, se o idioma suportar, eles podem ser muito eficientes se escritos corretamente.

Dos meus testes, esse método é ~ 60% mais rápido que a Array.joinabordagem. Embora, obviamente, não chegue nem perto da implementação do desatualizado, é muito mais simples que os dois.

Minha configuração de teste é o nó v0.10, usando o "Modo estrito" (acho que permite algum tipo de TCO ), chamando repeat(1000)uma sequência de 10 caracteres um milhão de vezes.

Guss
fonte
1

Se você acha que todas essas definições de protótipos, criações de matriz e operações de junção são um exagero, basta usar um código de linha único onde for necessário. Sequência S repetindo N vezes:

for (var i = 0, result = ''; i < N; i++) result += S;
Semra
fonte
3
O código deve ser legível. Se você literalmente usar apenas uma vez, formate-o corretamente (ou use o Array(N + 1).join(str)método se não houver um gargalo de desempenho). Se houver a menor chance de usá-lo duas vezes, mova-o para uma função de nome apropriado.
cloudfeet
1

Use a funcionalidade do utilitário Lodash para Javascript, como repetir strings.

O Lodash oferece bom desempenho e compatibilidade com ECMAScript.

Eu o recomendo para o desenvolvimento da interface do usuário e também funciona bem no servidor.

Veja como repetir a string "yo" 2 vezes usando o Lodash:

> _.repeat('yo', 2)
"yoyo"
l3x
fonte
0

Solução recursiva usando dividir e conquistar:

function repeat(n, s) {
    if (n==0) return '';
    if (n==1 || isNaN(n)) return s;
    with(Math) { return repeat(floor(n/2), s)+repeat(ceil(n/2), s); }
}
Fordi
fonte
0

Eu vim aqui aleatoriamente e nunca tive um motivo para repetir um caractere em javascript antes.

Fiquei impressionado com a maneira de fazer isso da artistoex e com os resultados desatualizados. Notei que o último concat de cordas era desnecessário, como Dennis também apontou.

Notei mais algumas coisas ao brincar com a amostra desfeita reunida.

Os resultados variaram bastante, favorecendo a última corrida, e algoritmos similares frequentemente disputavam posição. Uma das coisas que mudei foi em vez de usar a contagem gerada pelo JSLitmus como a semente das chamadas; como a contagem foi gerada diferente para os vários métodos, coloquei um índice. Isso tornou a coisa muito mais confiável. Eu, então, olhei para garantir que seqüências de tamanhos variadas fossem passadas para as funções. Isso impediu algumas das variações que eu vi, onde alguns algoritmos se saíram melhor nos caracteres únicos ou nas seqüências menores. No entanto, os três métodos principais foram bem, independentemente do tamanho da string.

Conjunto de teste bifurcado

http://jsfiddle.net/schmide/fCqp3/134/

// repeated string
var string = '0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789';
// count paremeter is changed on every test iteration, limit it's maximum value here
var maxCount = 200;

var n = 0;
$.each(tests, function (name) {
    var fn = tests[name];
    JSLitmus.test(++n + '. ' + name, function (count) {
        var index = 0;
        while (count--) {
            fn.call(string.slice(0, index % string.length), index % maxCount);
            index++;
        }
    });
    if (fn.call('>', 10).length !== 10) $('body').prepend('<h1>Error in "' + name + '"</h1>');
});

JSLitmus.runAll();

Eu então incluí a correção de Dennis e decidi ver se eu poderia encontrar uma maneira de me aprofundar um pouco mais.

Como o javascript não pode realmente otimizar as coisas, a melhor maneira de melhorar o desempenho é evitar as coisas manualmente. Se eu tirasse os 4 primeiros resultados triviais do loop, poderia evitar de 2 a 4 armazenamentos de string e gravar o armazenamento final diretamente no resultado.

// final: growing pattern + prototypejs check (count < 1)
'final avoid': function (count) {
    if (!count) return '';
    if (count == 1) return this.valueOf();
    var pattern = this.valueOf();
    if (count == 2) return pattern + pattern;
    if (count == 3) return pattern + pattern + pattern;
    var result;
    if (count & 1) result = pattern;
    else result = '';
    count >>= 1;
    do {
        pattern += pattern;
        if (count & 1) result += pattern;
        count >>= 1;
    } while (count > 1);
    return result + pattern + pattern;
}

Isso resultou em uma melhoria de 1-2%, em média, em relação à correção de Dennis. No entanto, diferentes execuções e navegadores diferentes mostrariam uma variação suficiente o suficiente para que esse código extra provavelmente não valha o esforço dos 2 algoritmos anteriores.

Um gráfico

Edit: Eu fiz isso principalmente no chrome. O Firefox e o IE costumam favorecer Dennis em alguns%.

Andrew Hallendorff
fonte
0

Método simples:

String.prototype.repeat = function(num) {
    num = parseInt(num);
    if (num < 0) return '';
    return new Array(num + 1).join(this);
}
Eduardo Cuomo
fonte
0

As pessoas complicam demais isso de maneira ridícula ou perdem desempenho. Matrizes? Recursão? Só podes estar a brincar comigo.

function repeat (string, times) {
  var result = ''
  while (times-- > 0) result += string
  return result
}

Editar. Fiz alguns testes simples para comparar com a versão bit a bit postada por artistoex / disfated e várias outras pessoas. O último foi apenas um pouco mais rápido, mas ordens de magnitude mais eficientes em termos de memória. Para 1000000 repetições da palavra 'blah', o processo Node subiu para 46 megabytes com o algoritmo de concatenação simples (acima), mas apenas 5,5 megabytes com o algoritmo logarítmico. Este último é definitivamente o caminho a percorrer. Reposicionando-o por uma questão de clareza:

function repeat (string, times) {
  var result = ''
  while (times > 0) {
    if (times & 1) result += string
    times >>= 1
    string += string
  }
  return result
}
Nelo Mitranim
fonte
Você tem uma string += stringmetade redundante do tempo.
Nikolay 23/03
0

Concatenando cadeias com base em um número.

function concatStr(str, num) {
   var arr = [];

   //Construct an array
   for (var i = 0; i < num; i++)
      arr[i] = str;

   //Join all elements
   str = arr.join('');

   return str;
}

console.log(concatStr("abc", 3));

Espero que ajude!

loxsat
fonte
0

Com o ES8, você também pode usar padStartou padEndpara isso. por exemplo.

var str = 'cat';
var num = 23;
var size = str.length * num;
"".padStart(size, str) // outputs: 'catcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcat'
wizzfizz94
fonte