python - 在功能上重写一个区间联合算法

Question

假设我们有一个间隔数组 [(a1, b1), (a2, b2), ... , (an, bn)] 根据起始位置和长度排序.我们想要联合所有相交的区间。这是一个包含至少 2 个孤立的间隔组的小样本数据集:

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

还有一些我们需要检查交集和延长间隔的函数。

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)

我们可以使用标准命令式编程简单地完成任务:

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

但我想用函数式编程重写它。我最近的镜头是:

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)

这里一半的工作是在功能上完成的，但我仍然必须使用命令式方法拆分初始数组。我怎样才能使用纯函数式编程来完成这件事？先感谢您。

Answer 1

您已经接近 reduce 的使用了。此解决方案使用 reduce 累积折叠间隔列表。

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

此外，这会进行大量重新分配，因为我在列表对象上使用 + 来累积结果。对于非常大的列表，这将是低效的。您可能会考虑使用类似 pyrsistent 库的东西来获取更高效的数据结构。