如何在Python中实现高效支持字典和堆操作的缓存？

Question

是否有一种 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”或列表的第零个元素来支持堆操作。

当前考虑的选项：

1. 从字典中形成堆（缺点 - 昂贵的操作 O(n^2)）。
2. 实现一个单独存储堆和字典的类（缺点 - 同步堆和字典中数据的复杂性）。
3. 在 O(n) 中对字典进行简单迭代。此选项因其简单性而受到青睐，但可能不是最佳选择。

是否有更有效的解决方案或不同的方法来避免创建自定义数据结构？

Answer 1

Python 的

dict

已经是插入排序的（在旧版本上，使用

collections.OrderedDict

），类似于按时间排序的堆。这意味着最早插入的项目始终位于最前面。不更新值，而是删除并插入项目以强制将更新的项目移到后面。

为了将

dict

用作基于时间的缓存，请使用以下方法。您可以将其转换为单独的子类，提供辅助函数，或添加内联代码。子类更好，可以避免误用，但涉及许多特殊方法，因此我将展示更简单的辅助函数，并假设给出了生存时间 (

ttl

)。

• 项目应采用

  "key": (time, value)

  形式。具有不可变值（即

  tuple

  或

  NamedTuple

  ）是有利的，以防止有效

  time

  的约束无效。
• 插入时，删除同一键的所有先前项目。这会强制将项目插入到最后一个位置。

  def set(cache, key, value):
       cache.pop(key, None)  # clear the previous position if any
       cache[key] = (time.monotonic(), value))
  

• 访问时，只需检查时间即可。您可能希望在访问时直接驱逐过时的密钥以提高效率。

  def get(cache, key):
       key_time, value = cache[key]
       if key_time < time.monotonic() + ttl:  # check timestamp validity
           del cache[key]
           raise KeyError(key)
       return value
  

• 要驱逐最旧的项目，只需获取第一个密钥并将其删除即可。

  def free(cache):
       if cache:
          oldest_key = next(iter(cache))
          del cache[oldest_key]
  

• 要驱逐所有过时的项目，只需迭代直到第一个仍然有效的键。

  def clean(cache):
       outdated, deadline = [], time.monotonic() + ttl
       for key, (key_time, _) in cache.items():
           if key_time < deadline:
               outdated.append(key)
           else:  # all following keys are valid as well
               break
       for key in outdated:
           del cache[key]