Java Language Pitfall - La concaténation de chaînes dans une boucle ne s'adapte pas


Exemple

Considérez le code suivant comme illustration:

public String joinWords(List<String> words) {
    String message = "";
    for (String word : words) {
        message = message + " " + word;
    }
    return message;
}

Malheureusement, ce code est inefficace si la liste de words est longue. La racine du problème est cette déclaration:

message = message + " " + word;

Pour chaque itération de boucle, cette instruction crée une nouvelle chaîne de message contenant une copie de tous les caractères de la chaîne de message origine avec des caractères supplémentaires. Cela génère beaucoup de chaînes temporaires et fait beaucoup de copie.

Lorsque nous analysons joinWords , en supposant qu'il y ait N mots avec une longueur moyenne de M, nous trouvons que O (N) chaînes temporaires sont créées et que O (MN 2 ) caractères seront copiés dans le processus. La composante N 2 est particulièrement préoccupante.

L'approche recommandée pour ce type de problème 1 consiste à utiliser un StringBuilder au lieu de la concaténation de chaîne comme suit:

public String joinWords2(List<String> words) {
    StringBuilder message = new StringBuilder();
    for (String word : words) {
        message.append(" ").append(word);
    }
    return message.toString();
}

L'analyse de joinWords2 doit prendre en compte les frais généraux joinWords2 à la "croissance" du tableau de commandes StringBuilder qui contient les caractères du générateur. Cependant, il s'avère que le nombre de nouveaux objets créés est O (logN) et que le nombre de caractères copiés est O (MN). Ce dernier inclut les caractères copiés dans l’appel toString() final.

(Il est peut-être possible d’optimiser ce réglage en créant le StringBuilder avec la capacité correcte pour commencer. Cependant, la complexité globale reste la même.)

En revenant à la méthode joinWords origine, il s'avère que la déclaration critique sera optimisée par un compilateur Java typique en quelque chose comme ceci:

  StringBuilder tmp = new StringBuilder();
  tmp.append(message).append(" ").append(word);
  message = tmp.toString();

Cependant, le compilateur Java ne "retirera" pas le StringBuilder de la boucle, comme nous l'avons fait à la main dans le code de joinWords2 .

Référence:


1 - Dans Java 8 et Joiner ultérieures, la classe Joiner peut être utilisée pour résoudre ce problème particulier. Cependant, ce n'est pas ce que cet exemple est vraiment censé être .