Bạn có chắc chắn muốn xóa bài viết này không ?
Bạn có chắc chắn muốn xóa bình luận này không ?
Cài đặt thuật toán LRU Cache
Thuật toán LRU cache
Thuật toán cache thì khá đơn giản, bạn chỉ cần một hash table để lưu giữ giá trị của từng key.
Khi đó, việc set cache, và get cache sẽ có độ phức tạp trung bình là O(1)
Tuy nhiên, do memory là giới hạn, nên khi cache đầy, ta cần loại bỏ một số phần tử ra khỏi cache.
Thuật toán LRU lựa chọn những phần tử nào mà "lâu chưa được dùng tới" nhất.
Một key được định nghĩa là "dùng", khi có một thao tác get
hoặc set
vào key đó.
Để có thể cài đặt LRU cache, bạn sẽ cần phải có 2 cấu trúc dữ liệu: một cấu trúc để lưu cặp key, value - cấu trúc này dễ thấy sẽ là HashMap, một cấu trúc để lưu và thay đổi vị trị các key theo chiều tăng dần theo thời gian. Thuật toán của chúng ta sẽ phụ thuộc nhiều vào cấu trúc để lưu các key.
Một cách dễ hình dung là sử dụng PriorityQueue để cài đặt cấu trúc dữ liệu này. Nhưng PriorityQueue, thì độ phức tạp khi set, get và, incr các key là O(logN), nên nếu cài đặt bằng PriorityQueue thì độ phức tạp của get
và set
cache sẽ là O(logN).
Có mấy quan sát cho chúng ta khi xem xét cấu trúc dữ liệu lưu các key đó là:
- cấu trúc này cần có thao tác remove phần tử đầu tiên (phẩn tử có thời gian truy cập nhỏ nhất) (1)
- cấu trúc này cần có thao tác chuyển vị trị 1 phẩn tử bất kỳ về cuối (hay là set timestamp lên (2) timestamp hiện tại)
- cấu trúc này cần có thao tác để search 1 phần tử theo key
Để search thì tốc độ tốt nhất là O(logN), nên nếu muốn xây dựng thuật toán tốt hơn O(logN), chúng ta cần loại bọ thao tác cuối. May thay, chúng sẽ có HashMap, HashMap có thể lưu trữ luôn vị trí của key.
Giờ chỉ cần thao tác (1) và (2). Do đó, thay vì cần sử dụng PriorityQueue, ta sẽ dùng Double Linked List, và lưu thêm head
, tail
của List này là có thể thực hiện 2 thao tác kia bằng O(1)
Chi tiết cài đặt
class Node(object):
def __init__(self, key, value, next=None, prev=None):
self.key = key
self.value = value
self.set_next(next)
self.set_prev(prev)
def set_next(self, next):
if next is None:
self.next = None
else:
next.prev = self
self.next = next
def set_prev(self, prev):
if prev is None:
self.prev = None
else:
prev.next = self
self.prev = prev
class LRUCache(object):
def __init__(self, capacity):
assert capacity > 0, 'Can not init cache with capacity is 0'
self.capacity = capacity
self.queue_size = 0
self.cache = {}
self.head = None
self.tail = None
def remove_head(self):
next_head = self.head.next
if next_head:
next_head.prev = None
self.head.next = self.head.prev = None
del self.cache[self.head.key]
self.head = next_head
def set_tail(self, node):
if self.tail is None:
self.tail = node
else:
node.set_prev(self.tail)
self.tail = node
if self.head is None:
self.head = node
def push_to_end(self, node):
if self.queue_size == self.capacity:
self.remove_head()
else:
self.queue_size += 1
self.set_tail(node)
def link_nodes_before_and_after(self, node):
if node.prev:
node.prev.set_next(node.next)
elif node.next:
# in this case node is head
node.next.set_prev(None)
self.head = node.next
def move_to_end(self, node):
if node == self.tail:
return
self.link_nodes_before_and_after(node)
self.set_tail(node)
node.next = None
def get(self, key):
node = self.cache.get(key)
if node is None:
return None
else:
self.move_to_end(node)
return node.value
def set(self, key, value):
node = self.cache.get(key)
if node is None:
node = Node(key, value)
self.push_to_end(node)
self.cache[key] = node
else:
node.value = value
self.move_to_end(node)
Cám ơn anh em #hardcore đã thảo luận và @huydx cho đề bài và review code giúp mình.







