Python：动态区间数据结构

Question

我正在寻找一些Python代码来有效地计算区间重叠。我以前使用过bx-python包的区间树，但现在需要从树中删除区间（或更好的是，修改它们）。似乎bx-python树不支持这个功能。有什么指针吗？

- buddahfist

---

我最近需要做这件事情，最初打算使用一组(起始位置，长度)对在一个以起始位置为索引的红黑树中（用C编写并带有Python绑定）。然后我意识到，在我的情况下，位图足够高效，并且当然，位图实现相对简单。这个方法对你有用吗？ - Robie Basak

谢谢回复！在我的情况下，事情会更加复杂，因为我需要将数据附加到每个间隔，并且当间隔被修改或合并时，我也需要修改/合并相应的数据。不确定从位数组区域到数据保持映射是否那么容易/高效。在树中，我只需将数据存储在节点中即可。 - buddahfist

Answer 1

banyan支持从树中删除区间。例如，要从一个区间列表中删除最小数量的区间，使剩余的区间不重叠，并且时间复杂度为O(n log n)，可以使用banyan.SortedSet（增强型红黑树）：

from banyan import SortedSet, OverlappingIntervalsUpdator # pip install banyan

def maximize_nonoverlapping_count(intervals):
    # build "interval" tree sorted by the end-point O(n log n)
    tree = SortedSet(intervals, key=lambda (start, end): (end, (end - start)),
                     updator=OverlappingIntervalsUpdator)
    result = []
    while tree: # until there are intervals left to consider
        # pop the interval with the smallest end-point, keep it in the result
        result.append(tree.pop()) # O(log n)

        # remove intervals that overlap with the popped interval
        overlapping_intervals = tree.overlap(result[-1]) # O(m log n)
        tree -= overlapping_intervals # O(m log n)
    return result

例子：

print maximize_nonoverlapping_count([[3, 4], [5, 8], [0, 6], [1, 2]])
# -> [[1, 2], [3, 4], [5, 8]]

请查看Python - 移除重叠的列表。

- jfs

Answer 2

如果您正在寻找一个处理区间算术的Python库，请考虑python-interval。免责声明：我是该库的维护者。

该库支持检查重叠，并自动合并区间。例如：

>>> import intervals as I
>>> I.closed(1,2) | I.closed(2,3)
[1,3]
>>> I.closed(1,2).overlaps(I.closed(3,4))
False

如果您想要特别计算重叠部分：

>>> I.closed(1,3) & I.closed(2, 4)
[2,3]

它支持开放/闭合区间，有限或无限。要删除给定区间的间隔，只需使用差分运算符：

>>> I.closed(1, 4) - I.closed(2, 3)
[1,2) | (3,4]

如果您能更具体地说明问题，我可以帮助您。

- Guybrush

---

我看到你的库仅限于整数、浮点数和其他默认变量类型。但我发现这个库在版本控制方面有很棒的用途。例如，I.openclosed(1.2.1,1.3.2) 将会是 (1.2.1,1.3.2]，并且将包含从 1.2.1.x，>1.2.2 到 1.3.2 的所有内容。 - XChikuX

它不仅限于整数或浮点数，而是允许存储任何可比较的值作为边界。很有趣，你建议使用版本作为边界，因为这正是我最初创建这个库的原因;-) 我需要一种统一的方式来编码在不同包装生态系统中使用的依赖关系约束，并且最简单的方法是将所有这些约束转换为区间（当时我没有找到一个处理这样的区间的库）。 - Guybrush

太棒了。我在想你是否有那个版本控制库的开源版本。我尝试使用我的版本和你的版本一起使用，但是出现了AttributeError 's AttributeError: '_PInf' object has no attribute 'vlist'。这里的vlist是我的版本类中从版本字符串派生出来的一个对象。 - XChikuX

请看这里：https://github.com/AlexandreDecan/secos-constraints/blob/master/constraints/versions.py - Guybrush

Answer 3

也许存储所有交集区间可以帮助解决问题。

您需要：

• 所有区间的并集边界，
• 对于每个交集左边界和由其组成的区间列表。

交集区间可以存储在树中，因为它们仅用左边界表示。插入和删除区间的方法如下（简化）：

插入：查找新区间左右边界的交集区间，将这些交集区间分成2或3个新的交集区间。对于每个之间的交集区间，添加指向新区间的指针。

删除：查找左右边界的交集区间，并将它们合并到之前的交集区间中。对于每个之间的交集区间，删除指向已删除区间的指针。

- Ante