Sưu tầm tại: http://www.vithon.org
Giới thiệu
Qua các lượt bài trước, chúng ta đã thảo luận về thuận toán tìm kiếm nhị phân và ngăn (partition). Cả hai thuận toán này đều dựa trên cấu trúc dữ liệu mảng (array) vốn rất quen thuộc với chúng ta.Ngoài ra, hai thuật toán trên được xếp vào nhóm thuật toán tất định (determistic algorithm). Các thuật toán thuộc nhóm này thỏa mãn hai điều kiện:
- Luôn trả về kết quả giống nhau nếu được cung cấp cùng một dữ liệu đầu vào.
- Các trạng thái (state) trong quá trình tính toán phải giống nhau với cùng một dữ liệu đầu vào.
Mục đích
Một cấu trúc dữ liệu đơn giản nhưng hiệu quả trên các tác vụ cơ bản: Thêm, Xóa và Tìm Kiếm.Định nghĩa
Danh sách nhảy cóc S là một tập hợp các danh sáchS[0], S[1] ... S[N-1]. Để dễ hình dung chúng ta xem mỗi danh sách con tương ứng với một “tầng”, trong đó 0 là tầng thấp nhất, cho đến N-1 là tầng cao nhất. Danh sách nhảy cóc luôn thỏa mãn các điều kiện:- Mỗi danh sách con chứa các giá trị theo thứ tự tăng dần.
- Phần từ đầu và cuối mỗi danh sách con đều là NULL.
- Danh sách ở tầng cao hơn là dãy con của danh sách tầng dưới.
12, 23, 34, 46, 64, 78, 89S[3] NULL 23 NULL S[2] NULL 23 64 NULL S[1] NULL 23 34 64 78 NULL S[0] NULL 12 23 34 46 64 78 80 NULL
Tìm kiếm trong danh sách
Gọi K là giá trị cần tìm kiếm. Ý tưởng chính của thuật toán là cố gắng duyệt càng xa càng tốt trên tầng cao hơn và tiếp tục ở tầng thấp hơn cho đến khi không thể duyệt được nữa.Thuật toán bắt đầu từ phần tử đầu tiên, tầng trên cùng của danh sách. Duyệt theo quy luật:
- Nhảy sang phần tử kế tiếp trên cùng tầng nếu phần tử tiếp theo đó khác NULL và bé hơn hoặc bằng K.
- Nếu không thể di chuyển trên cùng tầng được nữa:
- Dừng duyệt nếu như đang ở tầng thấp nhất.
- Ngược lại, nhảy xuống phần tử ngay bên dưới ở tầng tiếp theo.
Ví dụ dưới đây minh họa việc tìm kiếm
K = 85 trong danh sách S tại trạng thái được mô tả ở phần trước:S[3] NULL -------> 23 NULL S[2] NULL 23 -----------> 64 NULL S[1] NULL 23 34 64 -> 78 -> 83 NULL S[0] NULL 12 23 34 46 64 78 83 90 NULL
| Bước | Tầng hiện tại | Phần tử hiện tại | Phần tử kế tiếp | Di chuyển |
|---|---|---|---|---|
| 1 | S[3] | NULL | 23 | Nhảy sang phần tử kế tiếp vì 23 <= K |
| 2 | S[3] | 23 | NULL | Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL |
| 3 | S[2] | 23 | 64 | Nhảy sang phần tử kế tiếp vì 64 <= K |
| 4 | S[2] | 64 | NULL | Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL |
| 5 | S[1] | 64 | 78 | Nhảy sang phần tử kế tiếp vì 78 <= K |
| 6 | S[1] | 78 | 83 | Nhảy sang phần tử kế tiếp vì 83 <= K |
| 7 | S[1] | 83 | NULL | Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL |
| 8 | S[0] | 83 | 90 | Dừng thuật toán vì 90 > K |
K = 83, các bước duyệt trên danh sách sẽ giống hệt như vậy ngoại trừ việc thuật toán sẽ kết thúc ở bước thứ 7 và chúng ta tìm được K.Để ý các bước duyệt, chúng ta thấy thuật toán đã “nhảy cóc” qua các phần tử 12, 34 và 46.
Thêm phần tử vào danh sách
Gọi H là giá trị của phần tử cần thêm vào danh sách S. Thuật toán được mô tả như sau:- Bước 1: Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt:
p[N-1], p[N-2] … p[1], p[0]tương ứng với tầngN-1, N-2, ... 1, 0. - Bước 2: Nếu H đã tồn tại trong danh sách S, kết thúc thuật toán.
- Bước 3: Thêm phần tử giá trị
Hvào saup[0]. - Bước 4: Tung một đồng xu
- Nếu được mặt ngửa, di chuyển lên tầng trên và thêm phần tử giá trị H vào sau vị trí tương ứng ở tầng này. (
p[1]nếu là tầng 1,p[2]nếu là tầng 2, …..). - Nếu được mặt xấp, dừng thuật toán.
- Nếu được mặt ngửa, di chuyển lên tầng trên và thêm phần tử giá trị H vào sau vị trí tương ứng ở tầng này. (
- Bước 5: Quay lại bước 4.
Xóa phần tử khỏi danh sách
Gọi H là giá trị của phần tử cần phải xóa khỏi danh sách S. Thuật toán khá tương tự với việc thêm phần tử:- Bước 1: Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt:
p[N-1], p[N-2] … p[1], p[0] - Bước 2: Nếu không tìm thấy H, thuật toán kết thúc.
- Bước 3: Ngược lại, xóa tất cả các phần tử tại vị trí
p[N-1], p[N-2] … p[1], p[0]khỏi danh sách. - Bước 4: Xóa tất cả các tầng trống (tầng chỉ có hai phần tử NULL ở đầu và cuối)
Cài đặt
Chúng ta định nghĩa một phần tử của danh sách nhảy cóc như sau:class SkipListNode(object): def __init__(self, value): self.value = value self.next = None self.down = None
Kế tiếp, định nghĩa danh sách nhảy cóc với hàm khởi tạo:
class SkipList(object): def __init__(self): self.head = SkipListNode(None)
SkipList sử dụng biến head để lưu phần tử đầu tiên của tầng cao nhất, đây luôn là vị trí bắt đầu khi chúng ta duyệt danh sách.Dễ thấy rằng tác vụ Thêm và Tìm Kiếm đều cần phải duyệt qua danh sách với cùng một cách để tìm một giá trị, vì vậy chúng ta định nghĩa hàm
_search để có thể dùng chung cho cả hai như sau:def _search(self, value): last_nodes = [] current_node = self.head while True: if current_node.next is not None and current_node.next.value <= value: current_node = current_node.next else: last_nodes.append(current_node) if current_node.down is not None: current_node = current_node.down else: break return last_nodes
p[N-1], p[N-2], ... p[0] tương ứng với phần tử cuối cùng được duyệt đến tại các tầng N-1, N-1, ... 0Lúc này hàm
search của chúng ta khá đơn giản, chỉ cần kiểm tra giá trị của phần tử cuối cùng được trả về bởi _search:def search(self, value): last_nodes = self._search(value) if last_nodes[-1].value == value: return value return None
insert để thêm phần tử vào danh sách:def insert(self, new_value): last_nodes = self._search(new_value) # Stop if the value is already there in the list if last_nodes[-1].value == new_value: return last_created_node = None while True: new_node = SkipListNode(new_value) if len(last_nodes) > 0: last_node = last_nodes.pop() new_node.next = last_node.next last_node.next = new_node else: new_head = SkipListNode(None) new_head.down = self.head new_head.next = new_node new_node.next = None self.head = new_head new_node.down = last_created_node last_created_node = new_node # We are flipping the coin now if random.randint(0, 1) != 0: break
remove để xóa phần tử khỏi danh sách:def remove(self, value): current_node = self.head while True: if current_node.next is not None and current_node.next.value <= value: if current_node.next.value < value: current_node = current_node.next else: current_node.next = current_node.next.next if current_node.value is None and current_node.next is None\ and current_node.down is not None: self.head = current_node.down else: if current_node.down is not None: current_node = current_node.down else: break
_search: chúng ta vẫn duyệt từ head để tìm kiếm giá trị value. Điểm khác biệt là, nếu tìm thấy value ở bất kỳ tầng nào, chúng ta tiến hành xóa phần tử khỏi tầng đó đồng thời xóa luôn tầng này nếu không còn phần tử (khác NULL) nào khác.Độ phức tạp
- Trung bình:
- Bộ nhớ cần thiết: O(n)
- Thời gian tìm kiếm, thêm, xóa: O(logn)
- Tệ nhất:
- Bộ nhớ cần thiết: O(n*logn)
- Thời gian tìm kiếm, thêm, xóa: O(n)
Bàn luận thêm
- Các bạn có thể thấy ở thao tác Thêm phần tử, danh sách không thay đổi nếu chúng ta thêm một phần tử vốn đã có sẵn trong danh sách. Điều này đồng nghĩa với việc chúng ta mặc định các phần tử là đôi một khác nhau. Hãy sửa lại các đoạn mã ở trên để danh sách nhảy cóc của chúng ta có thể hỗ trợ các phần tử giống nhau.
- Để ý rằng độ phức tạp của Danh Sách Nhảy Cóc tương đương với Cây Nhị Phân, ngoại trừ việc Danh Sách Nhảy Cóc sử dụng nhiều bộ nhớ hơn. Bạn đọc có thể chỉ ra điểm nhỉnh hơn của Danh Sách Nhảy Cóc không ? (Gợi ý: chuyện gì xảy ra đối với hai danh sách khi có nhiều tiến trình muốn thêm phần tử vào danh sách cùng một lúc ?)
- Hãy viết hàm in ra trạng thái của danh sách nhảy cóc.
- Hãy viết hàm in ra các phần tử của danh sách nhảy cóc.
Tags:
Python Basic