Lento stringa concatenazione sopra il grande ingresso

Question

Ho scritto un albero n-ario ADT che funziona bene. Tuttavia, ho bisogno di memorizzare la sua serializzazione in una classe di una chiamata variabile. per esempio.

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

Ho metodo che serve allo scopo esattamente come ne ho bisogno, ma molto grandi ingressi ci vuole per sempre (20 minuti su un file di 100 MB xml) scritto - ho cronometrato i metodi e costruendo l'albero dal file XML è veloce , ma chiamando toString () come mostrato sopra è molto lento.

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

Sto indovinando che è a che fare con il modo in cui la corda è costruito, piuttosto che come l'albero viene attraversato? C'è un modo migliore per fare questo?

UPDATE: Seguendo l'esempio Skaffman, il seguente codice dare OutOfMemoryError per molto grande ingresso

.

@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: Funziona perfettamente ora, utilizzando Skaffmans esempio

Answer 1

concats stringa del genere sono punishingly lento. Utilizzare uno 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

Non utilizzare concatenazione di stringhe in loop. E non scala.

Usa StringBuilder, questo non rende nuovi oggetti per tutto il tempo, come concatenazione di stringhe ..

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

}

Answer 3

Guarda StringBuilder, non usare semplice concatenazione, e passare lo StringBuilder attraverso l'intero processo (o renderlo un globale).

Answer 4

Lasciatemi dire il motivo per cui concatenazione di stringhe è lento perché le stringhe sono immutabili. Questo significa che ogni volta che si scrive "+ =", viene creata una nuova stringa. Questo significa che il modo in cui si costruisce la stringa è nel caso peggiore, O (n ² ). Questo perché se si + = 'ED 1 carattere alla volta, il costo di costruzione di una nuova stringa sarebbe 2 + 3 + 4 + ... + n, che è O (n ² ).

Usa StringBuilder come altre del suggeriscono (oltre il più lento, ma threadsafe StringBuffer).

Credo che dovrei aggiungere, StringBuilder vi darà O (n) ammortizzato tempo, visto che funziona come un vettore dietro le quinte, dal momento che è mutevole. Quindi costruire la vostra stringa di lì, e quindi chiamare toString ().

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

Vorrei anche aggiungere che questo problema è simile in Python. L'idioma in pitone è di aggiungere tutte le stringhe per concatenare in una lista, e poi unirsi alla lista. "".join(the_list).

UPDATE: Come Bill fa notare, la concatenazione non è la radice di tutti i mali. One off concatenazioni di stringhe vanno bene, e può anche essere ottimizzato! (Essi sono anche peggiori caso lineare). Ma, quando si è concatenato in un ciclo, come si è sopra, le prestazioni saranno drasticamente cambiare il numero di iterazioni aumenta. In tal caso, la mia analisi di cui sopra è impeccabile, come ho espressamente dichiarato che è "caso peggiore", il che significa che si assume nessuna ottimizzazione. (Il che la JVM non può nemmeno di ottimizzare la concatenazione di cicli così come il possibile al di fuori).

Answer 5

Se un profiler conferma che il collo di bottiglia è concatenazione di stringhe si hanno due scelte:

• StringBuilder / StringBuffer (quest'ultimo è più adatto per filettatura)
• Corde per Java :

  

Una corda è un sostituto ad alte prestazioni per archi. Il datastructure, descritto in dettaglio nella sezione "Corde: un'alternativa al Strings", fornisce prestazioni migliori rispetto asintoticamente sia String e StringBuffer per le modifiche della stringa comuni come anteporre, aggiungere, eliminare, e l'inserimento. Come corde, funi sono immutabili e quindi particolarmente adatto per l'uso in multi-threaded programmazione.

Answer 6

Si potrebbe desiderare di guardare String.Intern () come un modo per ridurre l'uso della memoria. Questo utilizzerà lo String internato dal pool di stringa. Se si dispone di molte stringhe duplicate, potrebbe essere più veloce. Maggiori informazioni sulle stringhe internate qui