Python基于双向链表实现LFU缓存算法

算法目标与前置条件

LFU（Least Frequently Used）算法的核心目标是淘汰历史访问频次最低的数据块，其调度依据与LRU策略存在本质差异。为实现该逻辑，需预先确保开发环境中已集成基础的双向链表管理类（用于维持同频节点的时间序列）以及标准的Node基类。完成依赖对齐后，即可按以下步骤构建完整的调度内核。

第1步：扩展节点类以记录频率

目的：为数据载体附加热度追踪维度，支撑后续的频次对比逻辑。
入口与动作：创建子类继承原始节点定义，在构造阶段覆写初始化流程。
重要参数：key作为路由标识，value承载业务负载，freq固定赋值为初始计数。
完成状态：调用LFUNode(key, value)后返回的对象内部自带零频状态槽位，可随时接受外部累加指令。

class LFUNode(Node):
    def __init__(self, key, value):
        """
        LFU节点 增加频率属性
        :param key: 键名标识
        :param value: 存储的实际数据
        """
        super(LFUNode, self).__init__(key, value)
        self.freq = 0  # 初始访问频率归零

第2步：初始化缓存调度器与频率索引

目的：搭建双轨映射体系，兼顾O(1)键查找与同频组管理。
入口与动作：声明LFUCache容器，在__init__内预分配哈希空间。
重要参数：capacity划定物理容量红线，超出阈值触发熔断淘汰。
完成状态：self.map完成键值索引绑定，self.freq_map预留空字典供后续按次级聚合。

class LFUCache(object):
    def __init__(self, capacity=0xffffffff):
        """
        LFU缓存置换算法 最不经常使用
        :param capacity: 最大缓存容量限制
        """
        self.capacity = capacity
        self.size = 0
        self.map = {}         # key -> LFUNode 映射表
        self.freq_map = {}    # freq -> DoubleLinkedList 频率分组队列

第3步：实现核心更新逻辑与淘汰机制

目的：闭环处理节点层级跃迁与越界清理，保障系统资源不泄露。
入口与动作：封装私有迁移函数__update_freq，并在公开接口get与put中强制调用。
重要参数：节点指针、当前频次快照、目标频率阈值。淘汰逻辑依赖min(self.freq_map)定位最冷区间，并通过链表尾删执行硬卸载。
完成状态：原频段队列缩容，新频段头插生效；容量打满时旧键自动销毁，控制台或调用方捕获到的返回值符合预期衰减曲线。

    def __update_freq(self, node):
        """内部私有方法：更新节点频率并迁移队列"""
        freq = node.freq

        # 当前节点所在频率存在，从当前频率链表中移除当前节点
        if freq in self.freq_map:
            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)

        return node

    def get(self, key):
        """获取元素"""
        if key not in self.map:
            return None
        
        old_node = self.map.get(key)
        new_node = self.__update_freq(old_node)
        self.map[key] = new_node
        return new_node.value

    def put(self, key, value):
        """设置元素"""
        if key in self.map:
            old_node = self.map.get(key)
            old_node.value = value
            new_node = self.__update_freq(old_node)
            self.map[key] = new_node
        else:
            # 节点容量达到上限，移除最小频率链表头部的节点
            if self.size >= self.capacity:
                min_freq = min(self.freq_map)
                evict_node = self.freq_map[min_freq].pop()
                del self.map[evict_node.key]
                self.size -= 1

            # 构建新的节点并更新频率
            new_node = LFUNode(key, value)
            new_node = self.__update_freq(new_node)
            self.map[key] = new_node
            self.size += 1
        return new_node

    def print_status(self):
        """打印当前链表分布状态"""
        for freq, link in self.freq_map.items():
            print("frequencies： %d" % freq)
            link.print()

第4步：封装读取写入接口并验证运行状态

目的：通过标准化压测流确认调度器在读写交替下的自洽性。
入口与动作：撰写__main__防护块，实例化指定容量的缓存实例并串行走查指令。
重要参数：预设硬编码容量4，混合注入put与get序列制造频率偏移。
完成状态：程序顺利跑通全量分支，终端按序渲染各时间切片的热度拓扑，未抛出索引越界或死锁异常。

if __name__ == '__main__':
    lfu_cache = LFUCache(4)
    lfu_cache.put(1, 1)
    lfu_cache.print_status()
    
    lfu_cache.put(2, 2)
    lfu_cache.print_status()
    print(lfu_cache.get(1))  # 触发键1频率+1
    lfu_cache.print_status()
    
    lfu_cache.put(3, 3)
    lfu_cache.print_status()
    lfu_cache.put(4, 4)
    lfu_cache.print_status()
    lfu_cache.put(5, 5)  # 触发淘汰机制
    lfu_cache.print_status()
    print(lfu_cache.get(2))
    lfu_cache.put(4, 400)

完成判断与注意事项

对照上述步骤执行完毕且终端输出稳定后，即代表LFU内核已就绪。日常维护时建议重点监控freq_map的动态膨胀率，高频短生命周期场景下频率整数可能持续攀升，可适当引入定期归零或滑动窗口策略防溢出。本实现依赖外置的DoubleLinkedList与基类抽象，实际工程落地前请核对源码路径与接口契约的一致性。

以上就是基于Python双向链表实现LFU算法的详细步骤与代码解析，更多关于数据结构与算法优化的资料请关注本站其它相关文章！