Алгоритм Python: как эффективно найти, если два целых набора пересекаются?

Question

Учитывая набор [2004, 2008], какой самый быстрый способ найти, если этот набор пересекается с другими наборами?

На самом деле я имею дело с базой данных, таблица имеет 2 столбца, одиннижняя граница, другая верхняя граница.Задача состоит в том, чтобы найти все пересекающиеся строки с заданным кортежем 2 (например, [2004,2008]).

Я использую mongodb, это поддерживается по своей природе (я имею в виду ключевые слова для этого).У меня большая база пользователей, поэтому я хочу, чтобы эта задача была выполнена как можно быстрее.

РЕДАКТИРОВАТЬ: Для большей ясности таблица базы данных содержит следующие строки:

20 30
10 50
60 90
...

Учитываявведите (25 40) диапазон, я хочу вернуть строки, представляющие диапазон, имеющие пересечение с заданным диапазоном.

, поэтому возвращаемое значение равно: (20 30),(10 50)

Answer 1

Я вообще не знаю MongoDB, но вы в основном ищете

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

Answer 2

Попробуйте, предполагая, что low и high являются вашими связанными полями:

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

Замените $lte и $gte, если вы хотите, чтобы ваш запрос был включающим, а не эксклюзивным.

Answer 3

MongoDB не поддерживает пересечение. Выполните пересечение на уровне Python, используя API перекрестков () множеств.

Answer 4

Вы можете использовать запрос mongodb с выражением Javascript (при условии, что lowerbounds и upperbounds являются пределами пересекаемого множества):

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

Это должно обрабатывать все случаи, включая случаи, когда [this.lower, this.upper] является надмножеством или правильным подмножеством [lowerbounad, upperbounds].

Answer 5

Поскольку вы имеете дело с нижними и верхними границами, вы можете просто проверить границы.

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

Я не знаю MongoDB, но если бы вы могли реализовать эту логику в базе данных, я могу 'не поможет, но думаю, что это будет быстрее.