concatenación de cadenas lenta durante gran entrada

Question

He escrito un TAD árbol n-ario que funciona muy bien. Sin embargo, necesito para almacenar su serialización en una clase de un llamado variable. p.ej.

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

método que sirve para el propósito exactamente cómo lo necesito, pero en muy grandes entradas que se necesita para siempre (20 minutos en un archivo de 100 MB XML) que he escrito - He cronometrado los métodos y construir el árbol desde el archivo XML es rápida , pero llamar toString () como se muestra anteriormente es muy 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;    
    }
}

supongo que tiene que ver con la forma en que la cadena se construye en lugar de cómo se recorre el árbol? ¿Hay una mejor manera de hacer esto?

UPDATE: Siguiendo el ejemplo de Skaffman, el código siguiente dar OutOfMemoryError para muy grande de entrada

.

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

ACTUALIZACIÓN: Funciona perfectamente ahora, el uso de ejemplo Skaffmans

Answer 1

concats de cadenas como que son punishingly lento. Utilizar 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

No utilice la concatenación de cadenas en bucles. No escala.

El uso de StringBuilder, esto no hace que los objetos nuevos todo el tiempo, al igual que la concatenación de cadenas ..

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

}

Answer 3

Mira StringBuilder, no utilice concatenación simple, y pasar el StringBuilder a través de todo el proceso (o que sea un mundial).

Answer 4

Permítanme decir la razón de que la concatenación de cadenas es lento se debe a que las cadenas son inmutables. Esto significa que cada vez que escribe "+ =", se crea una nueva cadena. Esto significa que la manera en que construyen su cadena está en el peor de los casos, O (n ² ). Eso es porque si usted + = 'ed 1 carácter a la vez, el costo de la construcción de una nueva cadena sería 2 + 3 + 4 + ... + n, el cual es O (n ² ).

El uso de StringBuilder como otros a sugerir (el más lento, pero threadsafe StringBuffer).

supongo que debería añadir, StringBuilder te dará O (n) amortizado tiempo, ya que funciona como un vector detrás de las escenas, ya que es mutable. Así que construir su cadena de allí, y luego llamar a toString ().

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

También me gustaría añadir que este problema es similar en Python. El idioma en el pitón es anexar todas sus cuerdas para concatenar en una lista, y luego unirse a la lista. "".join(the_list).

ACTUALIZACIÓN: Como Bill señala, la concatenación no es la raíz de todos los males. Uno de concatenaciones de cadenas están muy bien, y puede incluso ser optimizado! (También son peor de los casos lineal). Pero, cuando se está concatenando en un bucle, ya que está por encima, el rendimiento va a cambiar drásticamente a medida que el número de iteraciones sube. En ese caso, mi análisis anterior es impecable, como ya he dicho específicamente que es "peor de los casos", lo que significa que no asumen ninguna optimizaciones. (Que la JVM no puede incluso optimizar la concatenación de bucles, así como pueda exterior).

Answer 5

Si un generador de perfiles confirma que el cuello de botella es la concatenación de cadenas tiene dos opciones:

• StringBuilder / StringBuffer (este último es más adecuado para el roscado)
• Cuerdas para Java :

  

Una cuerda es un reemplazo de alto rendimiento para cuerdas. La estructura de datos, que se describe en detalle en "cuerdas: una alternativa a los Strings", ofrece asintóticamente mejor rendimiento que tanto de cadena y StringBuffer para las modificaciones de cadena comunes como prepend, añadir, eliminar e insertar. Como cuerdas, cuerdas son inmutables y por lo tanto muy adecuado para su uso en multi-hilo de programación.

Answer 6

Es posible que desee mirar a String.intern () como una manera de reducir el consumo de memoria. Esto utilizará la cadena internado desde el grupo de cadena. Si tiene muchas cadenas duplicadas, que podría ser más rápido. Más información sobre las cadenas internadas aquí