Python: how to efficiently find if two integer sets intersect?

Question

Given a set [2004, 2008], what is the fastest way to find if this set intersects with other sets?

Actually, I am dealing with a database, the table has 2 columns, one has a lower bound and the other has an upper bound. The task is to find all intersecting rows with the specified 2 tuples (for example, [2004,2008]).

I use mongodb, this is internally supported (I mean there are keywords for this). I have a large user base, so I want this task to be completed as quickly as possible.

EDIT: for clearer statistics, the database table contains the following rows:

20 30
10 50
60 90
...

Given the input range (25 40), I want to return the rows that represent the range intersect with the given range.

so return: (20 30),(10 50)

Answer 1

I don’t know MongoDB at all, but you are mostly looking

SELECT * from the_table where not (lower_bound > 2008 or upper_bound < 2004).

Answer 2

Try it, believing lowand highyour related field:

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

Replace $lteand $gteif you want your request to be included, not exclusive.

Answer 3

MongoDB . Python API- intersection().

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, , , .

Answer 5

You can use the mongodb request with a Javascript expression (assuming that lowerboundsboth upperboundsare set intersection limits):

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

This should handle all cases, including when [this.lower, this.upper] is a superset or corresponding subset of [lowerbounad, upperbounds].