大输入上的慢字符串连接

我写了一个n-ary树ADT工作正常。 但是，我需要将其序列化存储在一个变量调用类中。 例如。

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

我编写的方法完全符合我的需要，但在非常大的输入上它需要永远（在100MB xml文件上20分钟） – 我已经定时方法并从xml文件构建树很快，但是调用如上所示的toString（）非常慢。

 @Override public String toString(){ return printTree(this); } public String printTree(AbstractTree tree){ if (tree.isLeaf()){ return tree.getNodeName(); }else{ String tStr = tree.getNodeName() + "("; int i = 0; Iterator<AbstractTree> 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 tree, StringBuilder buffer){ if (tree.isLeaf()){ return tree.getNodeName(); }else{ buffer.append(tree.getNodeName()); buffer.append("("); int i = 0; Iterator<AbstractTree> 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 tree, StringBuilder buffer){ if (tree.isLeaf()){ buffer.append(tree.getNodeName()); } else { buffer.append(tree.getNodeName()); buffer.append("("); int i = 0; Iterator> 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

让我说字符串连接缓慢的原因是因为字符串是不可变的。 这意味着每次编写“+ =”时，都会创建一个新的String。 这意味着你构建字符串的方式是最坏的情况，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 5

如果探查器确认您的瓶颈是字符串连接，则您有两种选择：

• StringBuilder / StringBuffer（后者更适合线程化）
• Java的绳索 ：

绳索是Strings的高性能替代品。 “绳索：字符串的替代”中详细描述的数据结构提供了比String和StringBuffer渐近更好的性能，用于常见的字符串修改，如prepend，append，delete和insert。 与Strings一样，绳索是不可变的，因此非常适合用于multithreading编程。

Answer 6

您可能希望将String.intern（）视为减少内存使用的一种方法。 这将使用字符串池中的interned String。 如果您有许多重复的字符串，它可能会更快。 关于实习字符串的更多信息