Langsame String-Verkettung über großen Eingang

Question

Ich habe einen n-ary Baum ADT geschrieben, der gut arbeitet. Ich brauche aber seine Serialisierung in einer Variablen einer Berufung Klasse zu speichern. z.B.

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

I Methode geschrieben haben, die den Zweck genau dient, wie ich es brauchen, aber auf sehr großen Eingängen es dauert ewig (20 Minuten auf einer 100MB xml-Datei) - Ich habe die Methoden zeitlich und den Baum aus der XML-Datei Aufbau ist schnell , sondern ruft toString (), wie oben gezeigt, ist sehr langsam.

@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;    
    }
}

Ich vermute, es mit der Art und Weise zu tun, ist der String aufgebaut wird und nicht, wie der Baum durchlaufen wird? Gibt es einen besseren Weg, dies zu tun?

UPDATE: Nach dem Beispiel Skaffman, der folgende Code geben OutOfMemoryError für sehr großen Eingang

.

@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();   
    }
}

UPDATE: Funktioniert perfekt jetzt, mit Skaffmans Beispiel

Answer 1

String concats so sind punishingly langsam. Verwenden Sie einen String.

@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

Sie String-Verkettung nicht in Schleifen verwenden. Es ist nicht skaliert werden.

Verwenden String, dies nicht machen neue Objekte die ganze Zeit, wie die String-Verkettung ..

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

}

Answer 3

Schauen Sie sich String, verwenden Sie nicht einfach Verkettung und die String durch den gesamten Prozess übergeben (oder es sich um eine globale machen).

Answer 4

Lassen Sie uns sagen, dass der Grund dafür, dass die String-Verkettung langsam ist, weil Strings unveränderlich sind. Das bedeutet, jedes Mal wenn Sie „+ =“ eine neue String schreiben wird erstellt. Dies bedeutet, dass die Art und Weise Sie Ihre Zeichenfolge aufzubauen ist im schlimmsten Fall O (n ² ). Das ist, weil, wenn Sie + = 'ed 1 Zeichen in einer Zeit, die Kosten für eine neue Zeichenfolge zu bauen wären, 2 + 3 + 4 + ... + n, die O (n ² ) ist.

Verwenden Stringbuilder als andere vorschlagen (über die langsameren, aber THREADString).

Ich glaube, ich sollte hinzufügen, String geben Ihnen O (n) Zeit amortisiert, weil es wie ein Vektor hinter den Kulissen arbeitet, da es wandelbar ist. So bauen dort die Zeichenfolge, und dann rufen Sie toString ().

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

Ich möchte auch hinzufügen, dass dieses Problem in Python ähnlich ist. Das Idiom in Python ist es, alle Strings anhängen in eine Liste verketten, und dann die Liste beizutreten. "".join(the_list).

UPDATE: Wie Bill weist darauf hin, Verkettung nicht die Wurzel allen Übels ist. Ein off-String Verkettungen sind in Ordnung und sogar optimiert werden kann! (Sie sind auch schlimmster Fall linear). Aber, wenn Sie in einer Schleife verketten, wie Sie oben sind, wird drastisch die Leistung ändern, da die Anzahl der Iterationen steigt. In diesem Fall ist meine obige Analyse einwandfrei, wie ich es ausdrücklich angegeben ist „worst case“, das bedeutet, dass Sie keine Optimierungen übernehmen. (Die die JVM kann nicht einmal die Verkettung in Schleifen optimieren sowie es kann außen).

Answer 5

Wenn ein Profiler bestätigt Sie, dass der Engpass ist die String-Verkettung Sie haben zwei Möglichkeiten:

• String / Stringbuffer (letzteres ist besser geeignet zum Einfädeln)
• Seile für Java :

  

Ein Seil ist ein Hochleistungs-Ersatz für Streicher. Die Datenstruktur, die im Detail in „Ropes: eine Alternative zu Strings“ beschrieben, stellt asymptotisch bessere Leistung als sowohl String und Stringbuffer für die gemeinsame Zeichenfolge Modifikationen wie prepend, hängen, löschen und einzufügen. Wie Strings, sind Seile unveränderlich und daher gut geeignet für den Einsatz in Multi-Threaded-Programmierung.

Answer 6

Sie können unter String.intern () als eine Möglichkeit, auf die Speichernutzung zu reduzieren. Dies wird die internierten String aus dem String-Pool verwenden. Wenn Sie viele duplizierte Zeichenfolgen haben, kann es schneller sein. Weitere Informationen über internierten Strings hier