2

我有以下数据结构，它描述了一个对象及其有效的时间段。假设下面的数字是 unix 时间戳。

{
  "id": 1234,
  "valid_from": 2000
  "valid_to": 4000
},
{
 "id": 1235,
 "valid_from": 1000,
 "valid_to": 2200,
}
...

我希望能够快速将这些项目存储在 JavaScript 中，然后查询在特定时间有效的项目。

例如，如果我要查询在 2100 有效的对象，我会得到 [1234, 1235]。如果我要查询在 3999 有效的对象，我会得到 [1234]，而在 4999 什么也没有。

我将在结构中拥有大约 50-100k 个项目，我想要快速的查找速度，但插入和删除可能会更慢。

项目将具有重复的 valid_from 和 valid_to 值，因此它需要支持重复项。项目将重叠。

我将需要不断地将数据插入到结构中（可能是批量加载以进行初始加载，然后随着数据的变化进行一次更新）。我还将定期修改记录，因此很可能是删除和插入。

我不确定以高效方式解决此问题的最佳方法是什么？

算法不是我的强项，但如果我知道正确的方法，我可以自己研究算法。

我的想法：

我最初在考虑使用修改后的二叉搜索树来支持重复键和最接近查找，但这仅允许我查询 > valid_from 或 < valid_to 的对象。

这将涉及我将数组或树一分为二以查找所有项目> valid_from，然后手动检查每个项目的valid_to。

我想我可以有两棵搜索树，一棵用于 valid_to 和 valid_from，然后我可以检查结果重叠中的哪个 id 并返回那些 id？

这对我来说仍然有点hacky？有人可以推荐更好的方法还是这样做的。

4

1 回答 1

0

假设您有两个列表：启动/开始和到期/结束。两者都按时间排序。

给定特定时间，您可以通过二分搜索找到每个列表中第一项满足条件的位置。您还可以通过二进制搜索插入每个列表。

例如，如果有 1000 个项目并且开始位置是 342，那么项目 1-342 是可能的，如果结束位置是 901，那么终止列表中的项目 901-1000 是可能的。您现在需要将两个子列表相交。

从开始的 1-342 和结束的 901-1000 中获取项目 ID，并将它们放在单独的数组中（提前分配）。对数组进行排序。遍历数组。每当同一个 ID 连续出现两次时，它就是一个命中，一个有效的匹配。

于 2015-06-10T13:03:26.020 回答