Cách Triển Khai Mảng Động Trong C

Lần trước, chúng ta đã đề cập đến một kiểu dữ liệu trừu tượng (ADT) phổ biến là sequence và cách hiện thực hóa nó trong ngôn ngữ C. Thông thường, chúng ta không sử dụng trực tiếp sequence, mà thường tận dụng nó để xây dựng các cấu trúc dữ liệu phục vụ nhu cầu cụ thể. Ví dụ như hàng đợi thông báo, ngăn xếp lệnh, v.v. Một sequence được thiết kế tốt sẽ mang lại lợi ích đáng kể: ngay cả khi bạn chỉ sử dụng một phần chức năng, hiệu suất (về mặt thời gian và không gian) cũng không bị ảnh hưởng nghiêm trọng do các tính năng không dùng đến.

Hôm nay, tôi muốn nói về một ADT khác hữu ích hơn nữa: mảng động. Chủ đề này cũng được đề cập trong tác phẩm kinh điển “Interfaces and Implementations của C”. Tôi không có ý định chỉ trích cách triển khai trong sách là sai lệch hay thiếu sót, mà chỉ muốn trình bày vấn đề dưới góc nhìn cá nhân.

Tại sao chúng ta cần mảng? Trong C, ngôn ngữ đã hỗ trợ sẵn mảng, và đặc biệt từ phiên bản C99 cho phép khai báo mảng độ dài thay đổi trên stack. Trong C++, thư viện STL cung cấp sẵn module vector để lập trình viên sử dụng. Tuy nhiên, vấn đề không nằm ở chỗ ngôn ngữ hay thư viện cung cấp bao nhiêu lựa chọn, mà là chúng ta cần xác định rõ ràng: tối thiểu cần những gì để giải quyết vấn đề?

Mảng cho phép truy cập ngẫu nhiên các phần tử với độ phức tạp O(1), nhưng truy cập ngẫu nhiên chỉ là phương tiện chứ không phải mục đích. Chúng ta thực sự cần một mảng để giải quyết vấn đề nào? Khi nào thì nên tổ chức dữ liệu dưới dạng mảng? Những năm gần đây, tôi vẫn chưa thể đưa ra câu trả lời chính xác. Thông thường, chúng ta chỉ cảm tính rằng sử dụng vector (trong C++) rất tiện lợi nên cứ dùng. Khi làm việc với C, tôi thường viết liền tay hàm realloc để mở rộng khối dữ liệu. Gần đây, tôi nhận ra cần phải tổng hợp các yêu cầu và thiết kế một module chung để giải quyết vấn đề một cách nhất quán.

Kết quả suy nghĩ của tôi: chúng ta cần mảng mỗi khi phải tập hợp dữ liệu theo chu kỳ, khi độ dài dữ liệu không xác định và cần khả năng mở rộng động.

Tính chất quan trọng nhất của mảng là khả năng duyệt qua các phần tử một cách hiệu quả nhất. Khi xem xét ở cấp độ ngôn ngữ C, cần phân tích kỹ lưỡng sự khác biệt trong cách hiện thực và ảnh hưởng đến hiệu suất. Ví dụ như duyệt qua danh sách liên kết cũng có độ phức tạp O(N), nhưng chi phí về thời gian và không gian luôn cao hơn mảng lưu trữ liên tục trong bộ nhớ.

Chúng ta cần xóa sạch mảng nhanh chóng để chuẩn bị cho chu kỳ tập hợp dữ liệu mới.

Chúng ta cần sắp xếp dữ liệu để có thể duyệt qua các phần tử theo thứ tự mong muốn.

Đôi khi, chúng ta cần tìm kiếm nhanh. Nếu dữ liệu đã được sắp xếp, thuật toán tìm kiếm nhị phân sẽ giảm độ phức tạp xuống O(log n).

Các tính năng khác, chúng ta không cần thiết phải có.

Lưu ý: Chúng ta thường nhầm lẫn một nhu cầu khác. Nhiều khi, chúng ta sử dụng mảng như một cấu trúc key-value dictionary hiệu quả nhưng bị giới hạn bởi khóa số (chỉ số) trong mảng. Yêu cầu truy xuất nhanh đến giá trị thông qua khóa (có thể là số hoặc không) cần được xử lý riêng biệt.

Cuối cùng, tôi đã định nghĩa các phương thức cho ADT array như sau:

1
2
3
4
5
6

struct array * array_create(int atom_size);
void array_release(struct array *);
void array_clear(struct array *);
void array_push(struct array *, void *atom);
void array_iterator(struct array *, seqi iter);
void array_sort(struct array *, int (*compar)(void *,void *));

Hiện tại tôi chưa cung cấp phương thức tìm kiếm nhị phân vì chưa gặp nhu cầu thực tế. Đồng thời, tôi vẫn chưa xác định rõ giao diện chuẩn tốt nhất cho chức năng này nên cần cân nhắc thêm.

Trong quá trình hiện thực, tôi cấp phát một vùng nhớ liên tục để lưu trữ dữ liệu. Khi người dùng thêm phần tử bằng hàm push, dữ liệu sẽ được sao chép vào bên trong array. Sau đó, seq sẽ quản lý các tham chiếu (con trỏ) đến các phần tử này. Khi vùng nhớ không còn đủ, hàm realloc sẽ mở rộng không gian lưu trữ. Nếu địa chỉ vùng nhớ thay đổi, các con trỏ trong seq cũng sẽ được cập nhật tương ứng. Việc tách biệt giữa chỉ số và dữ liệu giúp tăng hiệu suất khi sắp xếp (giảm lượng dữ liệu cần trao đổi).

Hàm sort được thiết kế với giao diện tương tự qsort, tuy nhiên do định nghĩa khác biệt nên không thể trực tiếp gọi qsort. Trong glibc tồn tại hàm qsort_r phù hợp hơn, nhưng vì lý do hiệu suất tôi đã tự viết lại một thuật toán quicksort khác. Thực ra, đoạn code này không quá phức tạp.

Lưu ý rằng vị trí của dữ liệu trong bộ nhớ không cố định. Các con trỏ nhận được từ seq không được phép lưu trữ trong các cấu trúc dữ liệu khác. Cũng như seqi - bộ duyệt (iterator), theo như mô tả trong bài viết trước về sequence, không nên giữ lại lâu dài. Bạn có thể xem đây là một hạn chế của ADT này. Tuy nhiên, theo quan điểm cá nhân, mỗi thiết kế chỉ nên giải quyết những yêu cầu được định nghĩa rõ ràng, không nên ôm đồm mọi thứ.

Hãy làm một việc duy nhất, nhưng hãy làm nó thật xuất sắc.