如何在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, ... 是插入或更新这个条目的时间。

目标是实现一个高效的缓存，能够检查某个键是否存在，验证值的时效性（因为随着时间推移，它可能会过时），并在缓存满的时候移除最旧的键。这个字典应该支持堆操作，可以通过嵌套的“时间”键或者列表的第一个元素来实现。

目前考虑的选项有：

1. 从字典中形成一个堆（缺点是这个操作很耗时，复杂度是O(n^2)）。
2. 实现一个类，分别存储堆和字典（缺点是需要同步堆和字典中的数据，比较复杂）。
3. 简单地遍历字典，复杂度是O(n)。这个选项因为简单而受到青睐，但可能不是最优的。

有没有更高效的解决方案，或者其他方法可以避免创建自定义的数据结构呢？

Answer 1

Python中的dict（字典）本身就是按照插入顺序排列的（在旧版本中，可以使用collections.OrderedDict）。这就像一个按时间排序的堆，意味着最早插入的项目总是在最前面。如果你想更新某个值，不如先把这个项目删除再重新插入，这样更新后的项目就会被放到最后面。

如果你想把dict用作基于时间的缓存，可以采用以下方法。你可以把这个功能做成一个单独的子类，提供一些辅助函数，或者把代码直接写在一起。做成子类会更好，避免误用，但需要很多特别的方法，所以我会展示一些简单的辅助函数，并假设给定了一个有效时间（ttl）。

• 项目的格式应该是"key": (time, value)。使用不可变的值（比如tuple或NamedTuple）是有好处的，这样可以防止时间不合法的问题。
• 在插入时，先删除任何之前同样键的项目。这样可以确保新插入的项目放在最后。

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]