用双向链表实现内存置换算法(四)

这一篇是使用双向链表实现第三个内存置换算法----LFU

LFU算法分析：

最不经常使用算法，在缓存满了的时候，先淘汰使用频率最少的，这里我们就需要用一个变量来记录数据的使用频率。但是会有一个情况，就是使用频率相同的时候如何去处理，这里我是采用map来记录，key为使用的频率，value是双向链表，当缓存满了的时候，找到最低频率的value，根据FIFO的规则去淘汰。

• 第一步，我们先给每一个节点增加一个记录频率的属性

class LFUNode(Node):
    def __init__(self, key, value):
        self.freq = 0
        super(LFUNode, self).__init__(key, value)
           

• 第二步，实现LFU算法
  • 这里需要增加一个update()方法来更新节点的频率

这里直接附上代码，在结尾会对一些细节进行解释：

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        # key: 频率, value: 频率对应的双向链表
        self.freq_map = {}
        self.size = 0

    # 更新节点频率的操作
    def __update_freq(self, node):
        freq = node.freq

        # 删除
        node = self.freq_map[freq].remove(node)
        if self.freq_map[freq].size == 0:
            del self.freq_map[freq]

        # 更新
        freq += 1
        node.freq = freq
        if freq not in self.freq_map:
            self.freq_map[freq] = DoubleLinkedList()
        self.freq_map[freq].append(node)

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map.get(key)
        self.__update_freq(node)
        return node.value

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

        # 缓存命中
        if key in self.map:
            node = self.map.get(key)
            node.value = value
            self.__update_freq(node)
        # 缓存未命中
        else:
            if self.capacity == self.size:
                # 最低频率
                min_freq = min(self.freq_map)
                node = self.freq_map[min_freq].pop()
                del self.map[node.key]
                self.size -= 1
            node = LFUNode(key, value)
            node.freq = 1
            self.map[key] = node
            if node.freq not in self.freq_map:
                self.freq_map[node.freq] = DoubleLinkedList()
            self.freq_map[node.freq].append(node)
            self.size += 1
           

• init: 在初始化中增加了一个记录频率的map
• get： get方法和之前一样，没有key直接返回-1，有就返回数据
• update： 在进行put的时候，node存在，则先将原来的node删除，将这个频率+1，再放入相应的链表中。
• put： 缓存命中时，更新数据使用频率，缓存未命中，如果缓存未满，就放在频率为1的链表中，如果缓存满了，则把使用频率最低的链表根据FIFO原则替换。