大输入上的慢字符串连接

Question

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

    DomTree<String> 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<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

让我说字符串连接很慢的原因是因为字符串是不可变的。这意味着每次你写“+=”时，都会创建一个新的字符串。这意味着您构建字符串的方式是在最坏的情况下，O(n ² )。那是因为如果您一次 +='ed 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 甚至无法优化循环中的连接以及它可以在外部）。