Bộ nhớ đệm LFU bằng Python

Giả sử chúng ta muốn thiết kế và triển khai một cấu trúc dữ liệu cho hệ thống bộ đệm thường được sử dụng ít nhất (LFU). Nó sẽ hỗ trợ các hoạt động sau -

• get (key) - Điều này sẽ được sử dụng để nhận giá trị của khóa nếu khóa tồn tại trong bộ nhớ cache, nếu không trả về -1.

• put (khóa, giá trị) - Điều này sẽ được sử dụng để đặt hoặc chèn giá trị nếu khóa chưa có.

Khi bộ nhớ đệm đạt đến dung lượng tối đa, nó sẽ làm mất hiệu lực của phần tử ít được sử dụng nhất trước khi chèn phần tử mới.

Vì vậy, nếu LFUCache được khởi tạo với dung lượng 2 và gọi các phương thức này là cache.put (1, 1); cache.put (2, 2); cache.get (1); cache.put (3, 3); cache.get (2); cache.put (4, 4); cache.get (1); cache.get (3); cache.get (4); thì đầu ra sẽ lần lượt là 1, -1,1, -1,4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Trình khởi tạo sẽ lấy giá trị dung lượng

• còn lại:=công suất

• less_freq:=1

• node_for_freq:=bản đồ lưu trữ dữ liệu theo lệnh chèn

• node_for_key:=một bản đồ mới

• Định nghĩa một hàm _update (). Điều này sẽ lấy chìa khóa, giá trị

• x, freq:=node_for_key [key]

• xóa phần tử khỏi node_for_freq [freq] tương ứng với khóa

• nếu kích thước của node_for_freq [less_freq] bằng 0 thì

  • less_freq:=less_freq + 1

• node_for_freq [freq + 1, key]:=value, freq + 1

• node_for_key [key]:=value, freq + 1

• Định nghĩa một hàm get (). Điều này sẽ có chìa khóa

• nếu khóa không có trong node_for_key khác 0, thì

  • trả về -1

• giá trị:=node_for_key [key, 0]

• _ cập nhật (khóa, giá trị)

• giá trị trả về

• Định nghĩa một hàm put (). Điều này sẽ lấy chìa khóa, giá trị

  • nếu khóa trong node_for_key khác 0, thì

    • _ cập nhật (khóa, giá trị)

  • nếu không,

    • node_for_key [key]:=value, 1

    • node_for_freq [1, key]:=value, 1

    • nếu vẫn là 0, thì

      • remove:=xóa một phần tử khỏi node_for_freq [less_freq] theo thứ tự năm mươi

      • xóa phần tử khỏi node_for_key tương ứng với khóa bị xóa [0]

    • nếu không,

      • còn lại:=còn lại - 1

    • less_freq:=1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

import collections
class LFUCache:
   def __init__(self, capacity):
      self.remain = capacity
      self.least_freq = 1
      self.node_for_freq = collections.defaultdict(collections.OrderedDict)
      self.node_for_key = dict()
   def _update(self, key, value):
      _, freq = self.node_for_key[key]
      self.node_for_freq[freq].pop(key)
      if len(self.node_for_freq[self.least_freq]) == 0:
         self.least_freq += 1
      self.node_for_freq[freq+1][key] = (value, freq+1)
      self.node_for_key[key] = (value, freq+1)
   def get(self, key):
      if key not in self.node_for_key:
         return -1
      value = self.node_for_key[key][0]
      self._update(key, value)
      return value
   def put(self, key, value):
      if key in self.node_for_key:
         self._update(key, value)
      else:
         self.node_for_key[key] = (value,1)
         self.node_for_freq[1][key] = (value,1)
         if self.remain == 0:
            removed = self.node_for_freq[self.least_freq].popitem(last=False)
            self.node_for_key.pop(removed[0])
         else:
            self.remain -= 1
            self.least_freq = 1
cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3)
print(cache.get(2))
cache.put(4, 4)
print(cache.get(1))
print(cache.get(3))
print(cache.get(4))

Đầu vào

cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

Đầu ra

1
-1
1
-1
4