python lfu实现

以下是一种基本的 Python 实现 LFU 缓存的方法：

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.freq = {}
        self.min_freq = 0

    def get(self, key):
        if key not in self.cache:
            return -1

        # 更新频率
        freq = self.freq[key]
        self.freq[key] = freq + 1

        # 更新最小频率
        if freq == self.min_freq and not self.freq.get(self.min_freq):
            self.min_freq += 1

        return self.cache[key]

    def put(self, key, value):
        if not self.capacity:
            return

        # 如果键已经存在，更新其值并增加频率
        if key in self.cache:
            self.cache[key] = value
            self.get(key)
            return

        # 如果容量已满，删除最少使用的键
        if len(self.cache) == self.capacity:
            del self.cache[self.freq[self.min_freq][0]]
            del self.freq[self.min_freq][0]

            if not self.freq[self.min_freq]:
                del self.freq[self.min_freq]
                self.min_freq += 1

        # 插入新键
        self.cache[key] = value
        self.freq.setdefault(1, []).append(key)
        self.min_freq = 1

以上实现使用两个字典来维护 LFU 缓存。 `cache` 字典用于存储键值对，而 `freq` 字典用于存储键的频率。 `min_freq` 变量用于跟踪最小频率，以便在删除最少使用的键时使用。 `get` 和 `put` 方法分别用于获取和插入键值对，并根据键的频率更新 `freq` 和 `min_freq` 变量。