Python算法：如何高效地找到两个整数集合是否相交？

Question

给定一个集合[2004, 2008]，如何快速找到这个集合与其他集合是否有交集？

实际上我正在处理一个数据库问题，该表有两列，一列是下限，另一列是上限。任务是找到所有与给定的2元组（如[2004,2008]）相交的行。

我正在使用mongodb，它本质上支持这种操作（我的意思是有关键字来执行此操作）吗？我有大量的用户，所以我希望尽快完成此任务。

编辑：为了更清晰，一个数据库表包含以下行：

20 30
10 50
60 90
...

给定输入的范围为 (25 40)，我希望返回与给定范围有交集的行所代表的范围。

因此返回结果为：(20 30),(10 50)。

- Bin Chen

---

从你的陈述方式来看，不清楚你是否有代表范围的值对，并且想知道任何一对是否相交，还是有两个大的值集要相交。你了解整数的大小吗？ - Ira Baxter

我完全不了解MongoDB，但你基本上是在寻找SELECT * from the_table where not (lower_bound > 2008 or upper_bound < 2004)。如果它不能做到这一点，那么它就不是一个数据库 ;-p - Steve Jessop

@Steve 是的，实际上这就是答案！！请将您的评论写成一个答案，然后我可以接受它，谢谢！ - Bin Chen

Answer 1

我完全不了解 MongoDB，但你基本上是在寻找 SELECT * from the_table where not (lower_bound > 2008 or upper_bound < 2004) 这个查询语句。

- Steve Jessop

---

似乎 SELECT * from the_table where (lower_bound < 2008 and upper_bound > 2004) 更简单且等效。 - martineau

@martineau：应该是<=才能等价于我的，但是没错。这只是我不想的方式。 - Steve Jessop

我甚至不理解为什么有人会给一个 SQL 回答 NOSQL 数据库问题的积分。虽然它提供了算法，但是 mstearn 的答案在这里是正确的。 - Gnu Engineer

@Gnu：我也是，如果你看评论，你会看到OP要求我将其发布为答案，我想那时候这是最好的选择。我猜他可以处理语法，他的问题是无法简洁地描述范围重叠的属性。通过martineau的评论，很容易看出这个答案和mstearn的答案之间的等价性。 - Steve Jessop

Answer 2

假设 low 和 high 是您的绑定字段，请尝试以下操作：

db.ranges.find({'low': {'$lt': self.high}, 'high': {'$gt': self.low}})

如果您希望查询结果包含指定的值，而不是排除指定的值，请使用$lte和$gte代替。

- mstearn

Answer 3

MongoDB不支持交集。可以在Python层面上使用集合的intersection() API执行交集。

- user2665694

---

不使用Python集合(set)，而是使用两个整数表示上下界。 - aaronasterling

Answer 4

由于你正在处理下限和上限，所以可以直接检查边界。

def intersects(this, others):
    upper, lower = this
    return [[u, l] for u, l in others 
            if (l < upper < u) or (l < lower < u)]

我不熟悉MongoDB，但如果您能在数据库中实现该逻辑，我不禁想到它会更快。

- aaronasterling

---

值得一提的是，元组在这里比列表更快，用于存储上下限范围，因为它们的构建速度可以显著提高。 - aaronasterling

这里似乎有一些bug，这里缺少一个case，如果[lower, upper]是[u, l]的超集 :-) - Bin Chen

@Bin chen - 绝对正确。我匆忙发布的，现在遭报应了。看起来MongoDB可以本地化处理这个问题，所以这并不是一个很好的答案。 - aaronasterling

Answer 5

你可以使用带有Javascript表达式的mongodb查询（假设lowerbounds和upperbounds是被相交集合的限制）：

f = function() { return this.lower <= upperbounds && this.upper >= lowerbounds; }
db.ranges.find(f);

这应该处理所有情况，包括当 [this.lower, this.upper] 是 [lowerbounad, upperbounds] 的超集或真子集时。

- martineau

---

这样的查询应该始终使用本地查询语法而不是JavaScript。JavaScript查询执行速度较慢，无法使用索引。请参见我的答案，其中包含使用本地语法的示例。 - mstearn