Trong thư viện std của Rust coa sẵn hai kiểu dữ liệu vectơ là Vec và VecDeque. Đôi khi chúng ta không để ý đến những đặc điểm kỹ thuật của chúng khi lập trình nên sử dụng chưa được tối ưu. Bài viết này sẽ tóm tắt những đặc điểm kỹ thuật quan trọng trong việc quyết định sử dụng kiểu dữ liệu nào cho từng bài toán cụ thể. Các bạn có thể xem video phân tích chi tiết hơn tại "#029 - Vec vs. VecDeque - Khi nào dùng cái nào?" trên kênh RustDEV Vietnam.
Trong Rust, khi cần các mảng có kích thước động, chúng ta sẽ có hai lựa chọn chính: Vec<T> và VecDeque<T> (Vector Double-Ended Queue). Mặc dù cả hai đề lưu các phầ tử trong các cấu trúc tập hợp có thể dãn nở kích thước theo nhu cầu nhưng nội tại bên trong chúng lại được thiết kế cho các mục đích khác nhau.
Điểm khác nhau cơ bản - Cách tổ chức bộ nhớ
Vec<T> lưu các phần tử trong một vùng liên tục các khối bộ nhớ giống như cách mảng lưu trữ các phần tử của nó. Với cách thiết kế này, việc truy cập các phần tử của véc-tơ theo chỉ số vị trí hay việc thêm phần tử vào cuối véc-tơ có tốc độ nhất nhanh. Tuy nhiên, việc chèn hoặc loại bỏ một phần tử ở vị trí đầu tiên lại có độ phức tạp đến O(n).
VecDeque<T> (viết tắt của "vector double-ended queue") sử dụng một cấu trúc bộ nhớ vòng tròn (”ring buffer”) mà trong đó các phần tử được lưu như vòng tròn trong một khối bộ nhớ liên tục. Với cách lưu trữ này, việc thêm vào và lấy ra ở cả hai đầu vùng nhớ sẽ được thi hành rất hiệu quả, rất nhanh. Tất nhiên, việc gì cũng có giá của nó, và cái giá ở đây là cơ chế đánh chỉ số của VecDeque<T> phức tạp hơn và cần nhiều bộ nhớ hơn một chút so với Vec<T>.
Khi nào dùng Vec
Vec<T> vượt trội trong các bài toán chủ yếu sử dụng các thao tác thêm phần tử vào cuối và lấy phần tử ra dựa trên chỉ số vị trí hay thao tác chủ yếu là duyệt lần lượt danh sách các phần tử.
Khi nào dùng VecDeque
VecDeque<T> tỏa sáng khi chúng ta cần thực hiện các thao tác thêm vào và lấy ra ở hai đầu tập hợp. Đây là lựa chọn hoàn hảo khi chúng ta cần triển khai các hàng đợi xử lý, các cơ chế cửa sổ trượt trên tập hợp dữ liệu (”sliding window”) hoặc các bài toán tìm đường ngắn nhất chẳng hạn.
Các bạn có thể xem video phân tích chi tiết hơn tại "#029 - Vec vs. VecDeque - Khi nào dùng cái nào?" trên kênh RustDEV Vietnam.