7

我写了一个工作正常的 n 叉树 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 示例

4

6 回答 6

17

像这样的字符串连接非常慢。使用 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(")");
    }
}
于 2009-07-14T16:04:12.100 回答
6

不要在循环中使用字符串连接。它不缩放。

使用 StringBuilder，这不会一直创建新对象，例如字符串连接..

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

}

于 2009-07-14T16:04:16.343 回答
5

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

于 2009-07-14T16:15:31.470 回答
3

查看 StringBuilder，不要使用简单的连接，将 StringBuilder 传递给您的整个过程（或使其成为全局）。

于 2009-07-14T16:03:25.813 回答
2

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

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

绳索是弦乐的高性能替代品。在“Ropes: an Alternative to Strings”中详细描述的数据结构，对于常见的字符串修改（例如 prepend、append、delete 和 insert）提供了比 String 和 StringBuffer 更好的性能。与字符串一样，绳索是不可变的，因此非常适合用于多线程编程。

于 2009-07-14T16:20:21.303 回答
-1

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

于 2009-07-14T16:14:46.180 回答