下面是一个简单的概念验证逻辑实现,将布尔函数应用于有限的区间联合。有限的区间联合表示为(开始,结束)对的列表。
import functools
import heapq
import itertools
def iter_intervals(tag, interval_set):
for start, end in interval_set:
yield start, tag, True
yield end, tag, False
def apply_boolean_function(f, *interval_sets):
states = [False] * len(interval_sets)
result_state = False
result = []
for boundary, index, new_state in heapq.merge(*itertools.starmap(
iter_intervals, enumerate(interval_sets))):
states[index] = new_state
new_result_state = f(states)
if new_result_state != result_state:
result_state = new_result_state
if new_result_state and result and result[-1] == boundary:
result.pop()
else:
result.append(boundary)
return zip(*[iter(result)] * 2)
union = functools.partial(apply_boolean_function, any)
intersection = functools.partial(apply_boolean_function, all)
complement = functools.partial(apply_boolean_function,
lambda states: not states[0] and states[1])
实例(Python的2):
>>> union([(2, 4), (6, 8)], [(5, 7)])
[(2, 4), (5, 8)]
>>> intersection([(1, 5)], [(2, 6)])
[(2, 5)]
在Python 3,返回值将是一个懒惰zip()
对象,而不是一个列表。您可以将拨打list()
的电话添加到apply_boolean_function()
中的返回语句中,以获取列表。
有一个名为[intervaltree]的软件包(https://pypi.python.org/pypi/intervaltree/2.1.0),它允许您有效地对间隔执行一些操作。它已经有一段时间没有更新,但它可以为你工作,或给你一个暗示寻找什么。 –
@zvone哈哈,你有一个点:) –
标准库中没有这样的类。正如你最后一个例子所显示的那样,这个班级必须代表有限的时间间隔。实现起来相对简单,但会受到浮点数固有的精度限制。 –