Python中的LFU快取

假設我們想設計和實現一種用於最低使用頻率(LFU)快取系統的資料結構。它應該支援以下操作：

  • get(key) – 如果鍵存在於快取中，則用於獲取鍵的值；否則返回-1。

  • put(key, value) – 用於設定或插入值，前提是鍵不存在。

當快取達到最大容量時，在插入新元素之前，應使最低使用頻率的元素失效。

因此，如果LFUCache初始化容量為2，並呼叫這些方法：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); 那麼輸出將分別為1，-1，1，-1，4。

為了解決這個問題，我們將遵循以下步驟：

  • 初始化程式將接收容量值

  • remain := capacity

  • least_freq := 1

  • node_for_freq := 一個對映，用於根據插入順序儲存資料

  • node_for_key := 一個新的對映

  • 定義一個函式_update()。它將接收key和value

  • x, freq := node_for_key[key]

  • 從node_for_freq[freq]中刪除對應於key的元素

  • 如果node_for_freq[least_freq]的大小為0，則

    • least_freq := least_freq + 1

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

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

  • 定義一個函式get()。它將接收key

  • 如果key不在node_for_key中，則

    • 返回-1

  • value := node_for_key[key, 0]

  • _update(key, value)

  • 返回value

  • 定義一個函式put()。它將接收key和value

    • 如果key在node_for_key中，則

      • _update(key, value)

    • 否則，

      • node_for_key[key] := value,1

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

      • 如果remain為0，則

        • removed := 按FIFO順序從node_for_freq[least_freq]中刪除一個元素

        • 從node_for_key中刪除對應於removed[0]的元素

      • 否則，

        • remain := remain - 1

      • least_freq := 1

示例

讓我們來看下面的實現，以便更好地理解：

線上演示

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))

輸入

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)

輸出

1
-1
1
-1
4

更新於：2020年7月21日

2K+瀏覽量

啟動你的職業生涯

透過完成課程獲得認證

開始學習
廣告