Concaténation de chaîne lente sur une grande entrée

Question

J'ai écrit un arbre ADT n-aire qui fonctionne correctement. Cependant, j'ai besoin de stocker sa sérialisation dans une variable d'une classe appelante. par exemple.

DomTree<String> a = Data.createTreeInstance("very_large_file.xml"); 
    String x = a.toString(); 

J'ai méthode écrit qui sert le but exactement comment j'ai besoin, mais sur les entrées très importantes, il prend une éternité (20min sur un fichier xml 100Mo) - J'ai chronométré les méthodes et la construction de l'arbre de la Le fichier xml est rapide, mais appeler toString() comme indiqué ci-dessus est très lent.

@Override 
public String toString(){ 
    return printTree(this); 
} 

public String printTree(AbstractTree<E> tree){ 
    if (tree.isLeaf()){ 
     return tree.getNodeName(); 
    }else{ 
     String tStr = tree.getNodeName() + "("; 

     int i = 0; 
     Iterator<AbstractTree<E>> child = tree.getChildren().iterator(); 
     while (i < tree.getChildren().size() - 1){ 

      tStr += printTree(child.next()) + ", "; 
      i++; 
     } 
     tStr += printTree(child.next()) + ")"; 

     return tStr;  
    } 
} 

Je suppose que cela est lié à la façon dont la chaîne est construite plutôt qu'à la façon dont l'arbre est traversé? Y a-t-il une meilleure manière de faire cela? MISE À JOUR: À l'instar de Skaffman, le code suivant donne outOfMemoryError pour une très grande entrée.

@Override 
public String toString(){ 
    StringBuilder buffer = new StringBuilder(); 
    printTree(this, buffer); 
    return buffer.toString(); 

}

public String printTree(AbstractTree<E> tree, StringBuilder buffer){ 
    if (tree.isLeaf()){ 
     return tree.getNodeName(); 
    }else{ 
     buffer.append(tree.getNodeName()); 
     buffer.append("("); 

     int i = 0; 
     Iterator<AbstractTree<E>> child = tree.getChildren().iterator(); 
     while (i < tree.getChildren().size() - 1){ 

      buffer.append(printTree(child.next(), buffer)); 
      buffer.append(", "); 
      i++; 
     } 
     buffer.append(printTree(child.next(), buffer)); 
     buffer.append(")"); 

     return buffer.toString(); 
    } 
} 

MISE À JOUR: Fonctionne parfaitement maintenant, en utilisant par exemple Skaffmans

Answer 1

Les enchaînements de cordes comme celui-ci sont terriblement lents. Utilisez un StringBuilder.

@Override 
public String toString(){ 
     StringBuilder buffer = new StringBuilder(); 
     printTree(this, buffer); 
     return buffer.toString(); 
} 

public void printTree(AbstractTree<E> tree, StringBuilder buffer){ 
    if (tree.isLeaf()){ 
     buffer.append(tree.getNodeName()); 
    } else { 
     buffer.append(tree.getNodeName()); 
     buffer.append("("); 

     int i = 0; 
     Iterator<AbstractTree<E>> child = tree.getChildren().iterator(); 
     while (i < tree.getChildren().size() - 1){ 
      printTree(child.next(), buffer); 
      buffer.append(", "); 
      i++; 
     } 
     printTree(child.next(), buffer); 
     buffer.append(")"); 
    } 
} 

Answer 2

Regardez StringBuilder, ne pas utiliser concaténation simple, et passer le StringBuilder à travers l'ensemble de votre processus (ou faire c'est un mondial).

Answer 3

N'utilisez pas la concaténation de chaînes dans les boucles. Ça ne va pas.

Utilisez StringBuilder, cela ne fait pas de nouveaux objets tout le temps, comme la concaténation de chaîne ..

void print() { 
StringBuilder sb = new StringBuilder(); 
sb.append("hello"); 
sb.append(" World!"); 
System.out.println(sb.toString()); 

}

Answer 4

Vous pourriez vouloir regarder String.intern() comme un moyen de réduire l'utilisation de la mémoire . Cela utilisera la chaîne interned à partir du pool de chaînes. Si vous avez beaucoup de chaînes dupliquées, cela pourrait être plus rapide. Plus d'informations sur les chaînes internes here

Answer 5

Laissez-moi vous dire que la concaténation de chaînes est lente parce que les chaînes sont immuables. Cela signifie que chaque fois que vous écrivez "+ =", une nouvelle chaîne est créée. Cela signifie que la façon dont vous construisez votre chaîne est dans le pire des cas, O (n). C'est parce que si vous + = 'ed 1 char à la fois, le coût de construction d'une nouvelle chaîne serait 2 + 3 + 4 + ... + n, qui est O (n).

Utilisez StringBuilder comme d'autres suggèrent (sur le StringBuffer plus lent, mais threadsafe).

Je suppose que je devrais ajouter, StringBuilder vous donnera O (n) temps amorti, car il fonctionne comme un vecteur dans les coulisses, car il est mutable. Alors construisez votre chaîne ici, puis appelez toString().

StringBuilder builder = new StringBuilder(); 
builder.append("blah"); // append more as needed. 
String text = builder.toString(); 

Je voudrais également ajouter que ce problème est similaire en Python. L'idiome dans python est d'ajouter toutes vos chaînes à concaténer dans une liste, puis rejoindre la liste. "".join(the_list).Comme le fait remarquer Bill, la concaténation n'est pas la racine de tous les maux. Les enchaînements de chaînes sont parfaits et peuvent même être optimisés! (Ils sont aussi le cas le plus linéaire). Mais, lorsque vous êtes en train de concaténer, comme vous le voyez ci-dessus, la performance va changer radicalement au fur et à mesure que le nombre d'itérations augmente. Dans ce cas, mon analyse ci-dessus est sans faille, comme je l'ai spécifiquement dit, c'est le «pire des cas», ce qui signifie que vous n'optimisez pas. (La JVM ne peut même pas optimiser la concaténation dans les boucles aussi bien qu'elle le peut à l'extérieur).

Answer 6

Si un profileur confirme vous que le goulot d'étranglement est concaténation de chaîne que vous avez deux choix:

• StringBuilder/StringBuffer (ce dernier est mieux adapté pour le filetage)
• Ropes for Java:

Une corde est un remplacement de haute performance pour les cordes. La structure de données, décrite en détail dans "Cordes: une alternative aux cordes", offre des performances asymptotiquement meilleures que String et StringBuffer pour les modifications de chaînes courantes telles que prepend, append, delete et insert. Comme les cordes, les cordes sont immuables et donc parfaitement adaptées à la programmation multi-thread.