Dynadot Jtti 华纳云 搬瓦工 腾讯云

LFU 缓存(LFU Cache)Python 3 实现代码

GigsGigsCloud

LFU 缓存,也就是 LFU Cache,最近写的比较多,就在此记录一下。之前华为面试的时候也遇到了这个题,还好写过。LFU 缓存的定义就不用多说了吧,就是删除最近使用频率最少的一项,如果使用频率一样,就按照最近使用时间来删。之前实现 LFU Cache 写了一大堆代码,最近发现有比较简单的实现方法,测试了一下是没有什么问题,但是还是先不分享了,下面主要转载记录一下 LeetCode 上面的 LFUCache 这个类的实现方法,代码是基于 Python 3 的。

LFU Cache 实现起来比较复杂,最常见的是用二级链表。最近发现似乎可以直接用 pqdict 这个库来实现,并且目前也已经实现了,测试了一下并没有什么 bug。

下面分享转载一下 LeetCode 上面的 LFU Cache 问题,并转载上面最热门的一个题解,仅作记录。

一、问题描述

请你为最不经常使用(LFU)缓存算法设计并实现数据结构。

实现 LFUCache 类:

  • LFUCache(int capacity) – 用数据结构的容量 capacity 初始化对象
  • int get(int key) – 如果键存在于缓存中,则获取键的值,否则返回 -1。
  • void put(int key, int value) – 如果键已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量时,则应该在插入新项之前,使最不经常使用的项无效。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最久未使用 的键。

注意「项的使用次数」就是自插入该项以来对其调用 getput 函数的次数之和。使用次数会在对应项被移除后置为 0。

进阶:

你是否可以在 O(1) 时间复杂度内执行两项操作?

二、输入输出示例

示例:

输入:
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释:
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1);
lFUCache.put(2, 2);
lFUCache.get(1);      // 返回 1
lFUCache.put(3, 3);   // 去除键 2
lFUCache.get(2);      // 返回 -1(未找到)
lFUCache.get(3);      // 返回 3
lFUCache.put(4, 4);   // 去除键 1
lFUCache.get(1);      // 返回 -1(未找到)
lFUCache.get(3);      // 返回 3
lFUCache.get(4);      // 返回 4

三、LFUCache

class LFUCache:
    # 用于记录最后使用时间的链表 
    class Node:
        def __init__(self, key: int):
            self.prev = None
            self.next = None
            self.key = key

        def add(self, node):
            self.next = node
            node.prev = self

        def delete_self(self):
            if self.next is not None:
                self.next.prev = self.prev
            if self.prev is not None:
                self.prev.next = self.next

    # 用于记录使用次数的链表
    class Layer:
        def __init__(self, depth: int):
            self.prev = None
            self.next = None
            # depth表示使用次数
            self.depth = depth

            # 这个就是二级的hashmap 加上下面的二级链表 做成了LRU的缓存
            self.queue = {}
            # 二级链表头
            self.start = LFUCache.Node(-1)
            # 二级链表尾巴
            self.end = self.start

    def __init__(self, capacity: int):
        self.capacity = capacity

        # 这个就是一级的hashmap 加上下面的链表 做成了LFU的缓存
        self.data = {}
        # 这个map用于指向链表结点,如果重新设计的话,可以和上面的map合并的
        self.kToLayer = {}
        # 链表尾巴
        self.end_layer = None
        # 链表头
        self.top_layer = self.Layer(0)

    def get(self, key: int) -> int:
        r = self.data.get(key, -1)
        if r != -1:
            # 更新记录使用次数的链表
            self.kToLayer[key] = self.update_layer(self.kToLayer[key], key)
        return r

    def put(self, key: int, value: int) -> None:
        # 1. capacity为0的话直接不干了
        if self.capacity == 0:
            return
        # 2. 数据已经存在的话,就更新记录使用次数的链表
        if self.data.get(key) is not None:
            self.data[key] = value
            self.kToLayer[key] = self.update_layer(self.kToLayer[key], key)
            return

        # 3.1 如果超过了限度,就从链表头取出一个,删掉
        if len(self.data) >= self.capacity:
            key_to_del = self.pop_queue_from_layer(self.top_layer)
            self.data.pop(key_to_del)
            now = self.kToLayer[key_to_del]
            if len(now.queue) == 0 and now.depth > 0:
                self.clear_layer(now)
            self.kToLayer.pop(key_to_del)
        # 3.2 把新的加进去
        self.data[key] = value
        self.add_key_to_layer(self.top_layer, key)
        self.kToLayer[key] = self.top_layer

    # --------------下面都是链表操作的辅助方法,注意链表的穿插不要丢了节点---------------

    def add_key_to_layer(self, now: Layer, key: int):
        n = self.Node(key)
        now.queue[key] = n
        now.end.add(n)
        now.end = n

    def delete_key_of_layer(self, layer: Layer, key: int):
        node = layer.queue[key]
        if node == layer.end:
            layer.end = node.prev
        node.delete_self()
        layer.queue.pop(key)

    # 一级链表的更新(layer更新)
    def update_layer(self, now: Layer, key: int) -> Layer:
        self.delete_key_of_layer(now, key)

        # 注意那个depth+1 就是对应着频次的+1。ps 如果增加的值不定,就不应该用链表了,可能需要红黑树了
        # 1. 当前已是链表最后 即频次最高 ->需要创建新的layer
        if now.next is None:
            next_layer = self.Layer(now.depth + 1)
            self.add_key_to_layer(next_layer, key)
            self.insert_layer(now, next_layer)
            out = next_layer
        # 2. 下一个layer直接跨了好几个深度 ->需要创建新的layer
        elif now.next.depth > now.depth + 1:
            next_layer = self.Layer(now.depth + 1)
            self.add_key_to_layer(next_layer, key)
            self.insert_layer(now, next_layer)
            out = next_layer
        # 3. 下一个layer刚好是目标深度 ->不需要创建新的layer
        else:
            self.add_key_to_layer(now.next, key)
            out = now.next

        # 如果这一层空了,就把它删掉,节省空间
        if len(now.queue) == 0 and now.depth > 0:
            self.clear_layer(now)
        return out

    def insert_layer(self, now: Layer, target: Layer):
        if now.next is None:
            target.prev = now
            now.next = target
            self.end_layer = target
        else:
            target.prev = now
            target.next = now.next
            now.next.prev = target
            now.next = target

    def clear_layer(self, now: Layer):
        if now.next is None:
            now.prev.next = None
            self.end_layer = now.prev
        elif now.prev is None:
            now.next.prev = None
        else:
            now.prev.next = now.next
            now.next.prev = now.prev

    def pop_queue_from_layer(self, now: Layer) -> int:
        # 传进来时就是一级链表头了
        # for top layer
        if len(now.queue) == 0 and now.depth == 0:
            now = now.next

        # 取二级链表的第一个key
        key = now.start.next.key
        self.delete_key_of_layer(now, key)

        if len(now.queue) == 0 and now.depth > 0:
            self.clear_layer(now)
        return key
Dynadot Hostwinds
赞(2)
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《LFU 缓存(LFU Cache)Python 3 实现代码
文章链接:https://oldtang.com/5708.html
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。