Intervalo de intervalos de Python

Mi problema es el siguiente:

Tener archivo con lista de intervalos:

1 5 2 8 9 12 20 30 

Y una gama de

 0 200 

Me gustaría hacer una intersección tal que informe las posiciones [inicio final] entre mis intervalos dentro del rango dado.

Por ejemplo:

 8 9 12 20 30 200 

Además de cualquier idea sobre cómo morder esto, también sería bueno leer algunas reflexiones sobre la optimización, ya que, como siempre, los archivos de entrada serán enormes.

Esta solución funciona siempre que los intervalos estén ordenados por el punto de inicio y no requiera crear una lista tan grande como el rango total.

código

 with open("0.txt") as f: t=[x.rstrip("\n").split("\t") for x in f.readlines()] intervals=[(int(x[0]),int(x[1])) for x in t] def find_ints(intervals, mn, mx): next_start = mn for x in intervals: if next_start < x[0]: yield next_start,x[0] next_start = x[1] elif next_start < x[1]: next_start = x[1] if next_start < mx: yield next_start, mx print list(find_ints(intervals, 0, 200)) 

salida:

(en el caso del ejemplo que dio)

 [(0, 1), (8, 9), (12, 20), (30, 200)] 

Algoritmo en bruto:

  1. crear una matriz de valores booleanos, todo configurado como falso seen = [False]*200
  2. Iterar sobre el archivo de entrada, para cada línea start end conjunto start end seen[start] .. seen[end] como True
  3. Una vez hecho esto, entonces puede caminar trivialmente la matriz para encontrar los intervalos no utilizados.

En términos de optimizaciones, si la lista de rangos de entrada está ordenada por número de inicio, entonces puede rastrear el número más alto visto y usarlo para filtrar los rangos a medida que se procesan, por ejemplo, algo como

 for (start,end) in input: if end<=lowest_unseen: next if start 

que (ignorando el costo de la clasificación original) debería hacer todo el asunto O (n): se pasa por la matriz una vez para etiquetar lo visto / invisible y una vez para mostrar lo invisible.

Parece que me siento bien. Aquí está el código (no optimizado), asumiendo que su archivo de entrada se llama input

 seen = [False]*200 file = open('input','r') rows = file.readlines() for row in rows: (start,end) = row.split(' ') print "%s %s" % (start,end) for x in range( int(start)-1, int(end)-1 ): seen[x] = True print seen[0:10] in_unseen_block=False start=1 for x in range(1,200): val=seen[x-1] if val and not in_unseen_block: continue if not val and in_unseen_block: continue # Must be at a change point. if val: # we have reached the end of the block print "%s %s" % (start,x) in_unseen_block = False else: # start of new block start = x in_unseen_block = True # Handle end block if in_unseen_block: print "%s %s" % (start, 200) 

Dejo las optimizaciones como ejercicio para el lector.

Si toma una nota cada vez que uno de sus intervalos de entrada se abre o se cierra, puede hacer lo que desee al juntar las teclas de opens y closes , ordenar en un conjunto ordenado, y podrá pensar esencialmente, “bueno, digamos que cada par de números adyacentes forma un intervalo. Entonces puedo enfocar toda mi lógica en estos intervalos como partes discretas”.

 myRange = range(201) intervals = [(1,5), (2,8), (9,12), (20,30)] opens = {} closes = {} def open(index): if index not in opens: opens[index] = 0 opens[index] += 1 def close(index): if index not in closes: closes[index] = 0 closes[index] += 1 for start, end in intervals: if end > start: # Making sure to exclude empty intervals, which can be problematic later open(start) close(end) # Sort all the interval-endpoints that we really need to look at oset = {0:None, 200:None} for k in opens.keys(): oset[k] = None for k in closes.keys(): oset[k] = None relevant_indices = sorted(oset.keys()) # Find the clear ranges state = 0 results = [] for i in range(len(relevant_indices) - 1): start = relevant_indices[i] end = relevant_indices[i+1] start_state = state if start in opens: start_state += opens[start] if start in closes: start_state -= closes[start] end_state = start_state if end in opens: end_state += opens[end] if end in closes: end_state -= closes[end] state = end_state if start_state == 0: result_start = start result_end = end results.append((result_start, result_end)) for start, end in results: print(str(start) + " " + str(end)) 

Esto produce:

 0 1 8 9 12 20 30 200 

Los intervalos no necesitan ser ordenados.

Esta pregunta parece ser un duplicado de los intervalos de fusión en Python .

Si entendí bien el problema, tiene una lista de intervalos (1 5; 2 8; 9 12; 20 30) y un rango (0 200), y desea obtener las posiciones fuera de sus intervalos, pero dentro de un rango determinado. ¿Derecha?

Hay una biblioteca de Python que puede ayudarte en eso: intervalos de python (también disponibles en PyPI usando pip). Descargo de responsabilidad: Soy el mantenedor de esa biblioteca.

Suponiendo que importa esta biblioteca de la siguiente manera:

 import intervals as I 

Es bastante fácil obtener tu respuesta. Básicamente, primero desea crear una separación de intervalos basada en los que proporciona:

 inters = I.closed(1, 5) | I.closed(2, 8) | I.closed(9, 12) | I.closed(20, 30) 

Luego, calcula el complemento de estos intervalos, para obtener todo lo que está “afuera”:

 compl = ~inters 

Luego crea la unión con [0, 200], ya que desea restringir los puntos a ese intervalo:

 print(compl & I.closed(0, 200)) 

Esto resulta en:

 [0,1) | (8,9) | (12,20) | (30,200]