Как найти перекрытие диапазона в python?

Ответ 1

Попробуйте установить пересечение:

>>> x = range(1,10)
>>> y = range(8,20)
>>> xs = set(x)
>>> xs.intersection(y)
set([8, 9])

Обратите внимание, что intersection принимает любой итеративный аргумент (y не требуется преобразовывать в набор для операции). Существует оператор, эквивалентный методу intersection: &, но в этом случае требует, чтобы оба аргумента были наборами.

Ответ 2

Если шаг всегда равен +1 (который является значением по умолчанию для диапазона), то следующее должно быть более эффективным, чем преобразование каждого списка в набор или итерацию по любому списку:

range(max(x[0], y[0]), min(x[-1], y[-1])+1)

Ответ 3

Вы можете использовать set, но имейте в виду, что set(list) удаляет все повторяющиеся записи из list:

>>> x = range(1,10)
>>> y = range(8,20)
>>> list(set(x) & set(y))
[8, 9]

Ответ 4

Один из вариантов - просто использовать понимание списка, например:

x = range(1,10) 
y = range(8,20) 

z = [i for i in x if i in y]
print z

Ответ 5

Для "если x накладывает или не перекрывает y":

for a,b,c,d in ((1,10,10,14),
                (1,10,9,14),
                (1,10,4,14),
                (1,10,4,10),
                (1,10,4,9),
                (1,10,4,7),
                (1,10,1,7),
                (1,10,-3,7),
                (1,10,-3,2),
                (1,10,-3,1),
                (1,10,-11,-5)):
    x = range(a,b)
    y = range(c,d)
    print 'x==',x
    print 'y==',y
    b = not ((x[-1]<y[0]) or (y[-1]<x[0]))
    print '    x %s y' % ("does not overlap","   OVERLAPS  ")[b]
    print

результат

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [10, 11, 12, 13]
    x does not overlap y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [9, 10, 11, 12, 13]
    x    OVERLAPS   y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
    x    OVERLAPS   y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [4, 5, 6, 7, 8, 9]
    x    OVERLAPS   y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [4, 5, 6, 7, 8]
    x    OVERLAPS   y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [4, 5, 6]
    x    OVERLAPS   y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [1, 2, 3, 4, 5, 6]
    x    OVERLAPS   y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [-3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
    x    OVERLAPS   y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [-3, -2, -1, 0, 1]
    x    OVERLAPS   y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [-3, -2, -1, 0]
    x does not overlap y

x== [1, 2, 3, 4, 5, 6, 7, 8, 9]
y== [-11, -10, -9, -8, -7, -6]
    x does not overlap y

Изменить 1

Сравнение скоростей:

from time import clock

x = range(-12,15)
y = range(-5,3)
te = clock()
for i in xrange(100000):
    w = set(x).intersection(y)
print '                     set(x).intersection(y)',clock()-te


te = clock()
for i in xrange(100000):
    w = range(max(x[0], y[0]), min(x[-1], y[-1])+1)
print 'range(max(x[0], y[0]), min(x[-1], y[-1])+1)',clock()-te

результат

                     set(x).intersection(y) 0.951059981087
range(max(x[0], y[0]), min(x[-1], y[-1])+1) 0.377761978129

Соотношение этих времен исполнения составляет 2,5

Ответ 6

Если вы хотите найти перекрытие диапазонов с помощью произвольных шагов, вы можете использовать мой пакет https://github.com/avnr/rangeplus, который обеспечивает класс Range(), совместимый с диапазоном Python(), плюс некоторые полезные свойства, включая пересечения:

>>> from rangeplus import Range
>>> Range(1, 100, 3) & Range(2, 100, 4)
Range(10, 100, 12)
>>> Range(200, -200, -7) & range(5, 80, 2)  # can intersect with Python range() too
Range(67, 4, -14)

Диапазон() также может быть несвязанным (когда stop - None, Range продолжает +/- бесконечность):

>>> Range(1, None, 3) & Range(3, None, 4)
Range(7, None, 12)
>>> Range(253, None, -3) & Range(208, 310, 5)
Range(253, 207, -15)

Пересечение вычисляется, а не повторяется, что делает эффективность реализации независимой от длины Range().

Ответ 7

Предполагая, что вы работаете исключительно с диапазонами, с шагом 1, вы можете сделать это быстро с помощью математики.

def range_intersect(range_x,range_y):
    if len(range_x) == 0 or len(range_y) == 0:
        return []
    # find the endpoints
    x = (range_x[0], range_x[-1]) # from the first element to the last, inclusive
    y = (range_y[0], range_y[-1])
    # ensure min is before max
    # this can be excluded if the ranges must always be increasing
    x = tuple(sorted(x))
    y = tuple(sorted(y))
    # the range of the intersection is guaranteed to be from the maximum of the min values to the minimum of the max values, inclusive
    z = (max(x[0],y[0]),min(x[1],y[1]))
    if z[0] < z[1]:
        return range(z[0], z[1] + 1) # to make this an inclusive range
    else:
        return [] # no intersection

В паре диапазонов, каждый из которых содержит более 10 ^ 7 элементов, это заняло не менее секунды, независимо от того, сколько элементов перекрыто. Я пробовал с 10 ^ 8 или около того элементов, но мой компьютер замер на некоторое время. Я сомневаюсь, что вы долго будете работать со списками.