Медленная конкатенация строк на большом входе

Question

Я написал n-арное дерево ADT, которое отлично работает. Однако мне нужно хранить его сериализацию в переменной вызывающего класса. например.

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

Я написал метод, который служит цели именно так, как мне нужно, но на очень больших входах это занимает вечность (20 минут для файла XML объемом 100 МБ) - я рассчитал методы и построил дерево из файла XML быстро , но вызов toString (), как показано выше, очень медленный.

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

Я предполагаю, что это связано с тем, как строится строка, а не с тем, как обходится дерево? Есть ли лучший способ сделать это?

ОБНОВЛЕНИЕ: Следуя примеру Skaffman, следующий код выдаетOfMemoryError для очень большого ввода.

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

ОБНОВЛЕНИЕ: теперь работает отлично, на примере Skaffmans

Answer 1

Конкаты строк, как это, карательно медленны. Используйте 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

Не используйте конкатенацию строк в циклах. Не масштабируется.

Используйте StringBuilder, это не создает новые объекты все время, как конкатенация строк ..

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

}

Answer 3

Позвольте мне сказать, что причина медленной конкатенации строк в том, что строки неизменяемы. Это означает, что каждый раз, когда вы пишете «+ =», создается новая строка. Это означает, что способ построения вашей строки в худшем случае, O (n ² ). Это потому, что если вы + = 'ed 1 char за раз, стоимость построения новой строки будет 2 + 3 + 4 + ... + n, что равно O (n ² ).

Используйте StringBuilder как совет для других (более медленный, но поточно-безопасный StringBuffer).

Полагаю, мне следует добавить, что StringBuilder даст вам амортизированное время O (n), потому что оно работает как закулисный вектор, поскольку оно изменчиво. Поэтому создайте свою строку там, а затем вызовите toString ().

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

Я также хотел бы добавить, что эта проблема похожа на Python. В Python идиома состоит в том, чтобы добавить все ваши строки для объединения в список, а затем присоединиться к списку. "".join(the_list).

ОБНОВЛЕНИЕ: Как указывает Билл, конкатенация не является корнем всего зла. Одна конкатенация строк хорошо, и даже может быть оптимизирована! (Они также линейные в худшем случае). Но когда вы выполняете конкатенацию в цикле, как и выше, производительность резко меняется с увеличением количества итераций. В этом случае мой анализ выше безупречен, так как я специально заявил, что это «худший случай», что означает, что вы не предполагаете оптимизацию. (Что JVM не может даже оптимизировать конкатенацию в циклах так же хорошо, как вне).

Answer 4

Посмотрите на StringBuilder, не используйте простую конкатенацию и передайте StringBuilder через весь процесс (или сделайте его глобальным).

Answer 5

Если профилировщик подтверждает , что узким местом является конкатенация строк, у вас есть два варианта:

• StringBuilder / StringBuffer (последний лучше подходит для многопоточности)
• Канаты для Java :

Веревка - это высокопроизводительная замена струн. Структура данных, подробно описанная в разделе «Веревки: альтернатива строкам», обеспечивает асимптотически лучшую производительность, чем String и StringBuffer, для таких распространенных модификаций строк, как prepend, append, delete и insert. Как и строки, веревки являются неизменными и поэтому хорошо подходят для использования в многопоточном программировании.

Answer 6

Возможно, вы захотите посмотреть на String.intern () , чтобы сократить использование памяти. Это будет использовать интернированную строку из пула строк. Если у вас много дублирующихся строк, это может быть быстрее. Подробнее об интернированных строках здесь