Concatenazione di stringhe lente su input di grandi dimensioni

Question

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

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

Ho metodo che serve allo scopo esattamente come ho bisogno scritto, ma molto grandi ingressi ci vuole sempre (20 minuti su un file di 100 MB xml) - ho cronometrato i metodi e costruendo l'albero dal il file xml è veloce, ma chiamare 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 farlo?

AGGIORNAMENTO: Seguendo l'esempio di Skaffman, il seguente codice fornisce outOfMemoryError per un input molto 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(); 
    } 
} 

UPDATE: Funziona perfettamente ora, utilizzando Skaffmans esempio

Answer 1

Concorsi di stringhe del genere sono estremamente lenti. Utilizzare un oggetto 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

Guardate StringBuilder, non usare semplice concatenazione, e passare lo StringBuilder attraverso l'intero processo (o fare è globale).

Answer 3

Non utilizzare la concatenazione di stringhe nei loop. 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 4

si potrebbe desiderare di guardare String.intern() come un modo per ridurre l'utilizzo della memoria . Questo utilizzerà la stringa internata dal pool di stringhe. Se hai molte stringhe duplicate, potrebbe essere più veloce. Ulteriori informazioni sulle stringhe interne here

Answer 5

Lasciatemi dire che la concatenazione delle stringhe è lenta perché le stringhe sono immutabili. Ciò significa che ogni volta che scrivi "+ =", viene creata una nuova stringa. Ciò significa che il modo in cui crei la stringa è nel peggiore dei casi, O (n). Questo perché se hai + = 'ed un carattere alla volta, il costo di costruire una nuova stringa sarebbe 2 + 3 + 4 + ... + n, che è O (n).

Utilizzare StringBuilder come suggerito da altri (più lentamente, ma StringBuffer threadsafe).

Suppongo che dovrei aggiungere, StringBuilder ti darà O (n) tempo ammortizzato, perché funziona come un vettore dietro le quinte, dal momento che è mutabile. Quindi crea la tua stringa lì, quindi chiama 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 Python è quello di aggiungere tutte le stringhe per concatenare in un elenco e quindi unire l'elenco. "".join(the_list).

UPDATE: Come sottolinea Bill, la concatenazione non è la radice di tutti i mali. Le concatenazioni di una stringa fuori vanno bene e possono persino essere ottimizzate! (Sono anche nel caso peggiore lineare). Tuttavia, quando si concatena in un ciclo, come sopra, le prestazioni cambieranno drasticamente con l'aumento del numero di iterazioni. In tal caso, la mia analisi di cui sopra è impeccabile, come ho affermato in modo specifico che è "worst case", il che significa che non si assume alcuna ottimizzazione. (Che la JVM non è nemmeno in grado di ottimizzare la concatenazione in loop come può al di fuori).

Answer 6

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

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

Una corda è un sostituto ad alte prestazioni per stringhe. La struttura dei dati, descritta in dettaglio in "Corde: un'alternativa alle stringhe", fornisce prestazioni asintoticamente migliori rispetto a String e StringBuffer per le comuni modifiche alle stringhe come anteporre, aggiungere, eliminare e inserire. Come le stringhe, le corde sono immutabili e quindi ben si adattano all'uso nella programmazione multi-thread.