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

Я написал 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.