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

Question

Я написал n-ary tree 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, следующий код выдает OutOfMemoryError для очень больших входных данных.

@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

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

Answer 4

Позвольте мне сказать, что причина, по которой конкатенация строк происходит медленно, заключается в том, что строки неизменяемы.Это означает, что каждый раз, когда вы пишете "+=", создается новая строка.Это означает, что способ, которым вы создаете свою строку, в наихудшем случае, O (n²).Это потому, что если вы +='редактируете по 1 символу за раз, стоимость создания новой строки будет равна 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 5

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

• StringBuilder /StringBuffer (последний лучше подходит для обработки потоков)
• Веревки для Java:

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

Answer 6

Возможно, вы захотите взглянуть на Строка.стажер() как способ сократить использование памяти.При этом будет использоваться интернированная строка из пула строк.Если у вас много дублированных строк, это может быть быстрее.Дополнительная информация о интернированных строках здесь