Nối chuỗi chậm trên đầu vào lớn

Question

Tôi đã viết một cây ADT n-ary hoạt động tốt. Tuy nhiên, tôi cần phải lưu trữ serialization của nó trong một biến một lớp gọi điện thoại. ví dụ.

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

Tôi đã viết phương pháp phục vụ mục đích chính xác làm thế nào tôi cần đến nó, nhưng đầu vào rất lớn nó sẽ mãi mãi (20 phút trên một tập tin 100MB xml) - Tôi đã timed các phương pháp và xây dựng cây từ Tệp xml là nhanh, nhưng gọi toString() như được hiển thị ở trên là rất chậm.

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

Tôi đoán nó là để làm với cách chuỗi được xây dựng chứ không phải như thế nào cây được đi qua? Có cách nào tốt hơn để làm điều này?

CẬP NHẬT: Theo ví dụ về Skaffman, mã sau cung cấp cho outOfMemoryError cho đầu vào rất lớn.

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

UPDATE: Tác phẩm hoàn hảo bây giờ, sử dụng Skaffmans dụ

Answer 1

Các chuỗi trùng lặp như vậy có vẻ chậm chạp. Sử dụng một 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

Nhìn vào StringBuilder, không sử dụng nối đơn giản, và vượt qua StringBuilder thông qua toàn bộ quá trình của bạn (hoặc làm nó toàn cầu).

Answer 3

Không sử dụng nối chuỗi trong vòng lặp. Nó không mở rộng.

Sử dụng StringBuilder, điều này không làm cho các đối tượng mới tất cả các thời gian, như nối chuỗi ..

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

}

Answer 4

Bạn có thể muốn nhìn vào String.intern() như một cách để cắt giảm sử dụng bộ nhớ . Điều này sẽ sử dụng chuỗi ký tự trong chuỗi từ chuỗi. Nếu bạn có nhiều chuỗi trùng lặp, nó có thể nhanh hơn. Thông tin thêm về chuỗi nội bộ here

Answer 5

Hãy để tôi nói lý do chuỗi ghép nối chậm là do các chuỗi không thay đổi. Điều này có nghĩa là mỗi khi bạn viết "+ =", một Chuỗi mới sẽ được tạo. Điều này có nghĩa là cách bạn xây dựng chuỗi của bạn là trong trường hợp xấu nhất, O (n). Đó là bởi vì nếu bạn + = 'ed 1 char tại một thời điểm, chi phí xây dựng một chuỗi mới sẽ là 2 + 3 + 4 + ... + n, là O (n).

Sử dụng StringBuilder như đề xuất của người khác (trong chuỗi StringBuffer chậm hơn nhưng có chủ đề hơn).

Tôi cho rằng tôi nên thêm, StringBuilder sẽ cung cấp cho bạn thời gian phân bổ O (n), bởi vì nó hoạt động như một vectơ đằng sau hậu trường, vì nó có thể thay đổi. Vì vậy, xây dựng chuỗi của bạn ở đó, và sau đó gọi toString().

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

Tôi cũng muốn thêm rằng vấn đề này tương tự như trong Python. Thành ngữ trong python là nối thêm tất cả các chuỗi của bạn để nối vào một danh sách, và sau đó tham gia vào danh sách. "".join(the_list).

CẬP NHẬT: Như Bill chỉ ra, nối không phải là gốc rễ của mọi điều xấu. Một chuỗi nối tắt là tốt, và thậm chí có thể được tối ưu hóa! (Họ cũng là trường hợp tệ nhất tuyến tính). Tuy nhiên, khi bạn đang ghép nối trong một vòng lặp, như bạn đang ở trên, hiệu suất sẽ thay đổi đáng kể khi số lần lặp đi lên. Trong trường hợp đó, phân tích ở trên của tôi là hoàn hảo, như tôi đã nói cụ thể đó là "trường hợp xấu nhất", có nghĩa là bạn không cho phép tối ưu hóa. (Mà JVM thậm chí không thể tối ưu hóa nối trong vòng cũng như nó có thể bên ngoài).

Answer 6

Nếu một hồ sơ khẳng bạn rằng nút cổ chai là chuỗi nối bạn có hai lựa chọn:

• StringBuilder/StringBuffer (sau này là phù hợp hơn cho luồng)
• Ropes for Java:

Dây thừng là một sự thay thế hiệu suất cao cho chuỗi. Datastructure, được mô tả chi tiết trong "Ropes: a Alternative to Strings", cung cấp hiệu năng tốt hơn so với cả String và StringBuffer cho các sửa đổi chuỗi phổ biến như prepend, append, delete và insert. Giống như Strings, dây là không thay đổi và do đó rất phù hợp để sử dụng trong lập trình đa luồng.