大输入上的慢字符串连接 [英] Slow string concatenation over large input

问题描述

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

I've written an n-ary tree ADT which works fine. However, I need to store its serialization in a variable a calling class. eg.

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

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

I've written method which serves the purpose exactly how I need it, but on very large inputs it takes forever (20mins on a 100MB xml file) - I have timed the methods and building the tree from the xml file is quick, but calling toString() as shown above is very slow.

@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;    
    }
}

我猜它是这样做的是否构建了字符串而不是遍历树的方式？有没有更好的方法呢？

I'm guessing it is to do with the way the string is built up rather than how the tree is traversed? Is there a better way to do this?

更新：以Skaffman为例，下面的代码为非常大的输入提供outOfMemoryError。

UPDATE: Following the example of Skaffman, the following code give outOfMemoryError for very large input.

@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示例完美工作

UPDATE: Works perfectly now, using Skaffmans example

推荐答案

这样的字符串连接速度非常慢。使用StringBuilder。

String concats like that are punishingly slow. Use a 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(")");
    }
}

这篇关于大输入上的慢字符串连接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！