Python中如何实现兼具字典与堆操作的高效缓存及最优方案？

核心疑问 #

• 如何在Python中实现同时高效支持字典操作与堆操作的缓存？
• 是否存在一种Python数据结构，能无缝结合字典（值为嵌套字典或列表）与堆，支持基于嵌套结构内的特定值进行排序？

候选缓存结构示例 #

以下是两种候选的缓存结构：
第一种（值为嵌套字典）：

cache = {"key1": {"time": time1, "info": "key1 info"}, "key2": {"time": time2, "info": "key2 info"}, ...}

第二种（值为列表）：

cache = {"key1": [time1, "key1 info"], "key2": [time2, "key2 info"], ...}

其中time1、time2等代表条目的插入或更新时间。

缓存需实现的功能 #

该缓存需具备以下功能：

• 检查指定键是否存在
• 验证缓存条目的新鲜度（支持随时间过期）
• 缓存容量满时自动移除最旧的条目
• 支持基于嵌套键"time"或列表第0个元素进行堆相关操作

现有方案及缺点 #

目前已考虑三种方案，但均存在明显缺点：

1. 每次需要堆操作时从字典重新构建堆：操作开销极大，时间复杂度为O(n²)
2. 自定义类分别维护堆和字典：需要手动同步两者的数据，实现复杂度高
3. 直接遍历字典查找目标条目：时间复杂度为O(n)，实现简单但性能无法达到最优

最终询问 #

请问是否存在更高效的解决方案？或者有没有无需自定义数据结构的替代实现方式？

内容的提问来源于stack exchange，提问作者maskalev