在给定的范围内查找成对的值

Question

我有一个由N对(v1, v2)组成的数组，其中v1 <= v2。这些代表随时间开始于v1并结束于v2的事件。如果它们相等，则该事件是瞬时的。该数组按照起始时间v1进行排序。

给定一个范围(L, R)，我想找到任何一对满足L <= v1 <= R或L <= v2 <= R的值。这里的思路是获取在给定范围内开始、发生或结束的事件。

我的主要问题是效率。数组可能包含数十万个事件。所以只通过遍历所有对的线性搜索不是一个选择。

我了解过kd-tree，但它的问题是它排除了范围的边界，并且只返回L <= v1 <= R AND L <= v2 <= R。也就是说，只返回在范围内实际发生（开始和结束）的事件，而我需要开始或结束（或两者都有）。

我还考虑过保持2个查找表（我使用double作为时间）。

std::map<double, Event*> startPoints;
std::map<double, Event*> endPoints;

并在它们两者中使用std::find算法，然后合并结果。

只是想寻求建议，无论这是否是一个好的解决方案，或者是否有更聪明的方法。

编辑:

重新考虑，这更加复杂。以下是预期结果的示例：

• L < R：范围足够大

|---Ev1---|     |---Ev3---|     |---Ev5---|
        |---Ev2---|     |---Ev4---|
             |               |
             L               R

在这里，我想获取发生在范围内的Ev2（结束于范围内），正在范围内发生的Ev3以及开始于范围内的Ev4。

• L < R：范围太小了，无法完整记录事件

|---Ev1---|     |---Ev3---|     |---Ev5---|
        |---Ev2---|     |---Ev4---|
                    |    |
                    L    R

我希望得到Ev3在其当前范围内的情况，以及Ev4在范围内启动时的情况。

• L == R：如果我想知道某个时间点会发生什么

|---Ev1---|     |---Ev3---|     |---Ev5---|
        |---Ev2---|     |---Ev4---|
             |
             LR

我只想选择Ev2，因为它是目前唯一在运行的。

- Nico J.

---

看一下 Boost.ICL。 - Igor R.

你可以仍然看一下Boost，了解他们如何实现你的目标。然后使用这些想法来构思/研究你自己的实现。 - PaulMcKenzie

你写L <= v1 <= R or L <= v2 <= R，然后是开始、发生或结束，但这不一样。对于发生，你需要v1 <= R and L <= v2。 - Yola

@Yola：已经根据这个想法编辑了第一篇帖子。 - Nico J.

你正在寻找一个区间树吗：https://en.wikipedia.org/wiki/Interval_tree？ - Lawrence

Answer 1

由于需要处理三种情况 - 在给定范围内启动、正在执行或结束，因此我们可以将其分为三个部分。

1. 启动: v1 在 [L,R] 范围内。
2. 结束: v2 在 [L,R] 范围内。

第三种情况可以表示为 v1 <= R and L <= v2，但前两种情况部分覆盖了这种情况，因此我们将使用不同的表达方式来避免冲突:

3. 正在执行: v1 < L and R < v2

如果我们可以按照 v1 对事件数组进行排序，那么就可以在对数时间和报告事件数量之和的时间内轻松处理第一种情况。同样的技巧也适用于第二种情况。

第三种情况要棘手一些。让我们画一下:

粉色区域表示所有区间 L <= R。红点是一个区间，青色区域表示我们想要捕获的所有可能事件。为了进行这样的捕获，可以使用 k2-tree。

- Yola

---

非常感谢您，我认为这个链接 https://en.wikipedia.org/wiki/Interval_tree#Centered_interval_tree （感谢评论中的劳伦斯提供了该链接）与此相似，我将参考两者来实现它。 - Nico J.

Answer 2

使用索引方法是可以的，例如Boost.ICL解决方案。

话虽如此，您也可以轻松地使用std::vector进行操作，即使是未排序的 - 我认为只要您在某个100,000甚至1,000,000的范围内，就应该没问题（只要在向量中存储实际值而不是指针，因为这可能会很慢） - 精确数字当然取决于您的阈值。

struct MyEvent {
  double v1;//you use double for time
  double v2;
};


std::vector<MyEvent> events;

这是一个使用1,000,000个元素的示例：

http://coliru.stacked-crooked.com/a/9a6d90348f6915e1

搜索运行时间为42毫秒，其中包括一次比较和可选复制，尽管您的情况可能有所不同，但是可以进行比较。

进一步地，您可以通过某种方式并行化搜索，例如使用std::for_each，以获得更多的功率。

- darune

---

在某些情况下，“42毫秒”是很多。 - fjardon

@fjardon 的确可能是这样 - 这就是为什么我写了它取决于前提 以及 是否进一步进行。话虽如此，生成索引等也需要成本，这就是为什么数据库存在的原因等。 - darune

Answer 3

std::map -->查找元素的复杂度为O(logn)。 如果您的键是唯一的且没有内存问题，可以使用std::unordered_map，其复杂度为摊销（O1）。 此外，您不需要创建2个映射。 std::unordered_map<double, std::pair<Event*, Event*>> StartEndPoints;。 如果您的键不唯一，则可以使用std::unordered_multimap，但如果您的键将被重复很多次，则查找复杂度可能会变为(On)。 我建议不要将键类型传递为double。

std::hash<double> hashing.
auto temp = hashing(key). // decltype of temp will be size_t
std::unordered_map<std::size_t, std::pair<Event*, Event*>> StartEndPoints;

- Narek Aydinyan

---

当你想要查找一系列元素时，std::unordered_map 并不是非常适合。 - Max Langhof

从问题中我理解到，需要找到起始点和结束点，而不是这些点之间的所有元素。如果需要在此范围内获取所有元素，最好使用你提出的std::vector。 - Narek Aydinyan