6

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

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

定期，我希望删除并返回早于特定时间戳的元组列表（当它们“过期”时，我需要更新各种其他元素）。时间戳不必是特定的（它可以是 unix 时间戳、pythondatetime对象或其他一些易于比较的哈希/字符串）。

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

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

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

4

5 回答 5

4

这是一个相当不错的空间。您需要的是两个结构，您需要一些东西来告诉您您的密钥（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
于 2013-10-09T20:12:43.170 回答
3

我能想到的最接近具有您想要的属性的单个结构的是展开树（以您的哈希作为键）。

通过将最近访问（因此更新）的节点旋转到根节点，您应该最终在叶子或右子树中获得最近访问最少（因此更新）的数据。

弄清楚细节（并实现它们）留给读者作为练习......

注意事项：

  • 最坏情况的高度 - 因此复杂性 - 是线性的。这不应该发生在一个像样的哈希上
  • 任何只读操作（即不更新时间戳的查找）都会破坏展开树布局和时间戳之间的关系

一个更简单的方法是存储一个包含(hash, timestamp, prev, next)在常规字典中的对象，使用prev并next保持一个最新的双向链表。然后你需要的只是字典head和tail引用。

插入和更新仍然是常数时间（哈希查找 + 链表拼接），从列表尾部向后走，收集最旧的哈希是线性的。

于 2013-10-09T16:43:30.187 回答
2

除非我误读了您的问题，dict否则除了清除之外，普通的旧款应该是所有事情的理想选择。假设您试图避免在清除过程中检查整个字典，我建议保留第二个数据结构来保存(timestamp, hash)对。

这种补充数据结构可以是普通的旧数据结构，也可以是list（deque来自collections模块）。可能该bisect模块可以方便地将时间戳比较的数量保持在最低限度（而不是在达到截止值之前比较所有时间戳），但是因为您仍然必须按顺序迭代需要的项目要清除，消除最快的确切细节需要一些测试。

编辑：

对于 Python 2.7 或 3.1+，您还可以考虑使用OrderedDict（来自collections模块）。这基本上是dict在类中内置了一个补充的保持顺序的数据结构，因此您不必自己实现它。唯一的问题是它保留的唯一顺序是插入顺序，因此为了您的目的，您需要将其删除（使用del），而不是仅仅将现有条目重新分配给新的时间戳，然后使用新的时间戳。尽管如此，它仍然保留了 O(1) 查找并使您不必自己维护对列表(timestamp, hash)；当需要清除时，您可以直接遍历OrderedDict，删除条目，直到您到达一个时间戳晚于您的截止日期的条目。

于 2013-10-09T17:17:16.580 回答
1

如果您可以解决偶尔的误报，我认为布隆过滤器可能会很好地满足您的需求（它非常非常快）

http://en.wikipedia.org/wiki/Bloom_filter

和一个 python 实现：https ://github.com/axiak/pybloomfiltermmap

编辑：再次阅读您的帖子，我认为这会起作用，但不是存储散列，而是让布隆过滤器为您创建散列。即，我认为您只想将bloomfilter 用作一组时间戳。我假设您的时间戳基本上可能只是一个集合，因为您正在对它们进行哈希处理。

于 2013-10-09T15:48:51.203 回答
0

检查/更新/设置操作的简单哈希表或字典将是 O(1)。您可以同时将数据存储在一个简单的按时间排序的列表中，用于清除操作。保留一个头尾指针，这样插入也是 O(1) 并且移除就像推进头直到它到达目标时间并从散列中移除你找到的所有条目一样简单。

开销是每个存储的数据项有一个额外的指针，并且代码非常简单：

insert(key,time,data):
  existing = MyDictionary.find(key)
  if existing:  
      existing.mark()
  node = MyNodeType(data,time)  #simple container holding args + 'next' pointer
  node.next = NULL
  MyDictionary.insert(key,node)
  Tail.next = node
  if Head is NULL:  Head = node

clean(olderThan):
  while Head.time < olderThan:
    n = Head.next 
    if not Head.isMarked():  
        MyDictionary.remove(Head.key)
    #else it was already overwritten
    if Head == Tail: Tail = n
    Head = n
于 2013-10-09T16:21:33.687 回答