큰 입력에 대한 느린 문자열 연결

StackOverflow https://stackoverflow.com/questions/1126388

문제

나는 잘 작동하는 n-ary tree adt를 썼습니다. 그러나 직렬화를 변수 A 호출 클래스에 저장해야합니다. 예를 들어. 

    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 예제를 사용하여 지금 완벽하게 작동합니다

도움이 되었습니까?

해결책

그런 끈은 처벌 적으로 느린다. 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(")");
    }
}

다른 팁

루프에서 문자열 연결을 사용하지 마십시오. 확장되지 않습니다.

StringBuilder를 사용하십시오. 이것은 문자열 연결처럼 항상 새로운 객체를 만들지는 않습니다. 

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

}

StringBuilder를보고 간단한 연결을 사용하지 말고 전체 프로세스를 통해 StringBuilder를 전달하십시오 (또는 전 세계).

문자열 연결이 느린 이유는 줄이 불변이기 때문입니다. 이것은 "+="를 쓸 때마다 새 문자열이 생성된다는 것을 의미합니다. 이것은 당신이 당신의 줄을 쌓는 방법이 최악의 경우에 있다는 것을 의미합니다. o (n2). 한 번에 + = 'ed 1 char가된다면 새 문자열을 구축하는 데 드는 비용은 2 + 3 + 4 + ... + n이기 때문입니다.2).

StringBuilder를 다른 사람의 제안대로 사용하십시오 (느리게하지만 stressafe stringbuffer).

나는 내가 추가해야한다고 생각한다. StringBuilder는 당신에게 o (n) 상각 시간을 줄 것입니다. 왜냐하면 그것은 돌연변이가 있기 때문에 무대 뒤에서 벡터처럼 작동하기 때문입니다. 그래서 거기에 문자열을 만들고 toString ()을 호출하십시오.

StringBuilder builder = new StringBuilder();
builder.append("blah"); // append more as needed.
String text = builder.toString();

또한이 문제는 파이썬에서 비슷하다고 덧붙이고 싶습니다. 파이썬의 관용구는 모든 문자열에 목록에 연결하도록 한 다음 목록에 합류하는 것입니다. "".join(the_list).

업데이트: Bill이 지적한 바와 같이, 연결은 모든 악의 근본이 아닙니다. 하나의 오프 스트링 연결은 괜찮으며 최적화 될 수도 있습니다! (그들은 또한 최악의 선형입니다). 그러나, 당신이 루프에서 연결을 할 때, 당신이 위에있는 것처럼, 반복 횟수가 증가함에 따라 성능이 크게 바뀔 것입니다. 이 경우 위의 분석은 "최악의 경우"라고 언급했듯이 위의 분석은 완벽합니다. 이는 최적화가 없다고 가정합니다. (JVM은 루프의 연결을 최적화 할 수없고 외부에서 가능한 경우도 있습니다).

프로파일 러 인 경우 확인합니다 병목 현상이 문자열 연결이라는 것은 두 가지 선택이 있습니다.

로프는 문자열의 고성능 대체물입니다. "로프 : 문자열 대안"에 자세히 설명 된 Datafrsucture는 Prepend, Append, Delete 및 Insert와 같은 일반적인 문자열 수정을 위해 String과 StringBuffer보다 비대칭 적으로 더 나은 성능을 제공합니다. 문자열과 마찬가지로 로프는 불변이기 때문에 멀티 스레드 프로그래밍에 사용하기에 적합합니다.

당신은보고 싶을 수도 있습니다 String.intern () 메모리 사용을 줄이는 방법으로. 이것은 문자열 풀에서 인턴 된 문자열을 사용합니다. 복제 된 문자열이 많으면 더 빠를 수 있습니다. 인내 줄에 대한 자세한 정보 여기

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top