Riscrive un algoritmo di unione intervallo funzionalmente

Question

Supponiamo di disporre di una serie di intervalli [(a1, b1), (a2, b2), ... , (an, bn)] ordinati rispetto alle posizioni iniziali e alla lunghezza. Vogliamo unire tutti gli intervalli intersecanti. Ecco un piccolo set di dati di esempio che contiene almeno 2 gruppi isolati di intervalli:

from random import randint 

def gen_interval(min, max): 
    return sorted((randint(min, max), randint(min, max))) 


sample = sorted([gen_interval(0, 100) for _ in xrange(5)] + 
       [gen_interval(101, 200) for _ in xrange(5)], 
       key=lambda (a, b): (a, b - a)) 

E un paio di funzioni che abbiamo bisogno di verificare la presenza di incrocio e di estendere gli intervalli.

def intersects(interval1, interval2): 
    a1, b1 = interval1 
    a2, b2 = interval2 
    return (a1 <= a2 <= b1) or (a1 <= b2 <= b1) 


def extend(interval1, interval2): 
    a1, b1 = interval1 
    a2, b2 = interval2 
    return (a1, b2) if b2 > b1 else (a1, b1) 

Possiamo semplicemente realizzare il compito utilizzando standard di programmazione imperativa:

result = [] 
for interval in sample: 
    if result and intersects(result[-1], interval): 
     result[-1] = extend(result[-1], interval) 
    else: 
     result.append(interval) 

Ma voglio riscrivere questa programmazione funzionale utilizzando. Il mio colpo più vicino è:

subsets = [] 
for interval in sample: 
    if subsets and any(intersects(x, interval) for x in subsets[-1]): 
     subsets[-1].append(interval) 
    else: 
     subsets.append([interval]) 

result = map(lambda x: reduce(extend, x), subsets) 

Ecco la metà del lavoro è fatto in modo funzionale, ma ho ancora di dividere la matrice iniziale utilizzando un approccio imperativo. Come posso ottenere la cosa usando la pura programmazione funzionale? Grazie in anticipo.

Answer 1

Ti stavi avvicinando all'uso di reduce. Questa soluzione accumula l'elenco degli intervalli compressi con riduzione.

def unite_intervals(intervals): 
    def f(acc, element): 
     if acc and intersects(acc[-1], element): 
      return acc[:-1] + [extend(acc[-1], element)] 
     else: 
      return acc + [element] 
    return reduce(f, intervals, []) 

Inoltre, questo fa un sacco di riallocazione dal momento che sto usando + sulla lista di oggetti per accumulare il risultato. Per elenchi molto grandi questo sarà inefficiente. Si può esaminare l'utilizzo di qualcosa come la libreria pyrsistent per strutture di dati più efficienti in cui accumularsi.