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

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 getset 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.

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

kiennt

30 bài viết.
288 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
93 18
Mọi chuyện bắt đầu từ nắm 2013 trong quá trình xây dựng chức năng login với Facebook, tôi đã tìm ra một cách để tấn công vào các hệ thống login với...
kiennt viết hơn 2 năm trước
93 18
White
64 4
Trong tuần vừa rồi, mình có đọc chương 7 cuốn sách (Link). Bài viết này nhằm mục đích giúp mình tổng hợp lại những kiến thức đã học được về chương ...
kiennt viết 6 tháng trước
64 4
White
29 5
1. Đặt vấn đề Một trong các vấn đề của một hệ thống backend là bài toán điều phối request tới các nguồn dữ liệu. Xét bài toán với một hệ thống bl...
kiennt viết 2 năm trước
29 5
Bài viết liên quan
White
44 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 10 tháng trước
44 7
White
3 0
What is competitive programming? Sites like CodeForces, TopCoder, HackerRank, CodeChef,... ACMICPC, Olympiad in Informatics (for high school stude...
Nguyễn Lê Vũ Long viết hơn 1 năm trước
3 0
White
77 34
Bài viết thuộc chủ đề nghiên cứu trong nhóm hardcore của Cộng đồng Ruby Việt Nam Đọc manga trên mobile là một nhu cầu rất lớn, nhưng hiện nay chư...
Huy Trần viết gần 2 năm trước
77 34
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
30 bài viết.
288 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!