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

Pythondict已经按插入顺序排序(在旧版本中，使用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]