len - while python

¿Cómo encontrar rango de superposición en python?

Question

¿Cuál es la mejor manera en Python para determinar qué valores de dos rangos se superponen?

Por ejemplo:

x = range(1,10)
y = range(8,20)
(The answer I am looking for would be the integers 8 and 9.)

Dado un rango, x, ¿cuál es la mejor manera de iterar a través de otro rango, y y genera todos los valores compartidos por ambos rangos? Gracias de antemano por la ayuda.

EDITAR:

Como seguimiento, me di cuenta de que también necesito saber si x se superpone o no a y. Estoy buscando una manera de iterar a través de una lista de rangos y hacer una serie de cosas adicionales con un rango que se superponen. ¿Hay una declaración simple de Verdadero / Falso para lograr esto?

Answer 1

Para "si x hace o no se superpone 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

resultado

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

Editar 1

Comparación de velocidades:

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

resultado

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

El ratio de estos tiempos de ejecución es de 2.5.

Answer 2

Probar con set intersección:

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

Tenga en cuenta que la intersection acepta cualquier iterable como un argumento ( y no se requiere que se convierta en un conjunto para la operación). Hay un operador equivalente al método de intersection : & pero, en este caso, requiere que ambos argumentos sean conjuntos .

Answer 3

Puede usar set s para eso, pero tenga en cuenta que set(list) elimina todas las entradas duplicadas de la list :

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

Answer 4

Si desea encontrar la superposición de rangos con pasos arbitrarios, puede usar mi paquete https://github.com/avnr/rangeplus que proporciona una clase Range () compatible con el rango de Python (), más algunos detalles, incluidas las intersecciones:

>>> 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)

El rango () también puede estar sin consolidar (cuando la parada es Ninguna, el rango pasa a +/- infinito):

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

La intersección se calcula, no se itera, lo que hace que la eficiencia de la implementación sea independiente de la longitud del Rango ().

Answer 5

Si el paso siempre es +1 (que es el valor predeterminado para el rango), lo siguiente debería ser más eficiente que convertir cada lista en un conjunto o iterar sobre cualquiera de las listas:

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

Answer 6

Si está buscando la superposición entre dos intervalos limitados de valor real, entonces esto es bastante bueno:

def overlap(start1, end1, start2, end2):
"""how much does the range (start1, end1) overlap with (start2, end2)"""
return max(max((end2-start1), 0) - max((end2-end1), 0) - max((start2-start1), 0), 0)

No pude encontrar esto en línea en ningún lugar, así que se me ocurrió esto y estoy publicando aquí.

Answer 7

Suponiendo que está trabajando exclusivamente con rangos, con un paso de 1 , puede hacerlo rápidamente con matemáticas.

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

En un par de rangos, cada uno con más de 10 ^ 7 elementos, esto tomó menos de un segundo, independientemente de cuántos elementos se superponen. Lo intenté con 10 ^ 8 o más elementos, pero mi computadora se congeló por un tiempo. Dudo que estuvieras trabajando con listas tanto tiempo.

Answer 8

Una opción es usar la comprensión de lista como:

x = range(1,10)
y = range(8,20)
z = [i for i in x if i in y]
print z