理想的数据结构,快速查找,快速更新和易于比较/排序

Question

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

• 数据进入,检查它是否已经存在于数据结构中(哈希相等,而不是时间戳).
• 如果是,请将时间戳更新为"now"
• 如果没有,请将其添加到时间戳为"now"的集合中

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

我使用它来接收传入的数据,如果它已经存在则更新它并清除超过X秒/分钟的数据.

多个数据结构也可以是一个有效的建议(我最初使用优先级队列+集合,但优先级队列不是最佳值,以不断更新值).

其他实现相同目标的方法也是受欢迎的.最终目标是跟踪元素是a)系统的新内容,b)系统中是否存在以及c)何时到期.

Answer 1

这是一个很好踩过的空间。您需要的是两个结构，您需要一些东西来告诉您您的密钥（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