concatenação lenta ao longo de grande entrada

Question

Eu escrevi um TAD árvore n-ária que funciona bem. No entanto, eu preciso armazenar sua serialização em uma variável de uma classe chamada. por exemplo.

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

Eu tenho método que serve o propósito exatamente como eu preciso dele escrito, mas em grandes entradas que leva uma eternidade (20min em um arquivo de 100MB xml) - Eu cronometrado os métodos e construir a árvore do arquivo xml é rápido , mas chamar toString () como mostrado acima é muito 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;    
    }
}

Eu estou supondo que tem a ver com a forma como a corda é construída ao invés de como a árvore é atravessada? Existe uma maneira melhor de fazer isso?

UPDATE:. Seguindo o exemplo de skaffman, a seguinte OutOfMemoryError Fornecer código para entrada muito 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: funciona perfeitamente agora, usando Skaffmans exemplo

Answer 1

concats corda como essa são punishingly lento. Use um 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

Não use concatenação em loops. Ele não escala.

Use StringBuilder, isso não faz novos objetos o tempo todo, como concatenação ..

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

}

Answer 3

Olhe para StringBuilder, não use concatenação simples, e passar o StringBuilder através de todo o seu processo (ou torná-lo um global).

Answer 4

Deixe-me dizer a razão que concatenação é lento porque strings são imutáveis. Isso significa que cada vez que você escrever "+ =", um novo String é criado. Isto significa que a maneira como você construir a sua corda está no pior caso, O (n ² ). Isso porque se você + = 'ed 1 caractere de cada vez, o custo de construção de uma nova cadeia seria 2 + 3 + 4 + ... + n, que é O (n ² ).

Use StringBuilder como outros de sugerir (sobre o mais lento, mas threadsafe StringBuffer).

Acho que eu deveria adicionar, StringBuilder lhe dará O (n) amortizados tempo, porque ele funciona como um vetor nos bastidores, uma vez que é mutável. Então, construir a sua corda lá, e depois chamar toString ().

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

Eu também gostaria de acrescentar que este problema é semelhante em Python. O idioma em python é acrescentar todas as suas cordas para concatenar em uma lista e, em seguida, entrar na lista. "".join(the_list).

UPDATE: Como Bill aponta, a concatenação não é a raiz de todo o mal. Um fora concatenations cordas estão bem, e pode até ser otimizado! (Eles também são pior linear caso). Mas, quando você está concatenando em um loop, como você está acima, o desempenho vai mudar drasticamente como o número de iterações sobe. Nesse caso, a minha análise acima é impecável, como eu disse especificamente que é "pior caso", o que significa que não assumem otimizações. (Que a JVM não pode ainda otimizar a concatenação em loops, bem como o possível fora).

Answer 5

Se um profiler confirma que o gargalo é concatenação você tem duas escolhas:

• StringBuilder / StringBuffer (este último é mais adequado para rosqueamento)
• cordas para Java :

Uma corda é um substituto alto desempenho para Strings. A estrutura de dados, descrito em detalhes em "Ropes: uma alternativa para Cordas", fornece assintoticamente melhor desempenho do que tanto de Cordas e StringBuffer para modificações cordas comuns, como preceder, acrescentar, apagar e inserção. Como cordas, cordas são imutáveis ??e, portanto, bem adequado para uso em programação multi-thread.

Answer 6

Você pode querer olhar para String.intern () como uma forma de reduzir o uso de memória. Isto irá usar a string internado da piscina string. Se você tem muitas cordas duplicados, pode ser mais rápido. Mais informações sobre internados cordas aqui