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

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

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

Я написал метод, который служит цели именно в том, как мне это нужно, но на очень больших входах, которые он принимает навсегда (20 минут на 100 МБ xml файле). Я приурочил методы и построил дерево из 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; }
}
</abstracttree<e></e>

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

ОБНОВЛЕНИЕ. Следуя примеру 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(); }
}
</abstracttree<e></e>

UPDATE: теперь работает отлично, используя пример Skaffmans

6 ответов

String concats вроде этого карательно медленны. Используйте 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(")"); }
}
</abstracttree<e></e>


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

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

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

}


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

Используйте 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 не может даже оптимизировать конкатенацию в циклах, а также может выйти наружу).


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


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

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

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


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

licensed under cc by-sa 3.0 with attribution.