在没有集合的情况下减去两个范围之间的重叠

Question

没有设置!

我不能使用Sets因为:

• 范围太长.
• 他们会占用太多记忆
• 集合本身的创建将花费太长时间.

---

仅使用范围的端点,是否有一种减去两个范围列表的最佳方法？

例:

r1 = (1, 1000), (1100, 1200)  
r2 = (30, 50), (60, 200), (1150, 1300)

r1 - r2 = (1, 29), (51, 59), (201, 1000), (1100, 1149)

其他信息:

• r2不必与r1重叠
• r1和r2不会有与其他对重叠的对.例如,r1不会同时具有(0,30)和(10,25)

谢谢.

Answer 1

该间隔包可提供所有你所需要的.

from interval import Interval, IntervalSet
r1 = IntervalSet([Interval(1, 1000), Interval(1100, 1200)])
r2 = IntervalSet([Interval(30, 50), Interval(60, 200), Interval(1150, 1300)])
print(r1 - r2)

>>> [1..30),(50..60),(200..1000],[1100..1150)

Answer 2

一种解决方案（除了此处介绍的所有其他解决方案之外）是使用间隔/段树（它们实际上是同一件事）：

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

我写的很快，并且没有做太多的测试，所以可能有错误。还要注意，此代码将适用于任意布尔操作，而不仅仅是差异（您只需将它们作为合并中op的参数传递）。评估任何一个的时间复杂度与输出树的大小呈线性关系（也与结果中的间隔数相同）。例如，我在您提供的案例中运行了它：

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

Answer 3

这是一个有趣的问题！

我认为这是对的，而且相当紧凑。它应该适用于所有类型的重叠范围，但它假设格式良好的范围（即[x, y)where x < y）。[x, y)为简单起见，它使用样式范围。它基于观察，实际上只有六种可能的安排（结果在 () 中）：

编辑：我发现了一个更紧凑的表示：

(s1 e1)  s2 e2
(s1 s2)  e1 e2
(s1 s2) (e2 e1)

 s2 e2  (s1 e1)
 s2 s1  (e2 e1)
 s2 s1   e1 e2 ()

给定一个排序的端点列表，如果endpoints[0] == s1那么前两个端点应该在结果中。如果endpoints[3] == e1那么最后两个端点应该在结果中。如果两者都不是，那么应该没有结果。

我没有对其进行大量测试，因此完全有可能出现问题。如果您发现错误，请告诉我！

import itertools

def range_diff(r1, r2):
    s1, e1 = r1
    s2, e2 = r2
    endpoints = sorted((s1, s2, e1, e2))
    result = []
    if endpoints[0] == s1 and endpoints[1] != s1:
        result.append((endpoints[0], endpoints[1]))
    if endpoints[3] == e1 and endpoints[2] != e1:
        result.append((endpoints[2], endpoints[3]))
    return result

def multirange_diff(r1_list, r2_list):
    for r2 in r2_list:
        r1_list = list(itertools.chain(*[range_diff(r1, r2) for r1 in r1_list]))
    return r1_list

测试：

>>> r1_list = [(1, 1001), (1100, 1201)]
>>> r2_list = [(30, 51), (60, 201), (1150, 1301)]
>>> print multirange_diff(r1_list, r2_list)
[(1, 30), (51, 60), (201, 1001), (1100, 1150)]