8

我有大量（~10 9）事件集，以开始和结束时间为特征。给定一个时间，我想知道当时有多少这些事件正在进行。

在这种情况下，什么样的数据结构会有所帮助？我需要快速的操作是：

  1. 插入新事件，例如{start: 100000 milliseconds, end: 100010 milliseconds}.
  2. 查询给定时间的并发事件数。

更新：有人在这上面放了一个计算几何标志，所以我想我应该用计算几何来改写它。我有一组一维区间，我想计算这些区间中有多少与给定点相交。新间隔的插入必须很快。

4

4 回答 4

8

您正在寻找区间树。

  • 构造：O(n log n)，其中n是区间数
  • Query: O(m+log n)，其中m为查询结果n数，为区间数
  • 空间：O(n)
于 2012-05-16T01:05:05.810 回答
3

只是为了添加其他答案，根据时间长度和所需的粒度，您可以简单地拥有一个计数器数组。例如，如果时间长度为 24 小时，所需的粒度为 1 毫秒，则数组中将有 86,400,000 个单元格。每个单元有一个 4 字节 int（足以容纳 10^9），这将小于 700 MB 的 RAM，而基于树的解决方案至少需要 (8+8+4+4)*10^ 9 = 24 GB RAM 用于两个指针加上每个树节点两个整数（由于 32 位可寻址内存不足，每个指针需要 64 位）。您可以使用交换，但这会大大减慢一些查询。

如果您只关心最近 24 小时的数据，也可以使用此解决方案，例如，将数组用作循环缓冲区。除了时间和粒度的限制之外，另一个缺点是间隔的插入时间与间隔的长度成正比，所以如果间隔长度是无限的，你可能会遇到麻烦。另一方面，查询是单个数组查找。

于 2012-05-16T03:43:22.987 回答
2

（由 tskuzzy 和 Snowball 扩展答案）

平衡的二叉搜索树是有意义的，只是内存需求对于您的数据集来说会过多。除非您可以使用库，否则B -tree的内存效率会更高，尽管会更复杂。

保留两棵树，一棵开始时间，一棵结束时间。要插入事件，请将开始时间添加到开始时间树，将结束时间添加到结束时间树。要查询时间 T 的活动事件数，请搜索开始时间树以找出有多少开始时间小于 T，并搜索结束时间树以找出有多少结束时间小于 T。结束时间与开始时间的数量，这就是活动事件的数量。

插入和查询都应该花费 O(log N) 时间。

几点评论：

  • 您表达问题的方式，您只关心活动事件的数量，而不关心哪些活动是活动的。这意味着您无需跟踪哪个开始时间与哪个结束时间！这也使得避免先前答案引用的查询中的“+M”术语变得更容易。

  • 请注意查询的确切语义。特别是，如果一个事件在时间 T 开始，那么它在时间 T 是否算作活动的？如果它在时间 T 结束？这些问题的答案会影响您在某些地方是否使用 < 或 <=。

  • 不要使用“集合”数据结构，因为您几乎肯定希望允许和计算重复项。也就是说，不止一个事件可能同时开始和/或结束。一组通常会忽略重复项。相反，您正在寻找的是“多集”（有时称为“包”）。

  • 许多二叉搜索树不支持开箱即用的“元素数 < T”查询。但是很容易通过在每个节点上存储一个大小来添加这个功能。

于 2012-05-16T16:37:00.373 回答
0

假设我们有一个带有N个元素的有序集合（例如，平衡二叉搜索树或跳过列表）数据结构。此外，假设排序集具有O(log N)搜索时间、O(log N)插入时间和O(N)空间使用（这些是合理的假设，例如，参见红黑树）。

一种可能性是有两个排序集，bystart和byend，分别按事件的开始时间和结束时间排序。

要查找在 time 正在进行的事件数t，请询问byend结束时间大于 的第一个时间间隔t：O(log N)搜索操作。调用这个间隔的开始时间left。现在，询问bystart开始时间大于或等于left且小于的间隔数t。这是O(log N + M)，其中M是此类间隔的数量。因此，搜索的总时间是O(log N + M)。

对于排序集，插入是O(log N)，我们必须对每个排序集执行一次。这使得插入操作的总时间为O(log N)。

从头开始构建这个结构只包含N次插入操作，因此构建的总时间是O(N log N)。

每个排序集的空间使用量为 O(N )，因此总空间使用量为O(N)。

概括：

  • 插入：O(log N)，其中N是间隔数
  • 构造：O(N log N)
  • 查询：O(log N + M)，其中M是结果数
  • 空间：O(N)
于 2012-05-16T03:17:34.663 回答