Одним из решений (в дополнение ко всем другим представленным здесь различным решениям) является использование дерева интервалов / сегментов (на самом деле это одно и то же):
http://en.wikipedia.org/wiki/Segment_tree
http://en.wikipedia.org/wiki/Interval_tree
Одним из больших преимуществ такого способа является то, что выполнять произвольные логические операции (а не только вычитание) тривиально, используя один и тот же фрагмент кода. Существует стандартная трактовка этой структуры данных в de Berg. Чтобы выполнить любую логическую операцию над парой интервальных деревьев (включая вычитание), вы просто объединяете их вместе. Вот некоторый (по общему признанию наивный) код Python для этого с несбалансированными деревьями диапазонов. Тот факт, что они несбалансированы, не влияет на время, затрачиваемое на объединение деревьев, однако конструкция дерева здесь является действительно тупой частью, которая оказывается квадратичной (если только редукция не выполняется путем разбиения, в чем я почему-то сомневаюсь). В любом случае, вы идете:
class IntervalTree:
def __init__(self, h, left, right):
self.h = h
self.left = left
self.right = right
def merge(A, B, op, l=-float("inf"), u=float("inf")):
if l > u:
return None
if not isinstance(A, IntervalTree):
if isinstance(B, IntervalTree):
opT = op
A, B, op = B, A, (lambda x, y : opT(y,x))
else:
return op(A, B)
left = merge(A.left, B, op, l, min(A.h, u))
right = merge(A.right, B, op, max(A.h, l), u)
if left is None:
return right
elif right is None or left == right:
return left
return IntervalTree(A.h, left, right)
def to_range_list(T, l=-float("inf"), u=float("inf")):
if isinstance(T, IntervalTree):
return to_range_list(T.left, l, T.h) + to_range_list(T.right, T.h, u)
return [(l, u-1)] if T else []
def range_list_to_tree(L):
return reduce(lambda x, y : merge(x, y, lambda a, b: a or b),
[ IntervalTree(R[0], False, IntervalTree(R[1]+1, True, False)) for R in L ])
Я написал этот вид быстро и не так много тестировал, так что могут быть ошибки. Также обратите внимание, что этот код будет работать с произвольными логическими операциями, а не только с различиями (вы просто передаете их в качестве аргумента для операции слияния). Временная сложность оценки любого из них линейна в зависимости от размера выходного дерева (которое также равно количеству интервалов в результате). В качестве примера, я запустил его для предоставленного вами случая:
#Example:
r1 = range_list_to_tree([ (1, 1000), (1100, 1200) ])
r2 = range_list_to_tree([ (30, 50), (60, 200), (1150, 1300) ])
diff = merge(r1, r2, lambda a, b : a and not b)
print to_range_list(diff)
И я получил следующий вывод:
[(1, 29), (51, 59), (201, 1000), (1100, 1149)]
Что, кажется, согласуется с тем, что вы ожидаете. Теперь, если вы хотите выполнить некоторые другие логические операции, вот как это будет работать, используя ту же функцию:
#Intersection
merge(r1, r2, lambda a, b : a and b)
#Union
merge(r1, r2, lambda a, b : a or b)
#Xor
merge(r1, r2, lambda a, b : a != b)