Cài đặt thuật toán LRU Cache trong lập trình

Trong lập trình, việc sử dụng bộ nhớ cache là cách hiệu quả để tăng tốc độ truy xuất dữ liệu. Một trong những thuật toán quản lý bộ đệm phổ biến là Least Recently Used (LRU) Cache. Thuật toán này dựa trên nguyên tắc: dữ liệu không sử dụng trong thời gian dài sẽ được loại bỏ khi cần thêm không gian lưu trữ. Bài viết này sẽ hướng dẫn cách cài đặt thuật toán LRU Cache bằng cách sử dụng các cấu trúc dữ liệu thường gặp trong lập trình.

Ý tưởng chính của thuật toán

Thuật toán LRU Cache duy trì một tập hợp các khóa và giá trị, cùng với thông tin về lần cuối cùng mỗi mục được truy cập. Khi một mục mới được thêm vào, nếu cache đầy, mục ít được sử dụng nhất sẽ bị loại bỏ. Điều này đòi hỏi hai thao tác chính:

Kiểm tra và cập nhật thời gian truy cập của các mục.
Loại bỏ mục ít được sử dụng nhất.

Các cấu trúc dữ liệu cần dùng

Để cài đặt LRU Cache hiệu quả, chúng ta cần:

Hash Map: Để tra cứu các giá trị theo khóa trong thời gian O(1).
Doubly Linked List: Để lưu trữ các mục theo thứ tự sử dụng và dễ dàng xoá, cập nhật mục.

Các bước triển khai

Bước 1: Xác định cấu trúc Node

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

Bước 2: Cấu trúc LRU Cache và các hành vi

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
    
    def _add(self, node):
        prev_node = self.tail.prev
        prev_node.next = node
        self.tail.prev = node
        node.prev = prev_node
        node.next = self.tail
    
    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.value
        return -1
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        
        new_node = Node(key, value)
        self._add(new_node)
        self.cache[key] = new_node
        
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

Giải thích chi tiết

Khởi tạo: Cache được khởi tạo với một dung lượng cố định. Tạo một linked list với hai node đặt biệt: head và tail.
Remove: Hàm _remove để loại bỏ một node khỏi linked list.
Add: Hàm _add thêm một node vào trước tail.
Get: Khi truy xuất một giá trị, đưa node tương ứng về cuối linked list để đánh dấu là vừa sử dụng.
Put: Thêm một mục mới. Nếu khóa đã tồn tại, loại bỏ node cũ trước khi thêm. Nếu cache đầy, xoá node đầu tiên của linked list.

Lợi ích và hạn chế

Lợi ích:

Tốc độ: Cả hai thao tác truy cập và cập nhật đều có độ phức tạp thời gian O(1).
Quản lý bộ nhớ hiệu quả: Chỉ giữ lại các mục được truy cập gần đây, tối ưu cho các ứng dụng yêu cầu truy xuất nhanh.

Hạn chế:

Không phù hợp cho dữ liệu lớn vượt quá dung lượng bộ nhớ: Chỉ nên sử dụng khi dung lượng bộ đệm có thể quản lý được.

Kết luận

Việc triển khai thuật toán LRU Cache trong lập trình giúp quản lý bộ nhớ hiệu quả, tăng cường hiệu suất cho ứng dụng. Hi vọng qua bài viết này, bạn đã có cách nhìn cơ bản về cấu trúc và cách cài đặt LRU Cache. Hãy thử áp dụng trong các dự án của mình để trải nghiệm hiệu quả mà nó mang lại.

Đăng ký