Fusionando una lista de tuplas de rangos de tiempo que tienen rangos de tiempo superpuestos

Question

Tengo una lista de tuplas donde cada tupla es (start-time, end-time). Estoy intentando combinar todos los intervalos de tiempo superpuestos y devolver una lista de intervalos de tiempo distintos. Por ejemplo

[(1, 5), (2, 4), (3, 6)] ---> [(1,6)] 
[(1, 3), (2, 4), (5, 8)] ---> [(1, 4), (5,8)] 

Aquí es cómo implementado.

# Algorithm 
# initialranges: [(a,b), (c,d), (e,f), ...] 
# First we sort each tuple then whole list. 
# This will ensure that a<b, c<d, e<f ... and a < c < e ... 
# BUT the order of b, d, f ... is still random 
# Now we have only 3 possibilities 
#================================================ 
# b<c<d: a-------b   Ans: [(a,b),(c,d)] 
#     c---d 
# c<=b<d: a-------b   Ans: [(a,d)] 
#    c---d 
# c<d<b: a-------b   Ans: [(a,b)] 
#   c---d 
#================================================ 
def mergeoverlapping(initialranges): 
    i = sorted(set([tuple(sorted(x)) for x in initialranges])) 

    # initialize final ranges to [(a,b)] 
    f = [i[0]] 
    for c, d in i[1:]: 
     a, b = f[-1] 
     if c<=b<d: 
      f[-1] = a, d 
     elif b<c<d: 
      f.append((c,d)) 
     else: 
      # else case included for clarity. Since 
      # we already sorted the tuples and the list 
      # only remaining possibility is c<d<b 
      # in which case we can silently pass 
      pass 
    return f 

Estoy tratando de averiguar si

1. es el a una función incorporada de alguna módulo de Python que puede hacer esto de manera más eficiente? o
2. ¿Hay una manera más pitonica de lograr el mismo objetivo?

Su ayuda es apreciada. ¡Gracias!

Answer 1

algunas maneras de hacer que sea más eficiente, Pythonic:

1. eliminar la t él set() construcción, ya que el algoritmo debería eliminar los duplicados durante el ciclo principal.
2. Si solo necesita iterar sobre los resultados, use yield para generar los valores.
3. Reducir la construcción de objetos intermedios, por ejemplo: mover la llamada tuple() al punto donde se producen los valores finales, evitando tener que construir y tirar tuplas adicionales, y reutilizar una lista saved para almacenar el rango de tiempo actual para comparación.

Código:

parte

def merge(times): 
    saved = list(times[0]) 
    for st, en in sorted([sorted(t) for t in times]): 
     if st <= saved[1]: 
      saved[1] = max(saved[1], en) 
     else: 
      yield tuple(saved) 
      saved[0] = st 
      saved[1] = en 
    yield tuple(saved) 

data = [ 
    [(1, 5), (2, 4), (3, 6)], 
    [(1, 3), (2, 4), (5, 8)] 
    ] 

for times in data: 
    print list(merge(times)) 

Answer 2

Ordenar tuplas a continuación, lista, si t1.right> = t2.left => fusionar y se reinicia con la nueva lista, ...

->

def f(l, sort = True): 
    if sort: 
     sl = sorted(tuple(sorted(i)) for i in l) 
    else: 
     sl = l 
    if len(sl) > 1: 
     if sl[0][1] >= sl[1][0]: 
      sl[0] = (sl[0][0], sl[1][1]) 
      del sl[1] 
      if len(sl) < len(l): 
       return f(sl, False) 
    return sl 

Answer 3

La especie: utilizar la clasificación estándar, se compara tuplas de la manera correcta ya.

sorted_tuples = sorted(initial_ranges) 

La parte de fusión. También elimina rangos duplicados, por lo que no es necesario un set. Supongamos que tiene current_tuple y next_tuple.

c_start, c_end = current_tuple 
n_start, n_end = next_tuple 
if n_start <= c_end: 
    merged_tuple = min(c_start, n_start), max(c_end, n_end) 

Espero que la lógica sea lo suficientemente clara.

Para ver la próxima tupla, puede usar el acceso indexado a sorted tuples; es una secuencia totalmente conocida de todos modos.

Answer 4

Ordene todos los límites y luego tome todos los pares donde un límite final va seguido de un límite de inicio.

def mergeOverlapping(initialranges): 
    def allBoundaries(): 
     for r in initialranges: 
      yield r[0], True 
      yield r[1], False 

    def getBoundaries(boundaries): 
     yield boundaries[0][0] 
     for i in range(1, len(boundaries) - 1): 
      if not boundaries[i][1] and boundaries[i + 1][1]: 
       yield boundaries[i][0] 
       yield boundaries[i + 1][0] 
     yield boundaries[-1][0] 

    return getBoundaries(sorted(allBoundaries())) 

Hm, no es tan hermoso, pero fue divertido escribir al menos!

EDITAR: Años más tarde, después de un voto positivo, me di cuenta de que mi código estaba equivocado. Esta es la nueva versión sólo por diversión:

def mergeOverlapping(initialRanges): 
    def allBoundaries(): 
     for r in initialRanges: 
      yield r[0], -1 
      yield r[1], 1 

    def getBoundaries(boundaries): 
     openrange = 0 
     for value, boundary in boundaries: 
      if not openrange: 
       yield value 
      openrange += boundary 
      if not openrange: 
       yield value 

    def outputAsRanges(b): 
     while b: 
      yield (b.next(), b.next()) 

    return outputAsRanges(getBoundaries(sorted(allBoundaries()))) 

Básicamente marcar los límites con -1 ó 1 y luego ordenarlos por valor y sólo les salida cuando el equilibrio entre las llaves de apertura y cierre es cero.

Answer 5

Tarde, pero podría ayudar a alguien que busca esto. Tuve un problema similar pero con diccionarios. Dada una lista de rangos de tiempo, quería encontrar superposiciones y fusionarlas cuando sea posible. Una pequeña modificación en respuesta @samplebias me llevó a esto: la función

Combinar:

def merge_range(ranges: list, start_key: str, end_key: str): 
    ranges = sorted(ranges, key=lambda x: x[start_key]) 
    saved = dict(ranges[0]) 

    for range_set in sorted(ranges, key=lambda x: x[start_key]): 
     if range_set[start_key] <= saved[end_key]: 
      saved[end_key] = max(saved[end_key], range_set[end_key]) 
     else: 
      yield dict(saved) 
      saved[start_key] = range_set[start_key] 
      saved[end_key] = range_set[end_key] 
    yield dict(saved) 

datos:

data = [ 
    {'start_time': '09:00:00', 'end_time': '11:30:00'}, 
    {'start_time': '15:00:00', 'end_time': '15:30:00'}, 
    {'start_time': '11:00:00', 'end_time': '14:30:00'}, 
    {'start_time': '09:30:00', 'end_time': '14:00:00'} 
] 

Ejecución:

print(list(merge_range(ranges=data, start_key='start_time', end_key='end_time'))) 

Salida:

[ 
    {'start_time': '09:00:00', 'end_time': '14:30:00'}, 
    {'start_time': '15:00:00', 'end_time': '15:30:00'} 
]