Chuỗi hoạt động tối ưu hóa trong C#

Question

Mã C# sau mất 5 phút để chạy:

int i = 1; 
string fraction = ""; 
while (fraction.Length < 1000000) 
{ 
    fraction += i.ToString(); 
    i++; 
} 

"Tối ưu hóa nó" như thế này làm cho nó chạy trong 1,5 giây:

int i = 1; 
string fraction = ""; 
while (fraction.Length < 1000000) 
{ 
    // concatenating strings is much faster for small strings 
    string tmp = ""; 
    for (int j = 0; j < 1000; j++) 
    { 
     tmp += i.ToString(); 
     i++; 
    } 
    fraction += tmp; 
} 

EDIT: Một số người đã đề xuất sử dụng StringBuilder, đây cũng là một gợi ý tuyệt vời và điều này xuất hiện tại 0.06s:

int i = 1; 
StringBuilder fraction = new StringBuilder(); 
while (fraction.Length < 1000000) 
{ 
    fraction.Append(i); 
    i++; 
} 

Chơi xung quanh để tìm giá trị tối ưu là j là một chủ đề trong một thời điểm khác, nhưng tại sao chính xác việc tối ưu hóa không rõ ràng này lại hoạt động tốt như vậy? Ngoài ra, về một chủ đề liên quan, tôi đã nghe nói rằng bạn không bao giờ nên sử dụng toán tử + với chuỗi, ủng hộ string.Format(), điều này có đúng không?

Answer 1

Có thể bạn sẽ thấy 1000 ký tự đầu tiên sẽ mất gần như không có thời gian phản đối 1000 ký tự cuối cùng.

Tôi giả định rằng phần tốn thời gian là việc sao chép thực tế chuỗi lớn vào vùng bộ nhớ mới mỗi lần bạn thêm char là công việc khó khăn cho máy tính của bạn.

Tối ưu hóa của bạn có thể dễ dàng so sánh với những gì bạn thường làm với luồng, bạn sử dụng bộ đệm.Các khối lớn hơn thường sẽ dẫn đến hiệu suất tốt hơn cho đến khi bạn đạt đến kích thước quan trọng, nơi nó không còn tạo ra bất kỳ sự khác biệt nào và bắt đầu là một nhược điểm khi bạn xử lý một lượng nhỏ dữ liệu.

Nếu bạn tuy nhiên đã xác định một mảng char có kích thước phù hợp ngay từ đầu, nó có thể sẽ rất nhanh, vì sau đó nó sẽ không phải sao chép nó lặp đi lặp lại.

Answer 2

Sử dụng StringBuilder để nối nhiều hơn (xấp xỉ) 5 chuỗi (kết quả có thể thay đổi đôi chút). Ngoài ra, cung cấp cho constructor StringBuilder một gợi ý về kích thước tối đa dự kiến.

[Cập nhật]: chỉ cần nhận xét về chỉnh sửa của bạn cho câu hỏi. Bạn cũng có thể tăng hiệu suất StringBuilder 's nếu bạn có một ý tưởng gần đúng (hoặc chính xác) của kích thước cuối cùng của chuỗi kết nối, vì điều này sẽ làm giảm số lượng phân bổ bộ nhớ nó có để thực hiện:

// e.g. Initialise to 10MB 
StringBuilder fraction = new StringBuilder(10000000); 

Answer 3

Ngoài ra, về một chủ đề liên quan, tôi đã nghe nói rằng bạn không bao giờ nên sử dụng toán tử + với chuỗi, để ủng hộ string.Format(), điều này có đúng không?

Không, giống như tất cả các tuyên bố tuyệt đối đó là vô nghĩa. Tuy nhiên, nó là đúng là sử dụng Format thường làm cho mã định dạng dễ đọc hơn và thường nhanh hơn một chút so với nối - nhưng tốc độ không phải là yếu tố quyết định ở đây.

Đối với mã của bạn… nó dẫn đến các chuỗi nhỏ hơn được sao chép (cụ thể là, tmp) trong phần nối. Tất nhiên, trong fraction += tmp bạn sao chép một chuỗi lớn hơn nhưng điều này xảy ra ít thường xuyên hơn.

Vì vậy, bạn đã giảm nhiều bản sao lớn xuống một số lượng lớn và nhiều bản sao nhỏ.

Hmm, tôi vừa nhận thấy rằng vòng ngoài của bạn có cùng kích thước trong cả hai trường hợp. Điều này không nên nhanh hơn, sau đó.

Answer 4

Tôi không thể làm thử nghiệm ngay bây giờ, nhưng hãy thử sử dụng StringBuilder.

int i = 1; 
    StringBuilder fraction = new StringBuilder(); 
    while (fraction.Length < 1000000) 
    { 
     fraction.Append(i); 
     i++; 
    } 
return sb.ToString(); 

Answer 5

Tôi hoàn toàn không nhận được kết quả của bạn. Trên hộp của tôi StringBuilder thắng tay xuống. Bạn có thể đăng chương trình thử nghiệm đầy đủ của mình không? Đây là của tôi, với ba biến thể - tối ưu hóa chuỗi nối của bạn, StringBuilder "đơn giản" và StringBuilder với dung lượng ban đầu. Tôi đã tăng giới hạn vì nó đã đi quá nhanh trên hộp của tôi để có thể đo lường một cách hữu ích.

using System; 
using System.Diagnostics; 
using System.Text; 

public class Test 
{ 
    const int Limit = 4000000; 

    static void Main() 
    { 
     Time(Concatenation, "Concat"); 
     Time(SimpleStringBuilder, "StringBuilder as in post"); 
     Time(SimpleStringBuilderNoToString, "StringBuilder calling Append(i)"); 
     Time(CapacityStringBuilder, "StringBuilder with appropriate capacity"); 
    } 

    static void Time(Action action, string name) 
    { 
     Stopwatch sw = Stopwatch.StartNew(); 
     action(); 
     sw.Stop(); 
     Console.WriteLine("{0}: {1}ms", name, sw.ElapsedMilliseconds); 
     GC.Collect(); 
     GC.WaitForPendingFinalizers(); 
    } 

    static void Concatenation() 
    { 
     int i = 1; 
     string fraction = ""; 
     while (fraction.Length < Limit) 
     { 
      // concatenating strings is much faster for small strings 
      string tmp = ""; 
      for (int j = 0; j < 1000; j++) 
      { 
       tmp += i.ToString(); 
       i++; 
      } 
      fraction += tmp;    
     } 
    } 

    static void SimpleStringBuilder() 
    { 
     int i = 1; 
     StringBuilder fraction = new StringBuilder(); 
     while (fraction.Length < Limit) 
     { 
      fraction.Append(i.ToString()); 
      i++; 
     } 
    } 

    static void SimpleStringBuilderNoToString() 
    { 
     int i = 1; 
     StringBuilder fraction = new StringBuilder(); 
     while (fraction.Length < Limit) 
     { 
      fraction.Append(i); 
      i++; 
     } 
    } 

    static void CapacityStringBuilder() 
    { 
     int i = 1; 
     StringBuilder fraction = new StringBuilder(Limit + 10); 
     while (fraction.Length < Limit) 
     { 
      fraction.Append(i); 
      i++; 
     } 
    } 
} 

Và kết quả:

Concat: 5879ms 
StringBuilder as in post: 206ms 
StringBuilder calling Append(i): 196ms 
StringBuilder with appropriate capacity: 184ms 

Lý do nối của bạn là nhanh hơn so với giải pháp đầu tiên là đơn giản mặc dù - bạn đang làm một vài concatenations "giá rẻ" (nơi tương đối ít dữ liệu đang được sao chép mỗi lần) và tương đối ít "nối" lớn (của toàn bộ chuỗi cho đến nay). Trong bản gốc, mỗi bước sẽ sao chép tất cả dữ liệu thu được từ trước đến nay, điều này rõ ràng là tốn kém hơn.

Answer 6

trả lời cho queston sửa đổi ("tại sao tối ưu hóa này làm việc không rõ ràng rất tốt" và "là đúng, bạn không nên sử dụng + nhà điều hành trên dây"):

Tôi không chắc chắn mà không tối ưu hóa rõ ràng bạn đang nói về. Nhưng câu trả lời cho câu hỏi thứ hai, tôi nghĩ, bao gồm tất cả các căn cứ.

Cách chuỗi hoạt động trong C# là chúng được phân bổ dưới dạng độ dài cố định và không thể thay đổi. Điều này có nghĩa là bất cứ khi nào bạn cố gắng thay đổi độ dài của chuỗi, toàn bộ chuỗi mới sẽ được tạo và chuỗi cũ được sao chép theo chiều dài thích hợp. Đây rõ ràng là một quá trình chậm. Khi bạn sử dụng String.Format nó sử dụng nội bộ một StringBuilder để tạo chuỗi.

StringBuilder hoạt động bằng bộ đệm bộ nhớ được phân bổ thông minh hơn các chuỗi có độ dài cố định và do đó thực hiện tốt hơn đáng kể trong hầu hết các trường hợp. Tôi không chắc chắn về các chi tiết của StringBuilder trong nội bộ, vì vậy bạn sẽ phải hỏi một câu hỏi mới cho điều đó. Tôi có thể suy đoán hoặc không phân bổ lại các phần cũ của chuỗi (thay vì tạo một danh sách liên kết nội bộ và chỉ phân bổ đầu ra cuối cùng khi cần thiết bởi ToString) hoặc nó phân bổ lại với sự tăng trưởng theo hàm mũ (khi nó hết bộ nhớ, nó phân bổ gấp đôi thời gian tiếp theo, do đó đối với chuỗi 2GB, nó sẽ chỉ cần phân bổ lại khoảng 30 lần).

Ví dụ của bạn với vòng lặp lồng nhau tăng tuyến tính. phải mất một chuỗi nhỏ và phát triển lên đến 1000, và sau đó vá 1000 vào chuỗi lớn hơn trong một hoạt động lớn. Khi chuỗi lớn được thực sự lớn, bản sao kết quả từ việc tạo ra một chuỗi mới sẽ mất nhiều thời gian. Khi bạn giảm số lần này được thực hiện (thay vào đó thay đổi kích thước một chuỗi nhỏ hơn thường xuyên hơn) bạn tăng tốc độ. Tất nhiên, StringBuilder thậm chí còn thông minh hơn về phân bổ bộ nhớ, và do đó nhanh hơn nhiều.

Answer 7

Thêm một nhân vật thành một chuỗi có thể có hai hậu quả:

• nếu vẫn còn có không gian cho nhân vật nó chỉ được thêm vào ở cuối; (như một người bình luận nhận thấy, điều này không thể xảy ra với các chuỗi C#, vì bạn là bất biến).
• nếu không có dấu cách ở cuối, một khối bộ nhớ mới được cấp phát cho chuỗi mới, nội dung của chuỗi cũ được sao chép ở đó và ký tự được thêm vào.

Để phân tích mã của bạn, việc thêm 1000000 lần một ký tự đơn giản là đơn giản hơn. Ví dụ chính xác của bạn phức tạp hơn một chút để giải thích vì vì tôi cao hơn, bạn thêm nhiều ký tự hơn tại một thời điểm.

Sau đó, trong trường hợp không có thêm không gian được dành riêng, ví dụ đầu tiên phải làm 1000000 phân bổ và bản sao, trung bình 0,5 * 1000000 ký tự. Điều thứ hai phải làm 1000 phân bổ và bản sao của một trung bình 0,5 * 1000000 ký tự, và 1000000 phân bổ và bản sao của 0,5 * 1000 ký tự. Nếu sao chép là lineair với kích thước của bản sao và phân bổ miễn phí, tình hình đầu tiên mất 500 000 000 000 đơn vị thời gian và thứ hai 500 000 000 + 500 000 000 đơn vị thời gian.