Przepisz algorytm przedziałowy funkcjonalnie

Question

Załóżmy, że mamy szereg interwałów [(a1, b1), (a2, b2), ... , (an, bn)] posortowanych pod względem pozycji początkowych i długości. Chcemy zjednoczyć wszystkie przecinające się interwały. Oto mała próbka zbiór danych, który zawiera co najmniej 2 samodzielnie grup odstępach:

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

i kilka funkcji, musimy sprawdzić na skrzyżowaniu i wydłużyć okresy.

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) 

Możemy po prostu wykonać zadanie przy użyciu standardowego programowania KONIECZNIE:

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

Ale chcę przepisać to przy użyciu programowania funkcyjnego. Moja najbliższa strzał jest:

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) 

Tutaj połowa pracy odbywa się funkcjonalnie, ale wciąż muszę podzielić początkową tablicę stosując podejście imperatywne. Jak mogę to osiągnąć za pomocą czysto funkcjonalnego programowania? Z góry dziękuję.

Answer 1

Zbliżałaś się z użyciem reduce. To rozwiązanie gromadzi listę zwiniętych przedziałów z redukcją.

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, []) 

Również to robi mnóstwo realokacji ponieważ używam + na liście obiektów do gromadzenia wynik. W przypadku bardzo dużych list będzie to nieefektywne. Możesz zajrzeć do biblioteki podobnej do biblioteki pyrsistent, aby uzyskać bardziej wydajne struktury danych do gromadzenia.