python - 查找快、更新快、比较/排序方便的理想数据结构

Question

我正在寻找一个好的数据结构来包含具有 (hash, timestamp) 值的元组列表。基本上，我想按以下方式使用它:

• 数据进来，检查它是否已经存在于数据结构中(哈希相等，而不是时间戳)。
• 如果是，更新时间戳为“现在”
• 如果不是，则将其添加到时间戳为“现在”的集合中

我希望定期删除并返回一个早于特定时间戳的元组列表(我需要在“过期”时更新各种其他元素)。时间戳不必是任何特定的(它可以是 unix 时间戳、python datetime 对象或其他一些易于比较的哈希/字符串)。

我正在使用它来接收传入数据，如果它已经存在则更新它并清除早于 X 秒/分钟的数据。

多个数据结构也是一个有效的建议(我最初使用优先级队列 + 集合，但优先级队列对于不断更新值来说不是最佳选择)。

也欢迎使用其他方法来实现相同的目的。最终目标是跟踪元素何时 a) 对系统来说是新的，b) 已经存在于系统中以及 c) 它们何时过期。

Answer 1

这是一个非常受欢迎的空间。您需要的是两个结构，您需要一些东西来告诉您您的 key (在您的情况下为hash)是否为集合所知。为此，dict 非常适合；我们只是将 hash 映射到 timestamp，这样您就可以轻松地查找每个项目。按时间戳顺序迭代项目是一项特别适合堆的任务，堆由 heapq 提供。模块。每次我们看到一个键，我们都会将它添加到我们的堆中，作为 (timestamp, hash) 的元组。

不幸的是，没有办法查看堆砌列表并删除某些项目(因为，比如说，它们已被更新为稍后过期)。我们将通过忽略堆中具有与字典中的值不同的时间戳的条目来解决这个问题。

所以这是一个开始的地方，您可以向包装类添加方法以支持其他操作，或者更改数据的存储方式:

import heapq


class ExpiringCache(object):
    def __init__(self):
        self._dict = {}
        self._heap = []

    def add(self, key, expiry):
        self._dict[key] = expiry
        heapq.heappush(self._heap, (expiry, key))

    def contains(self, key):
        return key in self._dict

    def collect(self, maxage):
        while self._heap and self._heap[0][0] <= maxage:
            expiry, key = heapq.heappop(self._heap)
            if self._dict.get(key) == expiry:
                del self._dict[key]

    def items(self):
        return self._dict.items()

创建缓存并添加一些项目

>>> xc = ExpiringCache()
>>> xc.add('apples', 1)
>>> xc.add('bananas', 2)
>>> xc.add('mangoes', 3)

重新添加一个过期时间更晚的项目

>>> xc.add('apples', 4)

收集所有“早于”两个时间单位的东西

>>> xc.collect(2)    
>>> xc.contains('apples')
True
>>> xc.contains('bananas')
False