Bao nhiêu để phát triển bộ đệm trong mô-đun C giống như StringBuilder?

Question

Trong C, tôi đang làm việc trên một "lớp" quản lý một bộ đệm byte, cho phép dữ liệu tùy ý được nối vào cuối. Tôi hiện đang xem xét thay đổi kích thước tự động khi mảng cơ bản đầy lên bằng cách sử dụng các cuộc gọi đến realloc. Điều này có ý nghĩa với bất kỳ ai đã từng sử dụng Java hoặc C# StringBuilder. Tôi hiểu cách thay đổi kích thước. Nhưng có ai có bất cứ đề xuất nào, với lý do được cung cấp, trên bao nhiêu để phát triển bộ đệm với mỗi thay đổi kích thước?

Rõ ràng, có một giao dịch được thực hiện giữa không gian lãng phí và cuộc gọi realloc quá mức (có thể dẫn đến sao chép quá mức). Tôi đã thấy một số hướng dẫn/bài viết đề xuất tăng gấp đôi. Điều đó có vẻ lãng phí nếu người dùng quản lý để cung cấp một dự đoán ban đầu tốt. Có đáng để cố gắng làm tròn một số sức mạnh của hai hoặc một bội số của kích thước căn chỉnh trên nền tảng không?

Có ai biết Java hoặc C# làm gì dưới mui xe không?

Answer 1

Trong C#, chiến lược được sử dụng để phát triển bộ đệm trong được sử dụng bởi một StringBuilder đã thay đổi theo thời gian.

Có ba chiến lược cơ bản để giải quyết vấn đề này và chúng có đặc điểm hiệu suất khác nhau.

Chiến lược cơ bản đầu tiên là:

• Hãy một mảng kí tự
• Khi bạn chạy ra khỏi phòng, tạo ra một mảng mới với k nhiều ký tự, đối với một số k không đổi.
• Sao chép mảng cũ vào mảng mới, và mồ côi mảng cũ.

Chiến lược này có một số vấn đề, rõ ràng nhất trong số đó là O (n) trong thời gian nếu chuỗi được tạo là vô cùng lớn. Giả sử k là một nghìn ký tự và chuỗi cuối cùng là một triệu ký tự. Bạn kết thúc việc phân bổ lại chuỗi tại 1000, 2000, 3000, 4000, ... và do đó sao chép 1000 + 2000 + 3000 + 4000 + ... + 999000 ký tự, được tính vào thứ tự 500 tỷ ký tự được sao chép!

Chiến lược này có thuộc tính tốt đẹp là lượng bộ nhớ "bị lãng phí" bị giới hạn bởi k.

Trong thực tế, chiến lược này hiếm khi được sử dụng vì vấn đề n bình phương đó.

Chiến lược cơ bản thứ hai là

• Hãy một mảng
• Khi bạn chạy ra khỏi phòng, tạo ra một mảng mới với k% nhân vật hơn, đối với một số k không đổi.
• Sao chép mảng cũ vào mảng mới, và mồ côi mảng cũ.

k% thường là 100%; nếu nó là sau đó điều này được gọi là chiến lược "tăng gấp đôi khi đầy đủ".

Chiến lược này có thuộc tính tốt đẹp là khấu hao chi phí là O (n). Giả sử một lần nữa chuỗi cuối cùng là một triệu ký tự và bạn bắt đầu với một nghìn. Bạn tạo bản sao ở 1000, 2000, 4000, 8000, ... và kết thúc sao chép 1000 + 2000 + 4000 + 8000 ... + 512.000 ký tự, tổng cộng khoảng một triệu ký tự được sao chép; tốt hơn nhiều.

Chiến lược có thuộc tính rằng chi phí phân bổ là tuyến tính bất kể tỷ lệ phần trăm bạn chọn.

Chiến lược này có một số nhược điểm mà đôi khi một hoạt động sao chép là cực kỳ đắt, và bạn có thể lãng phí lên đến k% chiều dài chuỗi thức trong bộ nhớ không sử dụng.

Chiến lược thứ ba là tạo một danh sách liên kết các mảng, mỗi mảng có kích thước k. Khi bạn tràn một mảng hiện có, một mảng mới sẽ được cấp phát và nối vào cuối danh sách.

Chiến lược này có thuộc tính tốt đẹp mà không hoạt động đặc biệt tốn kém, tổng số bộ nhớ bị lãng phí bị giới hạn bởi k, và bạn không cần phải xác định khối lượng lớn trong heap một cách thường xuyên. Nó có nhược điểm mà cuối cùng biến điều thành một chuỗi có thể tốn kém như các mảng trong danh sách liên kết có thể có địa phương nghèo.

Trình tạo chuỗi trong khuôn khổ .NET được sử dụng để sử dụng chiến lược gấp đôi khi toàn bộ; nó bây giờ sử dụng một chiến lược liên kết danh sách các khối.

Answer 2

Đó là thực hiện cụ thể, theo the documentation, nhưng bắt đầu với 16:

Công suất mặc định cho việc thực hiện này là 16, và công suất tối đa mặc định là Int32.MaxValue.

Đối tượng StringBuilder có thể cấp phát bộ nhớ nhiều hơn để lưu trữ các ký tự khi giá trị của một thể hiện được phóng to và dung lượng là được điều chỉnh cho phù hợp. Ví dụ: các phương thức Append, AppendFormat, EnsureCapacity, Insert và Replace có thể mở rộng giá trị của một phiên bản.

Số lượng bộ nhớ được phân bổ là thực hiện cụ thể, và một ngoại lệ (hoặc ArgumentOutOfRangeException hoặc OutOfMemoryException) được ném nếu dung lượng bộ nhớ cần thiết lớn hơn công suất tối đa.

Dựa trên một số thứ khác trong khung công tác .NET, tôi khuyên bạn nên nhân nó với 1,1 mỗi lần đạt công suất hiện tại. Nếu cần thêm dung lượng, chỉ cần tương đương với EnsureCapacity sẽ mở rộng nó theo kích thước cần thiết theo cách thủ công.

Answer 3

Khi làm việc với bộ đệm mở rộng và hợp đồng, thuộc tính khóa bạn muốn là tăng hoặc thu nhỏ bởi nhiều kích thước của bạn, không phải là sự khác biệt liên tục.

Xem xét trường hợp bạn có mảng 16 byte, tăng kích thước của nó lên 128 byte là quá mức cần thiết; tuy nhiên, nếu thay vào đó bạn có một mảng 4096 byte và tăng nó lên chỉ 128 byte, bạn sẽ sao chép rất nhiều.

Tôi được dạy luôn luôn tăng gấp đôi hoặc giảm một nửa mảng. Nếu bạn thực sự không có gợi ý nào về kích thước hoặc tối đa, nhân với hai đảm bảo rằng bạn có nhiều dung lượng trong một thời gian dài và trừ khi bạn đang làm việc trên một hệ thống hạn chế tài nguyên, phân bổ tối đa gấp đôi không gian quá khủng khiếp. Ngoài ra, việc giữ mọi thứ trong quyền hạn của hai có thể cho phép bạn sử dụng các thay đổi bit và các thủ thuật khác và phân bổ cơ bản thường là quyền hạn của hai.

Answer 4

Dịch này sang C.

Tôi có thể sẽ giữ danh sách List<List<string>>.

class StringBuilder 
{ 
    private List<List<string>> list; 

    public Append(List<string> listOfCharsToAppend) 
    { 

     list.Add(listOfCharsToAppend); 
    } 

} 

Bằng cách này bạn chỉ là duy trì một danh sách các danh sách và phân bổ bộ nhớ trên nhu cầu chứ không phân bổ bộ nhớ cũng ở phía trước.

Answer 5

Bạn thường muốn giữ cho hệ số tăng trưởng nhỏ hơn một chút so với trung bình vàng (~ 1.6). Khi nó nhỏ hơn giá trị trung bình của vàng, các phân đoạn bị loại bỏ sẽ đủ lớn để đáp ứng yêu cầu sau đó, miễn là chúng liền kề với nhau. Nếu yếu tố tăng trưởng của bạn lớn hơn ý nghĩa vàng, điều đó không thể xảy ra.

Tôi nhận thấy rằng việc giảm yếu tố thành 1.5 vẫn hoạt động khá độc đáo và có lợi thế là dễ thực hiện trong toán số nguyên (size = (size + (size << 1))>>1; - với trình biên dịch phong nha, bạn có thể viết là (size * 3)/2 và biên dịch thành mã nhanh).

Tôi dường như nhớ lại một cuộc trò chuyện cách đây vài năm trên Usenet, trong đó PJ Plauger (hoặc có thể là Pete Becker) của Dinkumware, nói rằng họ sẽ thực hiện nhiều bài kiểm tra rộng hơn bao giờ hết. (ví dụ, việc thực hiện std::vector trong thư viện chuẩn C++ của họ sử dụng 1.5).

Answer 6

Có ai biết Java hoặc C# làm gì dưới mui xe không?

Hãy xem liên kết sau để xem cách nó được thực hiện trong StringBuilder của Java từ JDK7, cụ thể là phương pháp expandCapacity. http://hg.openjdk.java.net/build-infra/jdk7/jdk/file/0f8da27a3ea3/src/share/classes/java/lang/AbstractStringBuilder.java

Answer 7

Danh sách trong .NET framework sử dụng thuật toán này: Nếu dung lượng ban đầu được chỉ định, nó tạo bộ đệm có kích thước này, nếu không thì không có bộ đệm nào được cấp cho đến khi mục đầu tiên được thêm vào, phân bổ không gian bằng số lượng mục) được thêm vào, nhưng không nhỏ hơn 4. Khi cần thêm dung lượng, nó sẽ cấp phát bộ đệm mới với dung lượng 2x trước đó và sao chép tất cả các mục từ bộ đệm cũ sang bộ đệm mới. Trước đó StringBuilder sử dụng thuật toán tương tự.

Trong .NET 4, StringBuilder phân bổ bộ đệm ban đầu của kích thước được chỉ định trong hàm dựng (kích thước mặc định là 16 ký tự). Khi bộ đệm được phân bổ quá nhỏ, không sao chép được thực hiện. Thay vào đó nó lấp đầy bộ đệm hiện tại vào rim, sau đó tạo ra thể hiện mới của StringBuilder, cấp phát bộ đệm có kích thước * MAX (length_of_remaining_data_to_add, MIN (length_of_all_previous_buffers, 8000)) * vì vậy ít nhất tất cả dữ liệu còn lại phù hợp với bộ đệm mới và tổng kích thước của tất cả bộ đệm ít nhất là gấp đôi. StringBuilder mới giữ tham chiếu đến StringBuilder cũ và do đó các cá thể tạo ra danh sách các bộ đệm liên kết.