Quantas strings são criadas na memória ao concatenar strings em Java?

17

Me perguntaram sobre strings imutáveis ​​em Java. Fui encarregado de escrever uma função que concatenou um número de "a" s em uma string.

O que eu escrevi:

public String foo(int n) {
    String s = "";
    for (int i = 0; i < n; i++) {
        s = s + "a"
    }
    return s;
}

Perguntaram-me quantas seqüências de caracteres esse programa geraria, assumindo que a coleta de lixo não ocorra. Meus pensamentos para n = 3 foram

  1. ""
  2. "uma"
  3. "uma"
  4. "aa"
  5. "uma"
  6. "aaa"
  7. "uma"

Essencialmente, duas strings são criadas em cada iteração do loop. No entanto, a resposta foi n 2 . Quais seqüências de caracteres serão criadas na memória por essa função e por que é assim?

ahalbert
fonte
15
Se você se ofereceu este trabalho, fugir, correr muito rápido .......
mattnz
@mattnz por várias razões (e não apenas por causa do código escrito).
3
Isso leva tempo de execução O (n ^ 2), a menos que o JIT otimize o loop, mas não cria n ^ 2 strings.
User2357112 suporta Monica

Respostas:

26

Perguntaram-me quantas seqüências de caracteres esse programa geraria, assumindo que a coleta de lixo não ocorra. Meus pensamentos para n = 3 foram (7)

As strings 1 ( "") e 2 ( "a") são as constantes do programa, elas não são criadas como parte das coisas, mas são 'internadas' porque são constantes que o compilador conhece. Leia mais sobre isso em String interning na Wikipedia.

Isso também remove as seqüências 5 e 7 da contagem, pois são as mesmas "a"que a seqüência 2. Isso deixa as seqüências 3, 4 e 6. A resposta é "3 cadeias são criadas para n = 3" usando seu código.

A contagem de n 2 está obviamente errada, porque em n = 3, isso seria 9 e, até mesmo, na sua pior resposta, isso era apenas 7. Se suas seqüências não internadas estavam corretas, a resposta deveria ser 2n + 1.

Então, a questão de como você deve fazer isso?

Como a String é imutável , você deseja algo mutável - algo que pode ser alterado sem criar novos objetos. Esse é o StringBuilder .

A primeira coisa a olhar são os construtores. Nesse caso, sabemos quanto tempo a string será e existe um construtor StringBuilder(int capacity) que significa que alocamos exatamente o quanto precisamos.

Em seguida, "a"não precisa ser uma String , mas pode ser um personagem 'a'. Isso tem um pequeno aumento no desempenho ao chamar append(String)vs append(char)- com o append(String), o método precisa descobrir quanto tempo a String é e fazer algum trabalho nisso. Por outro lado, charsempre tem exatamente um caractere.

As diferenças de código podem ser vistas em StringBuilder.append (String) vs StringBuilder.append (char) . Não é algo para se preocupar muito , mas se você estiver tentando impressionar o empregador, é melhor usar as melhores práticas possíveis.

Então, como fica isso quando você o reúne?

public String foo(int n) {
    StringBuilder sb = new StringBuilder(n);
    for (int i = 0; i < n; i++) {
        sb.append('a');
    }
    return sb.toString();
}

Um StringBuilder e um String foram criados. Nenhuma string extra precisava ser internada.


Escreva alguns outros programas simples no Eclipse. Instale o pmd e execute-o no código que você escreve. Observe o que se queixa e corrija essas coisas. Teria encontrado a modificação de uma String com + em um loop, e se você a alterasse para StringBuilder, talvez tivesse encontrado a capacidade inicial, mas certamente perceberia a diferença entre .append("a")e.append('a')

Comunidade
fonte
9

Em cada iteração, um novo Stringé criado pelo +operador e atribuído a s. Após o retorno, todos eles, exceto o último, são coletados no lixo.

As constantes de string gostam ""e "a"não são criadas sempre, são cadeias internas . Como as cordas são imutáveis, elas podem ser compartilhadas livremente; isso acontece com constantes de string.

Para concatenar seqüências de caracteres com eficiência, use StringBuilder.

9000
fonte
As pessoas na entrevista realmente debateram se o literal era ou não e decidiram que os literais eram criados todas as vezes. Mas isso faz mais sentido.
Ahalbert #
6
Como você "debate" que uma língua faz, certamente você ler a especificação e saber com certeza, ou não é definido e, portanto, não há nenhuma resposta correta .....
mattnz
@mattnz Pode ser interessante saber o que o compilador / tempo de execução que você está usando faz, mesmo quando se trata de detalhes de implementação. Isso se aplica especialmente ao desempenho.
svick
1
@svick: Você pode ganhar muito fazendo suposições, depois o compilador é atualizado, uma otimização alterada etc. O comportamento muda causando bugs porque você confiou no comportamento não especificado, e não no comportamento definido. Você sabe o que eles dizem sobre otimização - a) deixe para especialistas eb) você ainda não é especialista. :) Se a confiança é baseada apenas no desempenho, mas ainda na especificação de idioma, você perde apenas o desempenho. Muitas vezes, vi códigos que se baseavam em comportamentos não especificados ou específicos do compilador de maneiras inesperadas (principalmente C e C ++).
mattnz
@mattnz Então, como você propõe tomar decisões relacionadas ao desempenho? Normalmente, o melhor que você pode obter com a especificação / documentação são as complexidades do grande O, mas isso não é suficiente. De qualquer forma, o desempenho sempre dependerá da implementação, por isso acho que é bom confiar nos detalhes da implementação quando se trata de desempenho.
svick
4

Como MichaelT explica em sua resposta, seu código aloca O (n) strings. Mas também aloca O (n 2 ) bytes de memória e é executado no tempo O (n 2 ).

Aloca O (n 2 ) bytes, porque as seqüências que você está alocando têm comprimentos 0, 1, 2,…, n-1, n, que soma (n 2 + n) / 2 = O (n 2 ).

O tempo também é O (n 2 ), porque a alocação da i-ésima sequência requer a cópia da (i-1) -ésima sequência, que tem o comprimento i-1. Isso significa que cada byte alocado deve ser copiado, o que levará tempo O (n 2 ).

Talvez seja isso que os entrevistadores quiseram dizer?

svick
fonte
A equação não deveria ser (n ^ 2 + n) / 2, como aqui ?
heyjude