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

Question

J'ai écrit un arbre n-aire ADT qui fonctionne très bien. Cependant, je dois stocker ses sérialisation dans une classe d'appel variable. 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 faut toujours (20min sur un fichier xml 100Mo) - J'ai chronométré les méthodes et la construction de l'arbre à partir du fichier xml est rapide , mais appelant 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 c'est de faire de la façon dont la chaîne est construit plutôt que de la façon dont l'arbre est traversée? Y at-il une meilleure façon de le faire?

MISE À JOUR: A l'instar de Skaffman, le code suivant donne OutOfMemoryError pour une entrée très grande

.

@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

chaîne concats comme ça sont punishingly 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

Ne pas utiliser concaténation de chaînes dans les boucles. Il n'échelle.

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 3

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

Answer 4

Permettez-moi de dire la raison pour laquelle la concaténation de chaîne 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 ² ). En effet, si vous + = 'ed 1 caractère à la fois, le coût de la construction d'une nouvelle chaîne serait 2 + 3 + 4 + ... + n, qui est O (n ² ).

Utilisez StringBuilder que d'autres suggèrent de (sur le ralentissement, mais threadsafe StringBuffer).

Je suppose que je devrais ajouter, StringBuilder vous donnera O (n) après amortissement, car il fonctionne comme un vecteur dans les coulisses, car il est mutable. Donc, construire votre chaîne là-bas, puis appelez toString ().

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

Je voudrais aussi ajouter que ce problème est similaire en Python. L'idiome en python est d'ajouter toutes vos chaînes à concaténer dans une liste, puis se joindre à la liste. "".join(the_list).

Mise à jour: Comme le projet de loi souligne, concaténation est pas la racine de tous les maux. Un hors concaténations de chaînes sont très bien, et peut même être optimisé! (Ils sont aussi pire des cas linéaire). Mais, lorsque vous concaténez dans une boucle, comme vous êtes au-dessus, la performance va considérablement changer le nombre d'itérations monte. Dans ce cas, mon analyse ci-dessus est impeccable, comme je l'ai dit plus particulièrement qu'il est « pire des cas », ce qui signifie que vous assumez aucune optimisation. (La machine virtuelle Java qui ne peut même optimiser la concaténation dans les boucles aussi bien qu'il peut à l'extérieur).

Answer 5

Si un profileur vous confirme 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)
• Cordes pour Java :

  

Une corde est un remplacement de haute performance pour les chaînes. La structure de données, décrit en détail dans « Cordes: une alternative à cordes », fournit asymptotiquement de meilleures performances que les deux cordes et StringBuffer pour les modifications de chaîne communes comme préajouter append, supprimer et insérer. Comme les chaînes, les cordes sont immuables et donc bien adapté pour une utilisation dans la programmation multi-thread.

Answer 6

Vous voudrez peut-être regarder String.intern () comme un moyen de réduire la consommation de mémoire. Cela utilisera la chaîne internées de la piscine de chaîne. Si vous avez beaucoup de chaînes dupliquées, il pourrait être plus rapide. Plus d'informations sur les chaînes internées