Timeranges algoritmo de superposición en Python

Tengo una lista de diferentes ID, fechas de inicio y fechas de finalización, digamos:

[ (5, d.datetime(2010, 9, 19, 0, 0, 0), d.datetime(2010, 9, 19, 0, 5, 10)), (6, d.datetime(2010, 9, 19, 0, 0, 0), d.datetime(2010, 9, 19, 12, 59, 59)), (4, d.datetime(2010, 9, 19, 10, 30, 17), d.datetime(2010, 9, 19, 20, 20, 59)), (6, d.datetime(2010, 9, 19, 14, 12, 0), d.datetime(2010, 9, 19, 23, 59, 59)), (5, d.datetime(2010, 9, 19, 17, 0, 22), d.datetime(2010, 9, 19, 19, 14, 20)) ] 

De alguna manera, necesito encontrar un intervalo de tiempo superpuesto y preparar una nueva lista con los identificadores adecuados que estaban cubiertos en el intervalo de tiempo específico, por ejemplo, para la lista anterior, el resultado debe ser:

 [ ('5,6', d.datetime(2010, 9, 19, 0, 0, 0), d.datetime(2010, 9, 19, 0, 5, 10), ('6', d.datetime(2010, 9, 19, 0, 5, 10), d.datetime(2010, 9, 19, 10, 30, 17), ('4,6', d.datetime(2010, 9, 19, 10, 30, 17), d.datetime(2010, 9, 19, 12, 59, 59), ('4', d.datetime(2010, 9, 19, 12, 59, 59), d.datetime(2010, 9, 19, 14, 12, 0), ('4,6', d.datetime(2010, 9, 19, 14, 12, 0), d.datetime(2010, 9, 19, 17, 0, 22), ('4,5,6', d.datetime(2010, 9, 19, 17, 0, 22), d.datetime(2010, 9, 19, 19, 14, 20), ('4,6', d.datetime(2010, 9, 19, 19, 14, 20), d.datetime(2010, 9, 19, 20, 20, 59), ('6', d.datetime(2010, 9, 19, 20, 20, 59), d.datetime(2010, 9, 19, 23, 59, 59) ] 

Concepto visual:

introduzca la descripción de la imagen aquí

De momento, por ahora tengo una solución como esta: obtengo fechas mínimas y máximas de todo el rango, luego comienzo iteración de min_date a max_date cada 1 segundo, cuando en particular segundo coincidimos con algunos intervalos de la lista de objectives, guardo coincidencias IDs como clave de diccionario y tiempo de agregación de iterador a lista como valor, luego guardarlo en la lista principal, luego siguiente y siguiente. Al final, repaso todos los dictados en la lista de padres y obtengo las identificaciones como claves y la primera y última fecha en la lista de valores como rango que necesito encontrar. Pero esta solución funciona muy lento cuando cuento los rangos en el mes. Porque lleva demasiado tiempo iterar 1 mes en segundos.

Aquí está el código:

  def delta(start, end, delta): cur = start while cur < end: yield cur cur += delta final_ranges = [] last_result = None i = -1 for checker_date in delta( sorted_ranges_by_start[0]['start'], sorted_ranges_by_end[-1]['end'], relativedelta(seconds=1)): aggregator = [] for rng in ranges: if rng['start'] <= checker_date  0: ids = ','.join(set(aggregator)) if last_result != ids: final_ranges.append({}) last_result = ids i += 1 if ids not in final_ranges[i]: final_ranges[i][ids] = [] final_ranges[i][ids].append(checker_date) 

Pero como dije, está funcionando muy lento en grandes rangos.

De esta manera, ayúdeme a encontrar un algoritmo que pueda hacerlo sin iteración a través del mes o tal vez algún consejo para mejorar la velocidad de iteración (no estoy seguro, tal vez intente escribir esta parte en C y luego incrustarla en Python)

Gracias.

Lo he hecho funcionar con el siguiente código.

La explicación básica es detectar primero los puntos de corte entre los períodos proporcionados, es decir, cada vez que un período comienza en los extremos. Segundo, iterar solo entre los puntos de corte, no los puntos, y verificar si se superponen con alguno para ver si están activos entre esos puntos de corte. Acumular periodos activos.

El tiempo de proceso depende de la cantidad de puntos de corte y períodos, y no del tiempo transcurrido.

 from datetime import datetime from sortedcontainers import SortedSet periods = [ (5, datetime(2010, 9, 19, 0, 0, 0), datetime(2010, 9, 19, 0, 5, 10)), (6, datetime(2010, 9, 19, 0, 0, 0), datetime(2010, 9, 19, 12, 59, 59)), (4, datetime(2010, 9, 19, 10, 30, 17), datetime(2010, 9, 19, 20, 20, 59)), (6, datetime(2010, 9, 19, 14, 12, 0), datetime(2010, 9, 19, 23, 59, 59)), (5, datetime(2010, 9, 19, 17, 0, 22), datetime(2010, 9, 19, 19, 14, 20)) ] cutpoints = SortedSet() for period in periods: cutpoints.add(period[1]) cutpoints.add(period[2]) ranges = [] start_cutpoint = None for end_cutpoint in cutpoints: if not start_cutpoint: # skip first start_cutpoint = end_cutpoint continue cut_point_active_periods = [] for period in periods: # check if period and cutpoint range overlap start_overlap = max(start_cutpoint, period[1]) end_overlap = min(end_cutpoint, period[2]) if start_overlap < end_overlap: cut_point_active_periods.append(period[0]) ranges.append((cut_point_active_periods, start_cutpoint, end_cutpoint)) start_cutpoint = end_cutpoint 

Haga dos registros para cada intervalo: {id, time, start/end}

Ordenar la lista de todos estos registros comparados por el tiempo. Si los campos de tiempo coinciden, compare el campo de inicio / finalización y elija finalizar primero.

Camina a través de la lista.

Cuando cumpla con el registro de inicio, agregue id a active list , haga la last time

Cuando cumpla con el registro final, genere active list con la last time etiqueta de last time para obtener el resultado, luego elimine el ID de la lista activa. Cambiar la last time

vamos a tener intervalos

  A: 0..3 B: 1..2 C: 2..4 

Archivos:

  (A,0,s), (A,3,e), (B,1,s), (B,2,e), (C,2,s), (C,4,e) 

Ordenados

  (A,0,s), (B,1,s), (B,2,e), (C,2,s), (A,3,e), (C,4,e) 

Lista ordenada de caminata

  current active output last time (A,0,s) A - 0 (B,1,s) A,BA 0..1 1 (B,2,e) AA,B 1..2 2 (C,2,s) A,C - 2 (A,3,e) CA,C 2..3 3 (C,4,e) - C 3..4 4 

Esto fue todo un reto de progtwigción para mí, pero finalmente lo logré. Básicamente, ordené todas las veces junto con sus ID, y luego ejecuté un bucle for para obtener los resultados:

 from datetime import datetime timelist = [ (5, datetime(2010, 9, 19, 0, 0, 0), datetime(2010, 9, 19, 0, 5, 10)), (6, datetime(2010, 9, 19, 0, 0, 0), datetime(2010, 9, 19, 12, 59, 59)), (4, datetime(2010, 9, 19, 10, 30, 17), datetime(2010, 9, 19, 20, 20, 59)), (6, datetime(2010, 9, 19, 14, 12, 0), datetime(2010, 9, 19, 23, 59, 59)), (5, datetime(2010, 9, 19, 17, 0, 22), datetime(2010, 9, 19, 19, 14, 20)) ] timelist_new = [] for time in timelist: timelist_new.append((time[0], time[1], 'begin')) timelist_new.append((time[0], time[2], 'end')) timelist_new = sorted(timelist_new, key=lambda x: x[1]) key = None keylist = set() aggregator = [] for idx in range(len(timelist_new[:-1])): t1 = timelist_new[idx] t2 = timelist_new[idx + 1] t1_key = str(t1[0]) t2_key = str(t2[0]) t1_dt = t1[1] t2_dt = t2[1] t1_pointer = t1[2] t2_pointer = t2[2] if t1_dt == t2_dt: keylist.add(t1_key) keylist.add(t2_key) elif t1_dt < t2_dt: if t1_pointer == 'begin': keylist.add(t1_key) if t1_pointer == 'end': keylist.discard(t1_key) key = ','.join(sorted(keylist)) aggregator.append((key, t1_dt, t2_dt)) for stuff in aggregator: print stuff 

Salida:

 ('5,6', datetime.datetime(2010, 9, 19, 0, 0), datetime.datetime(2010, 9, 19, 0, 0)) ('5,6', datetime.datetime(2010, 9, 19, 0, 0), datetime.datetime(2010, 9, 19, 0, 5, 10)) ('6', datetime.datetime(2010, 9, 19, 0, 5, 10), datetime.datetime(2010, 9, 19, 10, 30, 17)) ('4,6', datetime.datetime(2010, 9, 19, 10, 30, 17), datetime.datetime(2010, 9, 19, 12, 59, 59)) ('4', datetime.datetime(2010, 9, 19, 12, 59, 59), datetime.datetime(2010, 9, 19, 14, 12)) ('4,6', datetime.datetime(2010, 9, 19, 14, 12), datetime.datetime(2010, 9, 19, 17, 0, 22)) ('4,5,6', datetime.datetime(2010, 9, 19, 17, 0, 22), datetime.datetime(2010, 9, 19, 19, 14, 20)) ('4,6', datetime.datetime(2010, 9, 19, 19, 14, 20), datetime.datetime(2010, 9, 19, 20, 20, 59)) ('6', datetime.datetime(2010, 9, 19, 20, 20, 59), datetime.datetime(2010, 9, 19, 23, 59, 59)) ***Repl Closed*** 

Simplemente elimine esa primera línea de la salida, ya que las fechas de inicio y finalización son las mismas 🙂

 final_list = [] for stuff in aggregator: if stuff[1] != stuff[2]: final_list.append(stuff)