Cài đặt thuật toán LRU Cache

algorithm

35

kiennt viết ngày 09/10/2016

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.