while len float python range

len - while python



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

¿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?


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.


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 .


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]


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


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


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.


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