java - 基于时间的分组

Question

我有以下问题:

我有一个大小为 S 的对象列表(包含一个日期属性)(通常 S 会达到大约 200k，但在某些情况下它可能会达到一百万)。

我需要根据以下条件过滤列表:

• 仅当从其日期属性开始可以在列表中找到时间间隔 T 内的 X 个事件时，一项才必须保留在最终列表中。

考虑到庞大的 list 以及低效的解决方案可能会引起哪些性能问题，您能否告诉我解决此问题的最佳方法/算法是什么。

谢谢。

PS:JAVA实现

Answer 1

我在这里可能完全错了，但我认为人们忽略了这样一个事实，即您的标题使用了“分组”一词而不是“过滤”以及“从其日期属性开始”的部分.所以这是我对你的问题的看法:

• 您有一个源列表 L，其中包含具有时间戳属性 t 的类型 I 的项。
• 您希望构建一个目标列表 T，其中包含 L 中的项目(可能顺序相同)。
• 你有一些半径 r，用时间单位(毫秒、秒、分钟...)表示。
• 您有一些正整数阈值 l(这里的字母用完了)。
• 当且仅当 L 中有 l 个或更多项目的时间戳落在区间 [ i.t - r, i.t + r].

假设列表未排序，遍历列表并计算每个条目在间隔内的项目数将非常昂贵。这将导致 O(n²) 性能。

如果 T 中的项目顺序可能与 L 中的项目顺序不同，那么以下是一个有效的解决方案:

1. 对 L 中的项目进行排序。如果项目类型 I 实现了 Comparable 接口(interface)并且按时间戳排序，那么它会很简单。否则，您可能需要实现一个根据时间戳属性排序的 Comparator。排序不能比 O(n*log n) 更好，所以这是目前的底线。

2. 制作三个索引:s(开始)、e(结束)、c(当前项)。

3. 迭代索引为 c 的排序列表。对于每个条目，执行以下操作:

   3.1 从索引s开始，统计有多少项不再落在“半径”内。即，有多少项目的时间戳低于索引 c 处项目的时间戳减去时间半径。将该值添加到索引 s。这使得它指向落在半径内的“最早”项目。

   3.2 从索引e开始，检查排序列表中的项目，看它们是否落在半径内。让 e 指向最后一项。

   3.3取值(e-s)。如果它低于阈值 l，则意味着索引 c 处的项目通过了过滤器。否则，它不会。

   3.4 增量 c。如果 c 现在 > e，也增加 e。

就是这样。第 3 步检查排序列表中的每个项目一次，因此这是 O(n) 性能。最坏的情况取决于时间戳和半径。您不是每次都从列表的开头开始搜索下限，而是从尾随索引 s 开始搜索。您不是每次都从 c 开始搜索上限，而是从前导索引 e 开始。所以我相信最坏情况下的性能仍然是 O(n) 因为 s 和 e 也只能遍历列表一次。假设您有 100 个条目，并且从条目 3 开始，您发现所有剩余条目都在半径范围内(即 e 变为 99)，您将永远不必进一步检查。

通过一个 O(n*log n) 步和一个 O(n) 步，摊销性能变为 O(n*log n)。似乎完全可以接受。

请注意，如果过滤列表必须保持原始项目顺序，您将需要额外的步骤。在那种情况下，某种索引列表可能会有用。

编辑:我刚刚意识到你的字面意思可能是“从”开始，所以如果是这样的话，只需忽略尾随索引 s 并只使用前导索引 e。除了采用 (e - c) 而不是 (e - s) 之外，算法在其他方面保持不变。我在预编辑版本中也有一些“框架列表”，这显然是无稽之谈，因为索引足以计算所需的数量。