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

¿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 statement simple de Verdadero / Falso para lograr esto?

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 .

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) 

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] 

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 

Para “si x hace o no se superpone a”:

 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] 

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.

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

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

Esta es la respuesta para el rango simple con el paso = 1 caso (99% del tiempo), que puede ser 2500 veces más rápido como se muestra en el punto de referencia cuando se comparan los rangos largos usando conjuntos (cuando solo está interesado en saber si hay superposición) :

 x = range(1,10) y = range(8,20) def range_overlapping(x, y): if x.start == x.stop or y.start == y.stop: return False return ((x.start < y.stop and x.stop > y.start) or (x.stop > y.start and y.stop > x.start)) >>> range_overlapping(x, y) True 

Para encontrar los valores superpuestos:

 def overlap(x, y): if not range_overlapping(x, y): return set() return set(range(max(x.start, y.start), min(x.stop, y.stop)+1)) 

Ayuda visual:

 | | | | | | | | 

Punto de referencia:

 x = range(1,10) y = range(8,20) In [151]: %timeit set(x).intersection(y) 2.74 µs ± 11.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) In [152]: %timeit range_overlapping(x, y) 1.4 µs ± 2.91 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 

Conclusión : incluso para rangos pequeños, es el doble de rápido.

 x = range(1,10000) y = range(50000, 500000) In [155]: %timeit set(x).intersection(y) 43.1 ms ± 158 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [156]: %timeit range_overlapping(x, y) 1.75 µs ± 88.3 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each) 

Conclusión : desea utilizar la función range_overlapping en este caso, ya que es 2500 veces más rápida (mi registro personal en aceleración)

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. Probé con 10 ^ 8 o más elementos, pero mi computadora se congeló por un tiempo. Dudo que estuvieras trabajando con listas tanto tiempo.

Las respuestas anteriores parecen sobre todo demasiado complejas. Este forro funciona perfectamente en Python3, toma rangos como entradas y salidas. También maneja rangos ilegales. Para obtener los valores solo iterar sobre el resultado si no es Ninguno.

 # return overlap range for two range objects or None if no ovelap # does not handle step!=1 def range_intersect(r1, r2): return range(max(r1.start,r2.start), min(r1.stop,r2.stop)) or None