在功能上重写间隔联合算法

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库之类的东西来积累更有效的数据结构。