Каков наилучший способ в Python определить, какие значения в двух диапазонах перекрываются?
Например:
x = range(1,10)
y = range(8,20)
(The answer I am looking for would be the integers 8 and 9.)
Учитывая диапазон, х, что является лучшим способом для итерации через другой диапазон, y и вывода всех значений, которые разделяются обоими диапазонами? Заранее спасибо за помощь.
EDIT:
В качестве продолжения я понял, что мне также нужно знать, что x выполняет или не перекрывает y. Я ищу способ перебирать список диапазонов и делать ряд дополнительных вещей с диапазоном, который перекрывается. Есть ли простое утверждение True/False для выполнения этого?
Попробуйте установить пересечение:
>>> x = range(1,10)
>>> y = range(8,20)
>>> xs = set(x)
>>> xs.intersection(y)
set([8, 9])
Обратите внимание, что intersection принимает любой итеративный аргумент (y не требуется преобразовывать в набор для операции).
Существует оператор, эквивалентный методу intersection: &, но в этом случае требует, чтобы оба аргумента были наборами.
Если шаг всегда равен +1 (который является значением по умолчанию для диапазона), то следующее должно быть более эффективным, чем преобразование каждого списка в набор или итерацию по любому списку:
range(max(x[0], y[0]), min(x[-1], y[-1])+1)
Вы можете использовать set, но имейте в виду, что set(list) удаляет все повторяющиеся записи из list:
>>> x = range(1,10)
>>> y = range(8,20)
>>> list(set(x) & set(y))
[8, 9]
Один из вариантов - просто использовать понимание списка, например:
x = range(1,10)
y = range(8,20)
z = [i for i in x if i in y]
print z
Для "если 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
Сравнение скоростей:
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
Если вы хотите найти перекрытие диапазонов с помощью произвольных шагов, вы можете использовать мой пакет 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().
Предполагая, что вы работаете исключительно с диапазонами, с шагом 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 или около того элементов, но мой компьютер замер на некоторое время. Я сомневаюсь, что вы долго будете работать со списками.