Chương 3: DANH SÁCH ĐƯỢC LIÊN KẾT – 6. Danh sách được liên kết chưa được kiểm tra

Tram Ho

3.10 Unrolled Linked Lists

Một trong những ưu điểm lớn nhất của danh sách liên kết so với mảng là việc chèn một phần tử ở bất kỳ vị trí nào chỉ mất

O(1)O (1) thời gian.
Tuy nhiên, phải mất

O(n)O (n) để tìm kiếm một phần tử trong danh sách liên kết.
Có một biến thể đơn giản của danh sách được liên kết đơn được gọi là unrolled linked lists – danh sách liên kết mở rộng.
Một unrolled linked lists lưu trữ nhiều phần tử trong mỗi nút (chúng ta hãy gọi nó là một block – khối cho thuận tiện).
Trong mỗi khối, một circular linked list – danh sách liên kết vòng được sử dụng để kết nối tất cả các nút.

image.png

Giả sử rằng sẽ có không quá n phần tử trong unrolled linked list vào bất kỳ thời điểm nào.
Để đơn giản hóa vấn đề này, tất cả các khối, ngoại trừ khối cuối cùng, phải chứa chính xác

nsqrt { n } các phần tử.
Vì vậy, sẽ không có nhiều hơn

nsqrt { n } khối ở bất kỳ thời điểm nào.

Tìm kiếm 1 phần tử trong Unrolled Linked Lists

Trong unrolled linked lists, chúng ta có thể tìm thấy phần tử thứ k trong

O(n)O (sqrt { n }):

  1. Duyệt qua các khối của list đến khối chứa nút thứ k là khối thứ
    [kn][frac { k } { sqrt { n } }]
    (Giá trị sẽ được làm tròn lên).
    Nó yêu cầu O(n)O (sqrt { n }) vì chúng ta phải tìm nó bằng cách không đi qua quá nsqrt { n }

    khối.

  2. Tính k mod
    [n][sqrt { n }]
    (căn của n sẽ được làm tròn lên, mod: phép chia lấy dư). Nó yêu cầu O(n)O (sqrt { n }) vì chúng ta phải tìm nó bằng cách không đi qua quá nsqrt { n }

    node trong khối.

image.png

Thêm 1 phần tử trong Unrolled Linked Lists

image.png

Khi chèn một nút, chúng ta phải sắp xếp lại các nút trong unrolled linked lists để duy trì các thuộc tính đã đề cập trước đó, rằng mỗi khối chứa

nsqrt { n } các nút.
Giả sử rằng chúng ta chèn một nút x sau nút thứ i, và x nên được đặt trong khối thứ j.
Các nút trong khối thứ j và trong các khối sau khối thứ j phải được dịch chuyển về phía đuôi của danh sách để mỗi khối vẫn có

nsqrt { n } các nút.
Ngoài ra, một khối mới cần được thêm vào đuôi nếu khối cuối cùng của danh sách hết dung lượng, tức là nó có nhiều hơn

nsqrt { n } các nút.

Performing Shift Operation

Cái này dịch sang tiếng việt hơi khó, mình cũng không biết nên dùng từ gì 😅 Hiểu đơn giản nó sẽ là việc xử lý về các phép dịch chuyển các node trong list này.

Lưu ý rằng mỗi thao tác shift, bao gồm việc loại bỏ một nút khỏi phần đuôi của danh sách liên kết vòng trong một khối và chèn một nút vào đầu danh sách liên kết vòng trong khối phía sau, chỉ mất

O(1)O (1).
Do đó, tổng độ phức tạp về thời gian của một thao tác chèn cho các unrolled linked list là

O(n)O (sqrt { n }); có nhiều nhất là

nsqrt { n } khối và do đó có nhiều nhất là

O(n)O (sqrt { n }) hoạt động dịch chuyển.

  1. Một temp pointer để lưu trữ node đuôi của khối A.

image.png
2. Trong khối A, di chuyển con trỏ next của nút đầu trỏ đến nút phía trước nút cuối cùng, sau đó có thể loại bỏ nút đuôi của A.

image.png
3. Con trỏ next của node tạm thời temp trỏ tới nút đuôi của khối B

image.png
4. Head node của B trỏ tới node temp.

image.png
5. Cuối cùng, set head pointer node trỏ tới temp, temp trở thành node đầu của khối B.

image.png
6. Temp pointer tới đây có thể hủy bỏ. Chúng ta đã hoàn thành thao tác dịch chuyển để di chuyển nút đuôi ban đầu của A trở thành nút đầu mới của B.

image.png

Performance

Với unrolled linked lists, có một số lợi thế, một về tốc độ và một về không gian.
Đầu tiên, nếu số lượng phần tử trong mỗi khối có kích thước thích hợp (ví dụ: tối đa là kích thước của một dòng bộ nhớ cache), chúng ta sẽ nhận được hiệu suất bộ nhớ cache tốt hơn đáng kể từ vị trí bộ nhớ được cải thiện.
Thứ hai, vì chúng ta có

O(n/m)O (n / m) liên kết , trong đó n là số phần tử trong unrolled linked lists và m là số phần tử chúng ta có thể lưu trữ trong bất kỳ khối nào, chúng ta cũng có thể tiết kiệm một lượng không gian đáng kể, đặc biệt đáng chú ý nếu mỗi phần tử nhỏ.

So sánh giữa Doubly Linked Lists và Unrolled Linked Lists

Để so sánh chi phí cho một unrolled list, các phần tử trong triển khai danh sách được liên kết kép bao gồm dữ liệu, một con trỏ đến nút tiếp theo và một con trỏ đến nút trước đó trong danh sách, như ví dụ sau đây.
Giả sử chúng ta có con trỏ 4 byte, mỗi nút sẽ chiếm 8 byte(2 con trỏ next và prev).
Bộ nhớ được cấp phát cho 1 nút để chứa data có thể trong khoảng 8 bytes đến 16 bytes. Ta xem xét trường hợp tốt nhất, nó chiếm 8 bytes bộ nhớ.
Vậy tổng 1 node sẽ mất 16 bytes, 1000 node ta sẽ mất 16kb bộ nhớ.

Bây giờ tính toán cho unrolled linked list(có thể gọi nó là LinkedBlock). Nó sẽ trông giống như thế này:
Một block được cấp phát 12 bytes + 8 bytes và chứa một mảng 100 phần tử mất chi phí 400 bytes + 8 bytes chi phí => Tổng sẽ tốn 428 bytes hay 4.28 bytes cho mỗi phần tử.
So sánh với 1K phần tử ở trên thì ta sẽ cần 4.2KB chi phí, nghĩa là vẫn tốt hơn 4 lần so với danh sách được liên kết kép.
Ngay cả khi danh sách trở nên phân mảnh nghiêm trọng và các mảng mục chỉ đầy 1/2 trung bình, đây vẫn là một cải tiến.
Ngoài ra, hãy lưu ý rằng chúng ta có thể điều chỉnh kích thước mảng thành bất kỳ giúp chúng ta có chi phí tốt nhất cho ứng dụng của mình.

image.png

Ảnh trên là bản gốc mà tác giả viết, mình không chắc tác giả đang sử dụng ngôn ngữ hay hệ thống nào để cấp phát bộ nhớ, mảng 100 phần tử thì chỉ cần 4 bytes mỗi phần tử, 1 block – single node thì cần 12 bytes + 8 bytes chi tiết cho những gì, mính đoán là 1 biến int lưu số phần tử trong node 8 bytes, 1 con trỏ tới node tiếp theo 4 bytes, 1 biến lưu địa chỉ tới mảng 8 bytes.
Nếu ở đây mình có hiểu và dịch gì ý nào chưa đúng, các bạn comment giúp để mình sửa lại nhé.

Implementation

Một implement cơ bản của Unrolled Linked List mình tham khảo ở đây


Thêm phần tử vào Unrolled Linked List
Chia sẻ bài viết ngay

Nguồn bài viết : Viblo