8

TL;DR: sei que existe uma classe chamada StringBuilder, tanto em .NET quanto em Java, que permite realizar operações sobre um texto sem que seja gerada uma nova string a cada chamada de método. Me seria muito conveniente ter algo semelhante em Javascript, porém não consigo encontrar nada semelhante.

Meu objetivo: vamos supor que tenho alguns textos de tamanho considerável sobre o qual desejo realizar determinadas operações de substituição. Por tamanho considerável, vamos imaginar strings com milhões de caracteres.

Sei que Javascript pode não parecer ser uma tecnologia apropriada para isso. Mas desejo fazer as substituições em tempo real, o que exclui técnicas como deixar um job a operar em um servidor. Também desejo substituir múltiplos trechos, com base em input do utilizador.

O problema: substituições em Javascript acabam por ser caras em memória. Alguém me corrija se eu estiver errado - mas se tenho uma string que ocupa um megabyte, ao utilizar o método replace do objeto String, terei uma ocupação de dois megabytes: um da string original, que não deixará de existir até que o coletor de lixo a reclame, e outro da nova string. Ao executar uma nova substituição, serão três megabytes, e assim por diante. Na milésima alteração, já estamos a ocupar nas proximidades de um gigabyte.

Estou a pensar em números aproximados, e a considerar que todas as substituições são globais (uso expressões regulares com o modificador g, i.e.: /foo/g).

A dúvida: existe algo que faça o papel de um StringBuilder em Javascript? Se não existe, há alguma forma pela qual se poderia implementar?

0

2 Respostas 2

6

Estive a pesquisar sobre o assunto e encontrei esse projeto StringBuilder. O qual parece ser optimizado para isso que você quer.

Normalmente seria utilizado um trecho de código parecido com isto:

var myString = "";
for (var i = 0; i < 1000; i++) {
    myString += i.toString();
}

O problema com isto é que é utilizado muita memória. Após a terceira iteração os seguintes valores estarão na memória:

""
"1"
"12"
"123"

Exemplo utilizando StringBuilder:

var myStringBuilder = StringBuilder();
for (var i = 0; i < 1000; i++) {
    myStringBuilder.append(i.toString());
}

Após a terceira iteração, apenas estes valores estarão na memória:

"1"
"2"
"3"
3
  • 1
    Alguém fez um comentário (infezlimente apagado) com um projeto parecido no Code Project. Muito interessante para concatenações - e acredito que, com algumas modificações, pode-se melhorar a performance para substituições também, creio que dá pra facilitar o trabalho do GC de algumas formas :) +1, e eu gostaria de dar outro voto positivo só pelo fato do projeto estar no Github. Commented 16/05/2014 às 14:51
  • 1
    ainda assim, de lá pra cá a linguagem não mudou muito com relação a strings. Commented 16/05/2014 às 15:03
  • 2
    +1 Apenas observe que - embora o uso de memória de fato seja menor - a performance em tempo costuma ser significativamente pior (Edit: em alguns ambientes mais, outros menos, pelo que observei).
    – mgibsonbr
    Commented 16/05/2014 às 15:50
4

Em JavaScript, as strings são imutáveis. Isso significa que - sempre que você tentar fazer uma substituição em uma string - uma nova string será criada com o resultado. Isso torna particularmente problemático implementar de forma eficiente algo como o String.replace, em especial se expressões regulares estão envolvidas.

Em teoria, pode-se melhorar isso usando arrays em vez de strings. Por exemplo, para se concatenar várias strings, acumule-as em um array e ao final junte-as usando o método join:

var arr = [];
for (var i = 0; i < 1000; i++) {
    arr.push(i.toString());
}
var myString = arr.join('');

Essa solução (que por sinal é a mesma estratégia usada pelo StringBuilder como sugerido na resposta do DBX8) infelizmente não é a ideal, já que JavaScript não possui um tipo de dados "caractere". Em vez disso, ao se fazer referência a um índice na string o que temos de volta é apenas outra string:

var str = "abc";
console.log(typeof str[1]); // string

Por essa razão, representar uma string como uma lista de "caracteres" (ou mesmo de code points, se usarmos números inteiros como elementos do array) dificilmente será mais eficiente em memória [ou em tempo]. Somente quando os "pedaços" são razoavelmente grandes é que se espera ter ganho de performance usando esse método (o que pode ou não ser verdade num caso de regex replace, dependendo do caso).

O que resta então é usar uma estrutura de mais baixo nível, como o Uint16Array. Ao se criar um array desse tipo (ArrayBuffer; existe em vários formatos) apenas uma cópia é mantida em memória. Pode-se modificá-lo à vontade que nenhuma cópia adicional é feita, embora tem-se que ter cuidado para não ultrapassar o limite de espaço ou coisas assim:

function stringParaBuffer(str) {
    var ret = new Uint16Array(str.length);
    for ( var i = 0 ; i < str.length ; i++ )
        ret[i] = str.charCodeAt(i);
    return ret;
}
function bufferParaString(arr) { return String.fromCharCode.apply(null, arr); }

var arr = stringParaBuffer("abc");  // Cria o buffer
arr[1] = "d".charCodeAt(0);         // Nenhuma cópia é feita
console.log(bufferParaString(arr)); // imprime: "adc"

arr[3] = "e".charCodeAt(0); // Falha silenciosamente, o array continua o mesmo

Essa solução, embora "crua", pode ser usada como base para a construção de algo mais sofisticado (como um StringBuilder que mantém registro do tamanho, se redimensiona à medida da necessidade, etc) que permita um regex replace sem uso excessivo de memória. Mas até o momento, que eu saiba, não há nenhuma biblioteca pronta fazendo uso disso não...

1
  • Adorei a ideia! Acredito que rodar expressões regulares nessa estrutura deve ser muito complexo, mas não impossível. Quero tentar algo do tipo agora :) Commented 16/05/2014 às 17:13

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 .