Độ dài chuỗi động C

Question

Có nhiều cách khác nhau để tạo chuỗi động trong C (với độ dài thay đổi liên tục). Sau một số tìm kiếm trên google, cách chính để thực hiện việc này là sử dụng realloc().

Cách tôi đã thực hiện điều này là sử dụng danh sách được liên kết với 32 byte khối cho mỗi nút.

Tôi đã tự hỏi liệu có cách nào tốt hơn để giải quyết vấn đề này ngoài việc sử dụng realloc() và danh sách liên kết, và những điểm yếu và ưu điểm của mỗi phương pháp là gì.

EDIT Lý do tôi đang làm điều này là bởi vì tôi đang nhận dữ liệu động từ một ổ cắm recv(), và đang tìm kiếm một cách linh hoạt của lưu trữ nó, mà không phân bổ một lượng lớn dữ liệu mà aren' t cần thiết.

Answer 1

Bạn có thể phân bổ lại các kích thước được xác định trước khác nhau. Ví dụ, khi bộ đệm đầy, hãy tăng gấp đôi kích thước của nó.

Sử dụng danh sách được liên kết là một ý tưởng hay, nhưng dữ liệu không liên tục (bạn không thể chuyển toàn bộ cấu trúc sang printf) và lập chỉ mục sẽ tính toán nhiều hơn (O (N)). Một lợi thế lớn là các chuỗi phụ thêm (ở hai đầu) là O (1).

Answer 2

Tôi nghĩ rằng bạn đang tìm kiếm Scatter-Gather I/O, chức năng bạn cần tìm kiếm sẽ là readv().

Answer 3

Nếu bạn sử dụng realloc(), đừng thêm một lượng không gian liên tục trên mỗi realloc, vì sau đó chi phí sản xuất một chuỗi có độ dài n sẽ là O (n^2) (realloc có thể sẽ phân bổ một khu vực mới và sao chép dữ liệu ở đó, tức là độ phức tạp của nó không phải là hằng số mà là O (n)). Cách dễ nhất để làm điều đó là tăng gấp đôi kích thước của bộ đệm trên mỗi giá trị, sau đó chi phí khấu hao sẽ vẫn là O (n).

Answer 4

Sử dụng khối 32 byte có nghĩa là tỷ lệ giữa dữ liệu và phí trên là khủng khiếp - bạn có con trỏ trong danh sách được liên kết và ít nhất (có thể nhiều hơn) cùng một lần nữa từ bộ cấp phát bộ nhớ. Tôi thực sự khuyên bạn nên phân bổ một bộ nhớ lớn hơn nhiều và phát triển nó theo cấp số nhân để phù hợp và xem liệu điều này có gây ra vấn đề hay không. Chỉ khi bạn gặp phải vấn đề tôi sẽ đi tuyến đường danh sách liên kết.