Chương trình triển khai Bộ nhớ đệm ít được sử dụng nhất trong Python

Giả sử chúng ta muốn 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ó phải hỗ trợ các hoạt động sau:

• get (key) - Điều này giúp lấy giá trị của khóa nếu khóa tồn tại trong bộ đệm, nếu không thì trả về −1.

• set (key, value) - Giá trị 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.set (1, 1); cache.set (2, 2); cache.get (1); cache.set (3, 3); cache.get (2); cache.set (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 là 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ề

• Xác định một tập hợp hàm (). Đ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] trong đơn hàng năm

    • 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

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

Ví dụ

from collections import defaultdict, OrderedDict
class LFUCache:
   def __init__(self, capacity):
      self.remain = capacity
      self.least_freq = 1
      self.node_for_freq = defaultdict(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 set(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.set(1, 1)
cache.set(2, 2)
print(cache.get(1))
cache.set(3, 3)
print(cache.get(2))
cache.set(4, 4)
print(cache.get(1))
print(cache.get(3))
print(cache.get(4))

Đầu vào

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

Đầu ra

1
−1
1
−1
4