Hiệu suất (JAVA) ~ Ghép chuỗi trong một vòng lặp với việc thêm và thêm

Question

Tôi đang gặp sự cố về hiệu suất. Có ai có giải pháp nhanh hơn/tốt hơn để thực hiện những việc sau không:

String main = ""; 
    for (String proposition : propositions) { 
     if (main.length() == 0) { 
      main = proposition; 
     } else { 
      main = "|(" + proposition + "," + main + ")"; 
     } 
    } 

Tôi biết concat và stringbuilder nhanh hơn, nhưng tôi không biết cách sử dụng các phương pháp này. Vì dòng mã sau đây:

main = "|(" + proposition + "," + main + ")"; 

Cảm ơn bạn trước!

Answer 1

Vì vậy, từ những gì tôi có thể nói có 3 vấn đề ở đây:

1. Giá trị chủ yếu được thêm vào phía trước chuỗi.
2. Đối với mỗi giá trị, một ký tự được nối vào.
3. Nếu chỉ có một giá trị, không có gì được thêm vào hoặc được thêm vào trước.
4. Với 2 hoặc nhiều mục, mục 0 được xử lý khác nhau:

0: ""

1: "A"

2: "| (B, A) "

3:" | (C, | (B, A))"

Nó có thể được thực hiện nhanh hơn bằng cách thực hiện một vài thay đổi:

1. Đảo ngược thuật toán, điều này có nghĩa là phần lớn công việc liên quan đến phụ thêm, cho phép bạn sử dụng StringBuilders.
2. Đếm số lượng đóng ) và thêm sau khi vòng lặp kết thúc.
3. Trường hợp đặc biệt cho 0 hoặc 1 mục trong danh sách.

Với những thay đổi đó, thuật toán sẽ có thể sử dụng StringBuilder và nhanh hơn rất nhiều.

Nỗ lực tại một thuật toán:

int length = propositions.size(); 
if (length == 0) { 
    main = ""; 
} else { 
    StringBuilder sb = new StringBuilder(); 
    int nestingDepth = 0; 
    // Reverse loop, ignoring 0th element due to special case 
    for (int i = length - 1; i > 0; i--) { 
     sb.append("|(").append(propositions.get(i)).append(','); 
     nestingDepth++; 
    } 
    // Append last element due to special casing 
    sb.append(propositions.get(0)); 
    for (int i = 0; i < nestingDepth; i++) { 
     sb.append(')'); 
    } 

    main = sb.toString(); 
} 

tôi tin này nên tạo ra kết quả chính xác, nhưng nó sẽ cho ý tưởng đúng.

Answer 2

Sự cố là bạn đang thêm và thêm vào chuỗi khi bạn thực hiện. String và StringBuilder không xử lý tốt (và cung cấp cho hiệu suất bậc hai). Nhưng bạn có thể sử dụng một dequeue hỗ trợ chèn lúc bắt đầu và kết thúc để lưu trữ tất cả các mảnh. Sau đó, cuối cùng bạn có thể tham gia các bit trong dequeue.

ArrayDeque bits = new ArrayDeque(); 
for (String proposition : propositions) { 
    if (bits.size() == 0) { 
     bits.push(proposition); 
    } else { 
     // Add prefix 
     main.offerFirst("|(" + proposition + ","); 
     // Add suffix 
     main.push(")"); 
    } 
} 
StringBuilder sb = new StringBuilder(); 
for(String s : bits) { 
    sb.append(s); 
} 
main = sb.toString(); 

Answer 3

Giả sử đây là một mảng của propositions, trước tiên bạn có thể tổng hợp theo chiều dài của String (s) trong mảng. Thêm 4 cho các ký tự bổ sung của bạn và trừ 4 vì bạn không sử dụng các dấu tách đó trên phần tử đầu tiên.Đó phải là kích thước hoàn hảo cho đầu ra của bạn (tùy chọn này là tùy chọn, vì StringBuilder có kích thước động). Tiếp theo, tạo một StringBuilder. Thêm phần tử đầu tiên. Tất cả các phần tử tiếp theo đều theo cùng một mẫu, vì vậy vòng lặp được đơn giản hóa với một số for truyền thống. Một cái gì đó như,

int len = Stream.of(propositions).mapToInt(s -> s.length() + 4).sum() - 4; 
StringBuilder sb = new StringBuilder(len); // <-- len is optional 
sb.append(propositions[0]); 
for (int i = 1; i < propositions.length; i++) { 
    sb.insert(0, ",").insert(0, propositions[i]).insert(0, "|(").append(")"); 
} 
System.out.println(sb);