下面是一個簡單的概念驗證邏輯實現,將布爾函數應用於有限的區間聯合。有限的區間聯合表示爲(開始,結束)對的列表。
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哈哈,你有一個點:) –
標準庫中沒有這樣的類。正如你最後一個例子所顯示的那樣,這個班級必須代表有限的時間間隔。實現起來相對簡單,但會受到浮點數固有的精度限制。 –