1

假设我有一堆带有日期的对象，我经常想找到两个任意日期之间的所有对象。什么样的数据结构对此有好处？

4

5 回答 5

4

假设您说排序时按日期表示，则数组会执行此操作。

执行二进制搜索以查找 >= 开始日期的索引。然后，您可以进行另一次搜索以找到 <= 结束日期的索引，从而为您留下偏移量和项目计数，或者如果您要处理它们，只需遍历列表直到超过结束日期。

于 2009-04-02T22:49:13.663 回答
4

二叉搜索树听起来像您正在寻找的东西。您可以使用它来查找 O(log(N) + K) 中的所有对象，其中 N 是对象的总数，K 是实际在该范围内的对象的数量。（只要它是平衡的）。插入/移除是 O(log(N))。

大多数语言都有这个的内置实现。

您可以找到范围的下限（以 log(n) 为单位），然后从那里迭代直到达到上限。

于 2009-04-02T23:20:57.800 回答
0

如果没有更多细节，很难给出一个好的答案。

你需要什么样的性能？

如果线性很好，那么我将只使用一个日期列表并遍历该列表，收集该范围内的所有日期。正如安德鲁格兰特建议的那样。

列表中有重复项吗？

如果你需要在你的集合中有重复的日期，那么大多数二叉树的实现可能会被淘汰。Java 的 TreeSet 之类的东西是集合实现，不允许重复元素。

访问特点是什么？大量查找而几乎没有更新，反之亦然，甚至相当？

大多数数据结构在查找和更新之间进行权衡。如果您正在进行大量更新，那么一些针对查找优化的数据结构将不会那么好。

那么数据结构的访问特性是什么，需要什么样的性能，它必须支持哪些结构特性（例如必须允许重复元素）？

于 2009-04-02T23:33:53.447 回答
0

如果您需要进行随机访问修改：一棵树，如 v3 的答案。通过查找找到范围的底部，然后向上计数。插入或删除一个节点是 O(log N)。stbuton 提出了一个很好的观点，如果你想允许重复（这对于带日期戳的事件似乎是合理的），那么你不想要一个基于树的集合。

如果您不需要进行随机访问修改：排序数组（或向量或其他）。通过二进制印章找到范围开始的位置，然后向上计数。插入或删除在中间是O(N)。重复很容易。

在这两种情况下，查找的算法性能相同，O(M + log N)，其中 M 是范围的大小。但是数组每个条目使用更少的内存，并且可能更快地计算范围，因为在二进制切碎之后它只是向前顺序内存访问而不是跟随指针。

在这两种情况下，您都可以安排在最后插入（摊销）O（1）。对于树，在头部保留一个结束元素的记录，你会得到一个 O(1) 的界限。对于数组，以指数方式增长它，你得到摊销 O(1)。如果您所做的更改总是或几乎总是“使用当前时间添加新事件”，这将很有用，因为时间（您希望）是一个不减少的数量。如果您使用的是系统时间，那么您当然必须检查一下，以免时钟向后重置时发生意外。

替代答案：一个SQL表，让数据库优化它想要的方式。Google 的 BigTable 结构专门设计用于快速查询，确保任何查询的结果始终是来自预先准备好的索引的连续序列:-)

于 2009-04-02T23:48:30.137 回答
-1

您需要一种结构，使您的对象按日期排序，无论何时插入或删除一个新对象，并且在给定日期之后或之前找到所有对象段的边界很容易。

堆似乎是完美的候选者。在实际应用中，堆只是简单地用一个数组来表示，所有的对象都是按顺序存储的。将排序后的数组视为堆只是一种在正确的位置和 O(log(n)) 中插入和删除新对象的方法。

当你必须找到日期A（排除）和B（包含）之间的所有对象时，找到A的位置（或插入位置，即较早元素的位置晚于A），以及B的位置（或 B 的插入位置），并返回这些位置之间的所有对象（这只是数组/堆中这些位置之间的部分）

于 2009-04-02T22:54:27.130 回答