搜索时态数据

Question

我开发了一个应用程序(在C#中)，其中的对象在一段时间内是活动的，它们具有DateTime类型的from和to属性。现在我想要加速我的搜索例程，比如:在这个时间段/这个时候是否还有其他活动的对象。

是否有任何现有的时态索引可以使用，或者我是否可以使用四叉树/其他树结构以有效的方式进行搜索。

Answer 1

您还应该查看一下interval tree

在计算机科学中，区间树是一种用于保存区间的有序树数据结构。具体地说，它允许人们有效地找到与任何给定区间或点重叠的所有区间。

这让我想起了这个SO question。

Answer 2

为什么不直接在列表中对数据进行排序，然后使用类似二进制搜索的算法来限制您考虑的对象的数量。

Answer 3

这是一个有趣的排序问题，因为您需要同时考虑每个元素的开始日期和结束日期。如果您使用简单的排序算法，那么您可以按开始日期或结束日期进行排序，但同时按开始日期和结束日期进行排序并不是非常有效，因为开始日期较早的元素可能具有非常晚的结束日期，或者开始日期较晚的元素可能具有较早的结束日期，这意味着您不能根据“这些元素中是否有任何元素现在处于活动状态？”这一条件对此列表进行预排序。

如果您正在寻找一种超高效的机制来完成这项工作，我可能没有答案，但是如果您只是在寻找一些易于处理现有C#数据结构的方法，我会考虑创建两个排序列表，一个按开始日期排序，另一个按结束日期排序。在start -date排序列表中搜索当前开始之前的元素，在end -date排序列表中搜索当前结束之后的元素。将这些结果相交，得到你的最终答案。

正如我所提到的，我确信有一种更有效的机制可以做到这一点，但如果我想保持简单，只使用我现有的资源，我会考虑这样做。